In my previous post I gave a brief introduction about the Fifteen Puzzle, in this post I am trying to give you more insight into this puzzle. On the whole, the puzzle is extremely complicated and closely connected with one of the sections of advanced algebra ("the theory of determinants"). Here is what Ahrens wrote about it :
The job is to shift the blocks by using the blank space so as to arrange all 15 in a regular order, i.e. to have block 1 in the upper left - hand corner, block 2 to the right of it, block 3 next to block 2, and block in the upper right - hand corner; to have block 5, 6, 7, and 8 in this order in the next row, etc. (see Fig. 2).
Imagine for a moment that the blocks are all placed at random. It is always possible to bring block 1 to its correct position through a series of moves. It is equally possible to shift block 2 to the next square without touching block 1. Then, without touching blocks 1 and 2, one can move blocks 3 and 4 into their places. If, by chance, they are not in the last two vertical rows, it is easy to bring them there and to achieve the desired result. The top row 1, 2, 3, and 4 is now in order and in our subsequent operations we shall leave these four blocks alone. In the same way we shall try to put in order the row 5, 6, 7, and 8; this is also possible. Further, in the next two rows it is necessary to bring blocks 9 and 13 to their correct positions. Once in order, blocks 1, 2, 3, 4, 5, 6, 7, 8, 9, and 13 are not shifted any more. There remains six squares one of them blank and the other five occupied by blocks 10, 11, 12, 14, and 15 in pellmell order. It is always possible to shift block 10, 11, and 12 until they are arranged correctly. When this is done, there will remain blocks 14 and 15 in proper or improper order in the bottom row (Fig. 1).
If a combination, which we shall call C for short, can be rearranged into positions in Fig. 2 (position I), then it is obvious that we can do the reverse too, i.e. rearrange position I into combination C. After all, every move can be reversed: if, for instance, we can shift block 12 into
blank space, we can bring it back to its former position just as well.
Thus, we have two series of combinations : in the first we can bring the blocks into regular order (position I) and in the second into positions in Fig. 1 (position II). And conversely, from regular order we can obtain any combination of the first series and from position II any combination of the second series. Finally, any one of the two combinations of the same series may be reversed.
Is it possible to transform position I into position II? It may definitely proved that no number of moves is capable of doing that. Therefore, the huge number of combinations of blocks may be classed into two series, the first series where the blocks can be arranged in regular order, i.e. the solvable; and the second series where in no circumstances can the blocks be brought into regular order, i.e. the insoluble, and it is for the solution of these positions that huge prizes were offered. Is there any way of telling to what series the position belongs? There is, and here is an example.
Let us analyze the following position. The first row of blocks is in order and second, too, with the exception of block 9. This block occupies the space that rightfully belongs to block 8. Therefore block 9 precedes block 8. Such violation of regular order is termed 'disorder'. Our analysis further shows that block 14 is three spaces ahead of its regular position, i.e. it precedes blocks 12, 13, and 11. Here we have three 'disorders' (14 before 12, 14 before 13, and 14 before 11). All together we have 1+3=4 'disorders'. Further, block 12 precedes block 11, just as block 13 precedes block 11. That gives us another two 'disorders' and brings their total to 6. In this way we determine the number of 'disorders' in each position, taking good care to vacate beforehand the lower right hand corner. If the total number of 'disorders', as in this case, is even, then the blocks can be arranged in regular order and the problem is solvable. If, on the other hand, the number of 'disorders' is odd, then the position belongs to the second category, i.e. it is insoluble.
Mathematical explanation of this puzzle has dealt a death blow to the craze. Mathematics has created an exhaustive theory of the game, leaving no place whatever for doubts. The solution of the puzzle does not depend on guess work or quick wit, as in other games, but solely on mathematical factors that predetermine the result with absolutely certainty.
The job is to shift the blocks by using the blank space so as to arrange all 15 in a regular order, i.e. to have block 1 in the upper left - hand corner, block 2 to the right of it, block 3 next to block 2, and block in the upper right - hand corner; to have block 5, 6, 7, and 8 in this order in the next row, etc. (see Fig. 2).
If a combination, which we shall call C for short, can be rearranged into positions in Fig. 2 (position I), then it is obvious that we can do the reverse too, i.e. rearrange position I into combination C. After all, every move can be reversed: if, for instance, we can shift block 12 into
blank space, we can bring it back to its former position just as well.
Thus, we have two series of combinations : in the first we can bring the blocks into regular order (position I) and in the second into positions in Fig. 1 (position II). And conversely, from regular order we can obtain any combination of the first series and from position II any combination of the second series. Finally, any one of the two combinations of the same series may be reversed.
Is it possible to transform position I into position II? It may definitely proved that no number of moves is capable of doing that. Therefore, the huge number of combinations of blocks may be classed into two series, the first series where the blocks can be arranged in regular order, i.e. the solvable; and the second series where in no circumstances can the blocks be brought into regular order, i.e. the insoluble, and it is for the solution of these positions that huge prizes were offered. Is there any way of telling to what series the position belongs? There is, and here is an example.
Let us analyze the following position. The first row of blocks is in order and second, too, with the exception of block 9. This block occupies the space that rightfully belongs to block 8. Therefore block 9 precedes block 8. Such violation of regular order is termed 'disorder'. Our analysis further shows that block 14 is three spaces ahead of its regular position, i.e. it precedes blocks 12, 13, and 11. Here we have three 'disorders' (14 before 12, 14 before 13, and 14 before 11). All together we have 1+3=4 'disorders'. Further, block 12 precedes block 11, just as block 13 precedes block 11. That gives us another two 'disorders' and brings their total to 6. In this way we determine the number of 'disorders' in each position, taking good care to vacate beforehand the lower right hand corner. If the total number of 'disorders', as in this case, is even, then the blocks can be arranged in regular order and the problem is solvable. If, on the other hand, the number of 'disorders' is odd, then the position belongs to the second category, i.e. it is insoluble.
Mathematical explanation of this puzzle has dealt a death blow to the craze. Mathematics has created an exhaustive theory of the game, leaving no place whatever for doubts. The solution of the puzzle does not depend on guess work or quick wit, as in other games, but solely on mathematical factors that predetermine the result with absolutely certainty.
