The Story of The Fifteen Puzzle Part II

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 Story of The Fifteen Puzzle Part 1

        I recently came across an article on famous Fifteen Puzzle in the book Mathematics Can be Fun by Yakov Perelman. The 15-puzzle which is also known as Gem puzzle, Boss puzzle, Game of fifteen, Mystic Square and etc is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The story of the well known square shallow box with 15 blocks numbered 1 to 15 inclusive is an extremely interesting one, though very few players know it. Here is what W . Ahrens, German mathematician and draughts expert, wrote about it:
        "In the late 1870's there appeared in the United States a new game, 'The Fifteen Puzzle'. Its popularity spread fast and wide, and it soon became a real social calamity. The Fifteen Puzzle hit Europe too. One came across people trying to solve the puzzle everywhere, even on public transport. Office workers and shop salesmen became so absorbed in working it out that their employers had to forbid the game during working hours. Enterprising people took advantage of the mania to arrange large-scale tournaments".
           The puzzle made its way even into the German Reichstag. The well known geographer and mathematician Siegmund Gunther, a Reichstag deputy at the time of the craze, recalled seeing his grey-haired colleagues bending thoughtfully over the little square boxes.
         "In Paris the game was played in the open air, on the boulevards, and soon spread from the capital to the provinces. 'There was no rural homestead where this spider had not woven its web,' was how one French author described the craze.
          "The fever was apparently at its highest in 1880, but mathematicians soon defeated the tyrant by proving that only half of the numerous problems it posed were solvable. There was absolutely no chance of finding a solution for the rest.
          "The mathematicians made it clear why some problems remained unsolved despite all efforts and why the organizers of tournaments were not afraid of offering huge prizes for their solution. In this the inventor of the puzzle, Sam Loyd, surpassed everyone. He asked a New York news paper owner to offer $ 1000 to anyone who solve a certain variant of the Fifteen Puzzle, and when the publisher hesitated, Loyd said he would pay the sum himself. Loyd was well known for his clever conundrums and brain teasers. Curiously enough, he could not get a U. S patent for his puzzle. According to regulations, a person applying for one was required to submit a 'working model'. At the patent office he was asked if the puzzle was solvable, and Loyd had to admit that mathematically it was not. 'In that case,' the official said, there can be no working model and without it there can be no patent. Loyd left it at that, but there is no doubt that he would have been much more insistent could he have but foreseen the unusual success of his invention."
           Here are some facts about the puzzle, as told by the inventor himself :
           "Puzzle enthusiasts may well remember how, in the 1870's, I caused the world to rack its brain over a box with moving blocks, which became known as 'The Fifteen Puzzle'. Thirteen of the blocks were arranged in regular order and only two, 14 and 15, were not (Fig. 1). The task was to shift one block at a time until blocks 14 and 15 were brought into regular order.

                "No one won the $ 1000 prize offered for the first correct solution, although people worked tirelessly at it. There are many humorous stories told of tradesmen who were absorbed in the puzzle they forgot to open their shops, and of respected officials who spent nights seeking for a way to solve the problem. People just would not give up their search for the solution, being confident success. Navigators ran their ships against reefs, locomotive engineers missed stations, and farmers chucked up their ploughs."