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,
Presto <presto...@hotmail.com> wrote in message
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.
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.
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 !