Sliding Puzzle Maker

A sliding puzzle is a shallow tray, a set of square tiles and one empty square. A tile next to the gap may slide into it, and that is the only move there is. The goal is to bring the tiles back into order, or to bring a cut-up picture back together, with the gap in the bottom right corner.

Nothing about it looks mathematical. Yet the toy carries an exact piece of arithmetic that decides, before a single tile moves, whether the task is possible at all.

It also carries one of the more durable false credits in the history of games. Both stories are worth telling properly, because the popular versions of each are wrong in the same way: they trust the man who talked loudest.

The craze, and the man who claimed it

In 1880 the puzzle was everywhere in the United States. A library that holds one of the great puzzle collections describes the 15 puzzle as a craze unrivaled until the arrival of a famous twisting cube a century later. The version that caused it had fifteen numbered blocks in a tray four squares wide.

The inventor, according to the puzzle historians Jerry Slocum and Dic Sonneveld as reported by that library and by the encyclopedia article on the puzzle, was Noyes Palmer Chapman, the postmaster of Canastota, New York. He is said to have shown friends an earlier version as early as 1874. Copies travelled by way of his son to Syracuse, and on through acquaintances to Hartford, where students at the American School for the Deaf began making them. By December 1879 they were on sale there and in Boston.

A Boston woodworker, Matthias Rice, started producing the puzzle that same month and had it sold as the Gem Puzzle. In late January 1880 a dentist in Worcester, Charles Pevey, drew attention by offering a cash reward for a solution. Chapman applied for a patent early in 1880 and was refused, probably because a patent for puzzle blocks had been granted to another man in 1878. He made nothing from the mania he started.

Sam Loyd enters the story late. The same account says he had no connection to the invention or to its first success, that his first article about the puzzle appeared in 1886, and that he first claimed to be its inventor in 1891. He kept claiming it until he died in 1911. A book published under his name three years later has him boasting that in the seventies he drove the entire world crazy with a little box of movable blocks.

The claim worked. A respected biography of Loyd still states that he produced the 15 Puzzle in 1878, and a research paper on the puzzle from 2013 opens by saying it is often credited to him. A loud claim, repeated in print for twenty years, turned out to be stronger than a rejected patent application.

Why half the positions are impossible

Loyd’s best-known use of the puzzle was a challenge: start with every tile in order except the 14 and the 15, which are swapped, and put them right. He offered a prize. It was never paid, and his biography says plainly that he knew it was safe, because the task cannot be done.

The proof was already in print. In 1879, in the middle of the craze, William Woolsey Johnson showed with a parity argument that the swapped position has no solution, and William Story completed the picture in the same journal: on any rectangular board at least two squares each way, every arrangement of the right parity can be reached. The arrangements fall into two halves of equal size, and no move crosses from one to the other.

The test is a count. Read the tiles row by row, skip the gap, and count the pairs that stand in the wrong order, a larger number before a smaller one. Each such pair is an inversion. A sideways slide does not change the reading order, so the count stays as it was. A vertical slide carries one tile past the others in between, which on a board four wide is three tiles, and three changes the count from even to odd or back.

So on a board of odd width the count never changes parity, and a position can be solved exactly when its inversion count is even. On a board of even width every vertical move flips it, and what stays fixed is the count plus the row of the gap. Counting the gap’s row from the bottom, starting at one, a position on an even width is solvable exactly when that sum is odd. The solved board has no inversions and its gap in row one.

Here is one to try. Take the 3 x 3 position with rows 8 1 3, then 4, gap, 2, then 7 6 5. The 8 stands before seven smaller tiles. The 3 and the 4 each stand before the 2. The 7 stands before the 6 and the 5, and the 6 before the 5. That is 7 + 1 + 1 + 2 + 1, which makes 12 inversions. Twelve is even and the width is odd, so it can be solved; the tool, given the code sp1-3-813402765, reports the same count and a shortest solution of 14 moves.

Now swap the last two tiles so the bottom row reads 7 5 6. The count drops to 11, and no amount of sliding will ever finish it. Loyd’s challenge is the same trick on the bigger board: one inversion, gap in row one, a sum of two, which is even.

This is also why a physical set must never be mixed by lifting the tiles out. Dropped back at random, they land in the dead half as often as not. A classroom study of 313 pupils in grades 5 to 11 found that about two thirds could work out which case they had been given after a single lesson; the swapped position looks almost solved, which is exactly why it fooled adults for a decade.

How a computer finds the shortest way

Solving a puzzle and solving it in the fewest moves are different problems. For the 3 x 3 board the second can be settled by brute force. There are 181,440 reachable positions; a program can start from the solved board, visit every one in order of distance and write the distance down. The published counts say the largest distance is 31 moves and that exactly two positions need it. The table built by the tool on this page gives the same numbers, term for term.

The 4 x 4 board has 10,461,394,944,000 solvable arrangements, far too many for a table in a browser. The classic answer is a search that goes deeper a little at a time and gives up on any line of play as soon as the moves already made, plus a cautious estimate of the moves still needed, exceed the current limit. If the estimate never overstates, the first solution found is a shortest one.

The usual estimate is Manhattan distance: for each tile, the number of rows plus columns between it and its home. Every move shifts one tile one square, so the sum cannot overstate. It can understate badly, because it pretends tiles pass through each other. One paper reports that a search guided by it tries about 400 million moves on an average random position. Adding a correction for two tiles that sit in their home row in reversed order, where one must step aside, cuts that to about 40 million.

Better estimates come from small tables. Split the fifteen tiles into three groups of five and record, for every placement of one group, the fewest moves of those tiles that bring them home. The three values can be added, and the same paper puts the average search near 3 million moves with about 3 megabytes of tables. That is the scheme this tool builds when asked for a shortest 4 x 4 solution.

It still has a ceiling. A classic set of one hundred test positions averages about 53 moves each, and the hardest positions of all need 80 moves, a figure that took parallel computers to establish; seventeen positions are that far away. The tool stops after twenty million tries. In a test on those hundred positions it finished 86 within that limit. When it does not finish it says so, states how many moves it has ruled out, and offers a longer answer instead.

What the method cannot do, and how to solve by hand

No trick scales. Finding the shortest solution for boards of growing size is known to be intractable in the formal sense, and for the 5 x 5 puzzle the hardest position is only known to lie between 152 and 205 moves. A browser page will not close that gap. For 5 x 5 and 6 x 6 the tool gives a valid answer and labels it as not the shortest.

That longer answer is the way people solve by hand. Finish the top row, then the left column, and treat what remains as a smaller puzzle. The last two tiles of a row are the awkward part: bring them in together, one parked in the corner and the other beneath it, then turn them into place. On the 4 x 4 board this method averaged about 84 moves in testing, against a shortest route of about 53.

Two limits of the tool itself. Its shuffles draw a random arrangement by the standard exchange method, each tile swapped with a randomly chosen one, and repair the parity with a single swap when needed. The numbers come from a seeded generator, which can produce far fewer sequences than there are arrangements; each seed gives a solvable position, but not every position has a seed. Shuffling by sliding at random, the obvious alternative, is worse: analysis of that process on large boards shows the time it needs grows like the fourth power of the side, and in a test for this page twenty random slides left the 3 x 3 board far from evenly mixed.

One last point about pictures. A photograph with a wide plain sky cuts into tiles that cannot be told apart, and two identical tiles in each other’s places can make a solvable puzzle look finished when it is not, or the reverse. Numbers on the tiles remove the doubt, which is why the tool keeps them on unless told otherwise.