Many probably remember from childhood a popular puzzle called "Fifteen" or "Fifteen". It turns out that this small box with 4x4 cells and 15 numbered square checkers has a curious story that few players suspect.
Despite the widespread misconception that the inventor of the game was the famous American chess player and puzzle inventor Samuel Loyd (who claimed to have invented the puzzle until his death), the authorship of the tags is actually the humble postal clerk Noah Chapman, who in 1874 first showed puzzle to friends. Over time, from hand to hand, the puzzle spread throughout America, its production was quickly put on stream by enterprising merchants. Eh, Noah would have known about the popularity of his brainchild in advance, so he would have filed a patent for it in advance, and then it was too late.
Life decided otherwise, the inventor was exactly one year ahead of the entrepreneur Ernest W. Kinsey. having issued the authorship for himself in 1879. Meanwhile, tagging was already being played everywhere. This was facilitated by ordered articles in newspapers and an interesting advertising move. In early 1880, a certain Charles Pevey, a dentist from Worcester, offered a large monetary reward for solving the problem of collecting a puzzle with rearranged numbers 14 and 15, which must be replaced by moves. On the wave of new popularity in the spring of the same year, the game reached Europe.
Problem 14 and 15 without solution
After some time, a mathematical description of the puzzle was carried out, which showed that half of the problem variants, including the problem with 14 and 15, have no solution, and the maximum combination of all possible variants reaches 20, 922, 789, 888, 000.
To whet the interest of the public, new types of tags were released with a large number of cells and using letters and pieces of a picture instead of numbers. So the puzzle survived to the days of computer technology, where it was also used. Since the 1960s, it has been regularly used in research into the capabilities of Artificial Intelligence. The 3 × 3 puzzle can be easily solved by any search algorithm. 4 × 4 spots are solved by modern AI in a few milliseconds. And for the optimal solution of the 5 × 5 puzzle, a large expenditure of resources is required, even with the use of modern computers and algorithms, and the time takes up to several weeks. The optimal solution to arbitrary configurations of a 6 × 6 puzzle is still beyond the capabilities of modern computers.
And finally, if you suddenly wanted to plunge into childhood or just kill time, you can try to collect "tags" right on this page.