Fifties - the third in the world for popularity and fame mechanical puzzle. Yields only Puzzles and Rubik's Cube, however, in fact all three of these puzzles share a common root. Moreover, the standard Rubik Cube with 4 by 4 faces is, in fact, bulky spots on six faces.
A puzzle is not an easy task, for solving which, as a rule, requires intelligence, and not special knowledge of a high level.
What's this?
This puzzle belongs to the category of mechanical, that is, it needs to be moved by moving segments. The classic field for the game is a 4 by 4 square, so that it can hold 16 chips. Visually, the field is a board, drawer or frame. The chips are only fifteen, and they are numbered in order, so that on the field one cell remains free and allows the player to move the segments horizontally or vertically. The goal of the game is to move chips in the random order, picking up the correct number from 1 to 15.
The history of creating a puzzle.
There were spots in the 1870s, more precisely, no one can name the date. Among the options is 1874, 76 or 78 years. Most often called the first date, probably in order to emphasize the cyclical nature of the invention of puzzles, because 100 years later the most popular cube Rubik was released.
Sam Lloyd
The same confusion reigns over the authorship of the puzzle. One version insists that the ancestor of this fascinating puzzle was Sam Lloyd (who loves such entertainments, undoubtedly, know this name). However, the facts are stubborn, and they claim that Mr. Lloyd only spoke, but did not do it. He invented a postmaster unknown to the world.
Chronologically, the story is as follows. In 1891, Lloyd states that he came up with specks. However, in 1877, Postmaster Noyes Chapman patented a similar game. And in 1874, that is, even earlier, he invented it. In all likelihood, the postmaster was completely non-ambitious, had no commercial vein and did not promote the game to the masses.
Lloyd himself was not very scrupulous, so to the very last days he claimed that the honor of the invention of the spots belongs to him.
Unbeatable commercial move.
Perhaps, we will not especially dig history and we will lower the dispute about authorship on brakes. The main thing that Lloyd did was to make the whole world get sick with specks. After all, it was his head that came up with a brilliant idea to announce a contest with a prize of $ 1,000 to the one who correctly folded the puzzle. The task seemed to indecency simple, not in their places were only 14 and 15, and the prize was to the point of indecency big. So the people swallowed the bait and began to puzzle over the task.
The truth was that this puzzle did not have a solution, it was not going to. So Lloyd did not risk money, but skillfully heated the public's interest in new fun. The spots were sold out like hot cakes, in batches of millions. However, no one could solve the problem. And the scale of general insanity in the decision was grandiose. Solve the puzzle trying not only in the homeland of the game in the US, but also in Europe, Asia and New Zealand. But in vain. If Lloyd had been born a little earlier, Lynch's trial would have expected him for such tricks.
The Lynch Court is the murder of a person suspected of a crime or violation of public customs, without trial and investigation, usually by a street crowd, by hanging.
Spots are a classic task for modeling heuristic algorithms. Usually the problem is solved through the number of displacements and the search for the Manhattan distance between each knuckle and its position in the assembled puzzle. For the solution algorithms like A * are used.
It can be shown that exactly half of all possible 1 307 674 368 000 (= 15!) Initial spots can not be reduced to the assembled form: let the square with the number i be up to (if counting from left to right and from top to bottom) k squares with numbers less than i . We shall assume that ni = k, that is, if after the knuckle with the i-th number there are no numbers less than i, then k = 0. Also, let us introduce the number e - the number of the row of the empty cell (counting from 1). If the sum is odd, then the solution of the puzzle does not exist
For generalized spots (with more than 15, the number of knuckles), the problem of finding the shortest solution is NP-complete.
By the way, such a hoax led to the fact that the patent office refused to register a puzzle that has no solution.
An interesting algorithm.
The fact is that, only by shuffling the spots, moving them across the field, you can get a task that is guaranteed to have a solution. If all the chips are poured from the field, mixed in hands and randomly arranged on the game board, the probability of finding the right solution is only 50%. Here so!