Sliding puzzles - Algorithm?
BSvK
puzzle ? Or what is the idea behind such an algorithm ? I don't mean a
solving program - I know Balmoral Software has one - I'd like to know the
general principle for finding a solution. Thanks for help.
Presto
Here is the way I have learned to solve 3X3 sliding puzzles. It works very
well for me. I am sure there are more complete solutions out there but this
works fine.
For explanation sake let's suppose you have a 3X3 puzzle with pieces
numbered 1-8. The upper left corner is 1 then below it is 2 and then 3.
The next column is of course 4,5,6 and the rightmost column is is 7,8 with
the lower right being empty. Now you scramble the pieces.
It is easy to put the first piece any place you want. You are going to try
to put 1,2,3 (one column) in place. The trick is you put 2 in where 3
should be (lower left corner) and then put 1 above it. Now move 3 into
position just to the right of 2. Finally you slide 1 and 2 up and then 3
moves into place.
Now you are left with a very small puzzle (only 2 X 3). You do not disturb
the column which you have just completed. Leave it alone and randomly move
around the 5 remaining pieces. If you do it in a very random manner (zig
zaging the tiles around as wildly as possible you will suddenly come upon
the solution. The only way it could take a long time is if you fall into
the trap of repeating the same few moves over and over again.
Now if you have a very large puzzle it is not hard to solve it column by
column and then row by row, each time reducing the large puzzle to a smaller
puzzle until you only have a 2X3 puzzle.
Try this and let me know if it works for you,
BSvK
the size in this way. It may happen the the reduced puzzle has a wrong
parity and hence may be unsovable without disturbing the already solved row
or column. This happens to me by trying to reduce 4x4 puzle to 3x3. Although
I think that among several ways to arrange the first column or row in the
correct sequence there is always one for which the reduced puzzle has the
correct parity it is not always clear how to find it in a systematic way.
Presto <presto...@hotmail.com> wrote in message
news:8elioj$2lgc$1...@newssvr04-int.news.prodigy.com...
David Vanderschel
BSvK <bshu...@redshift.com> wonders:
> What kind of an algorithm can be used to solve a standard tile sliding puzzle
?
I am not quite sure what you mean by "standard". I am going to take it to be
fairly general in the sense that the tiles need not all be unit squares. (Eg..,
there can be a 2x2, a 1x2, or a 2x1 tile in the 'box'.)
A more tractable abstraction of the puzzle is a graph in which the vertices
correspond to possible arrangements of the tiles and the edges connect pairs of
vertices such that the arrangement corresponding to one of the vertices can be
transformed into that of the other by one simple 'move'. Now, in graph
theoretic terms, we are simply looking for a shortest path between specified
vertices (or sets of vertices). There is a sizable body of literature on this
subject. In general, it is hard, especially if you insist on the very best
answer. However, there are often heuristics arising from the geometry of the
original puzzle than can help focus the search.
If the search space is small enough, you can just brute force it by inductively
generating all positions reachable in N moves. (When generating the (N+1)-move
set, just avoid generating anything that is already in the (N-1)-move or N-move
sets.) Note a precursor of each generated position, and stop when the generated
set contains a target position.
Regards,
David V.
Willem-Jan Monsuwe
)the size in this way. It may happen the the reduced puzzle has a wrong
)parity and hence may be unsovable without disturbing the already solved row
)or column. This happens to me by trying to reduce 4x4 puzle to 3x3. Although
)I think that among several ways to arrange the first column or row in the
)correct sequence there is always one for which the reduced puzzle has the
)correct parity it is not always clear how to find it in a systematic way.
HUH?
Is there something I'm missing ? You can only change the parity of the
remaining bit by changing the parity of the already solved bit. Which you
can only do by exchanging two tiles in the solved bit. Which kind of makes
'solved' a misnomer.
In other words: if subpuzzle-plus-solved-bit has even parity, then the
subpuzzle will have even parity, because the solved bit has parity zero.
The only situation I can imagine where this happens is if there is more than
one solution, I.E. tiles are interchangeable.
SaSW,
--
Willem (at stack dot nl)
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Busha Dinsa
Is there 8 slider puzzle related project?