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."