Borjes Brick Game in Source Code forum

[Chris Boss]

Borje,

Well done !

I never did well with such games but I gave it a try and just by
chance I think I figured out the key to solving the puzzle.
The method works every time:

Step 1:

Slide pieces until you get the bottom row to look like this:

|9|13|14|15|

Step 2:

Slide pieces until you get the top row to look like this:

|1|2|3|4|

Step 3:

Slide pieces until middle rows are correct like this:
(and do not move any of the top or bottom row pieces to do it)

|5| 6| 7| 8|

| |10|11|12|

Step 4:

Move the 9 piece up to get:

|1| 2| 3| 4|
|5| 6| 7| 8|
|9|10|11|12|
| |13|14|15|

Step 5:

Move bottom row left one space to get:

| 1| 2| 3| 4|
| 5| 6| 7| 8|
| 9|10|11|12|
|13|14|15| |

The key is the bottom row of |9|13|14|15| !
Always get that first, then get the top row with |1|2|3|4| next
and then the rest is easy.

I have no idea how I came across this method, but it works every time !

My best time was 1:41 (1 minute 41 seconds).



------------------
Chris Boss
Computer Workshop
Developer of "EZGUI"
http://ezgui.com

[Chris Boss]

New best score: 1:36 (1 minutes 36 seconds).


------------------
Chris Boss
Computer Workshop
Developer of "EZGUI"
http://ezgui.com

[Borje Hagsten]

Thanks - yes, now each game is possible to solve (old code just shuffled
randomly and could end up not being possible to solve). Interesting pattern
you've found. I have always started from left-top and worked my way down
row by row, but your way maybe is faster.

Also note the brc variable in beginning of PBMAIN - it determines number
of bricks to play with.. <IMG SRC="http://www.powerbasic.com/support/forums/smile.gif" ALT="smile">


------------------
http://www.tolkenxp.com/pb
Download: incLean, PBcodec, custom controls and code, etc.
Borje Hagsten - [email protected]

[Karl Lessmann]

.

[This message has been edited by Karl Lessmann (edited September 23, 2003).]

[Borje Hagsten]

Should be no problem - maybe you didn't get all code at copy? PB help says:

"Error 452 - SUB expected - The compiler found an END SUB or EXIT SUB
statement without a procedure defined. You must define a procedure
by beginning it with a SUB statement."


------------------
http://www.tolkenxp.com/pb
Download: incLean, PBcodec, custom controls and code, etc.
Borje Hagsten - [email protected]

[Karl Lessmann]

.

[This message has been edited by Karl Lessmann (edited September 23, 2003).]

[Borje Hagsten]

patrick maxfield posted another way to shuffle the bricks. while i haven't
tested it, i do have tested the existing way extensively and found that
it works - each game is possible to solve.

so can't recommend replacing existing shuffling with patrick's yet, because
especially in 15-tile mode, there are a few game setups that isn't possible
to solve. think shuffling like in "real life" is safest way, and while maybe
not the fastest, still fast enough even in my slow computer. <img src="http://www.powerbasic.com/support/forums/smile.gif" alt="smile">

karl - i'm sure it will work better when you try next time. all is there in
code, so should not be a problem if all is copied correctly.

btw, code is at http://www.powerbasic.com/support/pb...ad.php?t=23876

------------------
http://www.tolkenxp.com/pb
download: inclean, pbcodec, custom controls and code, etc.
borje hagsten - [email protected]



[this message has been edited by borje hagsten (edited june 09, 2003).]

[Karl Lessmann]

.

[This message has been edited by Karl Lessmann (edited September 23, 2003).]

[Michael Mattias]

Interestingly, that [mismatched IF .. END IF ]is not what was flagged. The compiler pointed at the SUB in END SUB with a 452 error.

Sorry to break your heart, but this topic has come up here before and we have been assured that "SUB|FUNCTION EXPECTED" is the <U>correct</U> error message when you have mismatched IF..END IF within a procedure.


MCM

[Patrick Maxfield]

The following apparently should not have been
placed in the source code section. Apologies.
------------------------------------------------------
Neat game. Also nice programming.
I offer a much faster randomizer (see below) based on the fact
that placement of the bricks have two parities, that is, if
bricks are establisheded at random then there is a 1/2
probability that a solution to the puzzle can be obtained.
Also, if you know that a given arrangement offers a solution
then it is easy to show that interchanging two bricks will
change the parity so that no solution can be obtained.
But, if you know that a given arrangement offers a solution
then it is also easy to show that interchanging any three
different bricks will not change the parity, thus allowing for
a solution. Knowing this, I changed the mixing routine in
"ReMix" as follows:
DELETE THe following FROM YOUR PROGRAM:
'-------------------------
ePos = n

RANDOMIZE ' Seed the random number generator
FOR aa = 1 TO n * 100 'experiment if you like - think this is enough to mix them properly..
DO
bb = RND(1, n) - 1 ' Generate number, then see if it can be moved

IF (bPos(bb).z + 1 = ePos AND (bPos(bb).z + 1) MOD brc <> 0) OR _ 'test right of pos 1-3
(bPos(bb).z - 1 = ePos AND (ePos + 1) MOD brc <> 0) OR _ 'test left of position 2-4
bPos(bb).z + brc = ePos OR bPos(bb).z - brc = ePos THEN 'test above/under

tmp = bPos(bb).z
bPos(bb).z = ePos
ePos = tmp
EXIT DO
END IF' LOOP
IF aa > n * 50 AND ePos = n THEN EXIT FOR 'enough many draws and empty pos in down/right corner - use it!
NEXT
EmptyPos = ePos
'-----------------------------------------

