The Fifteen Puzzle - the classic N-Puzzle

The most famous of the n-puzzles is the Fifteen Puzzle. Originally know as the Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square, and many others, the puzzle is a classical problem for modeling algorithms involving heuristics.

Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration.

Until his death in 1911, Sam Loyd claimed he invented the puzzle in 1891, but Noyes Palmer Chapman is credited with the puzzles invention. Chapman, a postmaster from Canastota, New York, is said to have show a predecessor puzzle to friends as early as 1874. Chapman’s puzzle consisted of 16 numbered blocks that were to be put together in rows of four, each summing to 34.

Copies of the improved Fifteen Puzzle made their way to Syracuse, New York, by way of Chapman’s son Frank. From there, the puzzle made it’s way to Watch Hill, RI and finally Hartford, CT, where students at the American School for the Deaf started manufacturing the puzzle and selling them locally and in Boston, MA.

As the puzzles popularity spread, others soon copied its design. Matthias Rice, a woodworker in Boston, started manufacturing the puzzle sometime in December 1879 and sold them under the name “Gem Puzzle.” The puzzles popularity soon spread and by February 1880, the puzzle became a national hit in the United States, March in Canada, and April in Europe, but the craze ended almost as soon as it started and crumpled by July.

The solutions to the puzzle vary depending on the number of squares within the puzzle. The larger the n-puzzle – the easier it is to solve. The problem of finding the shortest solution is NP-hard.

Try your skill on this timeless classic.