I was able to locate my copy of 'Fermat´s Enigma,' by Simon Singh, as I mentioned in my last message. He has a very neat mathematical proof, by Sam Loyd himself, showing why certain puzzle configurations might be impossible to resolve.I shall proceed to paraphrase him.
Imagine you have a 4 by 4 puzzle, with 15 pieces, numbered 1 thru 15 from left to right and top to bottom(16 is the empty slot necessary for sliding the other pieces):
| 1
| 2
| 3
| 4
|
| 5
| 6
| 7
| 8
|
| 9
| 10
| 11
| 12
|
| 13
| 14
| 15
| |
Lets now define a Disorder Parameter (Dp) which will be the measure of Disorder within the puzzle. Dp will be a positive integer which stands for the count of puzzle pairs out of order.As the puzzle now stands Dp = 0, since no pieces are out of order.
The puzzle may be easily manipulated in order to produce the following arrangement:
| 1
| 2
| 3
| 4
|
| 5
| 6
| 7
| 8
|
| 9
| 10
| 12
| 15
|
| 13
| 14
| 11
| |
The Dp for this arrangement is 6, since the following puzzle-pairs are out of place:(12,11), (15,13), (15,14), (15,11), (13,11), (14,11). This means that the 12-tile is out of place because it stands before the 11-tile. The 15-tile is out of place because it stands before the 13,14 and 11-tiles. The 13 and 14-tiles are out of order because they stand before the 11-tile.(Note that even though the 10 and 12 tiles stand side-by-side they are not 'out of order' with respect to each other.)
Another possible setup is as follows:
| 1
| 2
| 3
| 4
|
| 5
| 6
| 12
| 7
|
| 9
| 10
| 8
| 15
|
| 13
| 14
| 11
| |
In which case Dp = 12, and the pairs are:(12,7), (12,9), (12,10), (12,8), (12,11), (9,8), (10,8), (15,13), (15,14), (15,11), (13,11), (14,11). The important point to notice is that thru sliding of the puzzle, Dp is always an even number. If a puzzle is created with two pieces inverted, as in Sam Loyd´s puzzle where 14 and 15 were inverted, Dp is an odd number (in this case, 1) and no set of tile-sliding can be performed to arrange the puzzle in the correct, 1 thru 15, manner.
Sliding of any puzzle with an odd Dp value will only generate another odd Dp value. The closest to a solution will be Dp=1, where the 14 and 15-tiles are swapped, and all else is correct.If puzzle pieces are arranged randomically, there´s a 50-50 chance that the generated puzzle will have Dp as an odd number, and thus, be impossible to solve.
As a suggestion for the structure of a 'checking' algortihm, imbedded loops may be used to count the number of disordered puzzle tiles, and if an odd count is reached (Dp%2 == 1) it may be fixed. I'm unsure about this 'fixing' step. Carefull thought must be given in order to un-switch two pieces to produce a even Disoreder parameter.
Unfortunately, all of this means a significant performance hit. Especially with bigger puzzles (more tiles). There seems, however, no way around it.
If anybody has any doubts about this proof, I tried to re-state as best as I could, please email me at gotilla@iname.com
Scott, feel free to alter this message to add clarity.