REPLACE WITH THE FOLLOWING
'---------------------------------------------
RANDOMIZE
FOR aa=0 TO n-1
bb=RND(0,n-1) : cc=RND(0,n-1)
WHILE aa=bb : bb=RND(0,n-1) : WEND
WHILE (cc=aa) OR (cc=bb): cc=RND(0,n-1) : WEND
tmp=bPos(aa).z
bPos(aa).z=bPos(bb).z
bPos(bb).z=bPos(cc).z
bPos(cc).z=tmp
NEXT aa
'---------------------------------------------

Actually, the "for loop" would also work just fine
with aa=0 to [n-1]/2 or thereabouts because at that
point most of the boxes have been replaced anyway.

Patrick



------------------

[Patrick Maxfield]

An even faster mixer follows.
replace the code I suggested above with following.
This is faster because it eliminates the while-wend loops.
===================================================
DIM P(0,n-1)
RANDOMIZE
FOR aa=0 TO n-1 : P(aa)=aa : NEXT
FOR bb=0 TO n-1
FOR aa=0 TO 2
SWAP P(aa),P(RND(0,n-1))
NEXT aa
tmp=bPos(P(0)).z
bPos(P(0)).z=bPos(P(1)).z
bPos(P(1)).z=bPos(P(2)).z
bPos(P(2)).z=tmp
NEXT bb
============================================
Patrick

------------------

[Karl Lessmann]

.

[This message has been edited by Karl Lessmann (edited September 23, 2003).]

[John McWilliams]

Borje, why do you have time to program a game? <IMG SRC="http://www.powerbasic.com/support/forums/smile.gif" ALT="smile">

[Brad D Byrne]

<IMG SRC="http://www.powerbasic.com/support/forums/wink.gif" ALT="wink"> come on guy's,
any possible combination can be solved!!!
from beginning, of any random mix... 16 posistions gives enough room
to remix to any order... therefore any order must be solvable...
<IMG SRC="http://www.powerbasic.com/support/forums/smile.gif" ALT="smile">
Brad
Added: to simplify proof, a 3x3 square w/ 8 tiles is solvable, and so
is a 2x3 rect w/ 5 tiles <IMG SRC="http://www.powerbasic.com/support/forums/smile.gif" ALT="smile">
------------------
Wash DC Area

[This message has been edited by Brad D Byrne (edited June 09, 2003).]

[Brad D Byrne]

Oop's!!! <IMG SRC="http://www.powerbasic.com/support/forums/redface.gif" ALT="red face">

maybe Brad's wrong... I don't believe a 2x3 is solvable...maybe 3x3,
or 4x4???

Arrgh!! never did like OOP's <IMG SRC="http://www.powerbasic.com/support/forums/smile.gif" ALT="smile">

------------------
Wash DC Area

[Borje Hagsten]

did you read semen's reply at http://www.powerbasic.com/support/pb...ad.php?t=23876 ?

with 15 bricks in a 4x4 board, there are some situations that cannot be
solved. so cannot simply mix randomly (like original code actually did).
like semen also points out - one has to start from a solved game and do
like "real life" shuffling of the bricks.

this is the major challenge when it comes to games programming - writing
the code is nothing, compared to the time it takes to make sure each game
setup also is possible to solve.. <img src="http://www.powerbasic.com/support/forums/smile.gif" alt="smile">


------------------
http://www.tolkenxp.com/pb
download: inclean, pbcodec, custom controls and code, etc.
borje hagsten - [email protected]

[Brad D Byrne]

yeah, Hey Borje,
I should'of know you guy's have thought this through <IMG SRC="http://www.powerbasic.com/support/forums/smile.gif" ALT="smile">
I'm just amazed that a 4x4 isn't solvable??
Brad

------------------
Wash DC Area

[Patrick Maxfield]

Hardly worth discussing but, place numbered bricks at random
and exactly 1/2 of all possible positions will be unsolvable.
The other 1/2 will be solvable.

For arrays with both dimensions >1 the following is true

Given a solvable position, interchanging any 2 bricks
will produce an unsolvable position.
Interchanging here means a --> b --> a

Given a solvable position, interchanging any 3 different bricks
will remain a solvable position.
Interchanging here means a --> b --> c --> a

A very simple proof of the above is available.
==============================================
An example of two unsolvable cases follow
_______
| | |
| 1 | 3 |
|___|___|
| | |
| 2 | |
|___|___|

___________
| | | |
| 1 | 2 | 3 |
|___|___|___|
| | | |
| 4 | 5 | 6 |
|___|___|___|
| | | |
| 8 | 7 | |
|___|___|___|




------------------

[Borje Hagsten]

It is well worth discussing, because it's easy to think all situations are
possible to solve and use random swapping/shuffling. I've even seen some
shareware brick games that has made this mistake.

Did same mistake myself first, but now shuffling is made correctly - each
game is possible to solve thanks to "backwards" shuffling of a solved board,
just like one has to do in a "real-life" physical brick game.


------------------
http://www.tolkenxp.com/pb
Download: incLean, PBcodec, custom controls and code, etc.
Borje Hagsten - [email protected]

[This message has been edited by Borje Hagsten (edited June 10, 2003).]

[Patrick Maxfield]

Borjes
Yes, your method works and is correct.
All I have done is offer another correct,
exact, and mathematically sound method.

In the game you have produced the micro-seconds of difference
between the two methods makes no difference to the user.
I only came forward as a matter of academic exercise because
I have been trained to trim code to the bone, even if
it only means a few steps.

Your method with n=4 takes many hundreds of iterations
where mine takes exactly 24 to perform the same task.
That is my only point and was not meant to disparage
your excellent programming.
Also, this concerns only a miniscule step of a grand
edifice.
Patrick


------------------