History of sliding block puzzles: 15 Puzzle to Rush Hour

The core idea of a sliding block puzzle is a frame with pieces and not quite enough room: you can only move a piece into the empty space. That idea was already on paper before the famous version arrived. A US patent granted to Ernest Kinsey in 1878 describes puzzle blocks that slide inside a frame with one gap.

The puzzle that made the idea famous was the 15 Puzzle: fifteen numbered tiles in a four-by-four tray, with one space. The long-standing research of Jerry Slocum and Dic Sonneveld, set out in their 2006 book The 15 Puzzle, traces it to Noyes Chapman, the postmaster of Canastota in New York state. Versions were being sold as the Gem Puzzle by the end of 1879.

Sources1Source 1Kinsey, E. U. (1878). Improvement in puzzle-blocks (U.S. Patent No. 207,124). U.S. Patent Office.2Source 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

In the early months of 1880 the 15 Puzzle became a craze. It spread across the United States within weeks and on to Europe, turning up in offices, parlours and newspaper columns. Accounts differ on the exact weeks, but by the spring it was everywhere, and by the summer it was fading. Chapman applied for a patent, which was refused; the reason is not certain, and one likely explanation is that earlier sliding-block patents already covered the idea.

Part of the fascination was that some starting positions seemed impossible, and they were. In 1879 William Woolsey Johnson and William Story published notes on the puzzle in the American Journal of Mathematics showing that exactly half of all arrangements can never be solved. The argument rests on parity: every slide changes the arrangement in a way that keeps a hidden even-or-odd count fixed, so a position with the wrong count cannot be reached, however long you try.

That result explains the most famous trick in the puzzle’s history. Swap only the 14 and the 15 in a finished tray and you have a position that looks one move from done and is in fact unreachable.

Sources3Source 3Johnson, W. W., & Story, W. E. (1879). Notes on the “15” puzzle. American Journal of Mathematics, 2(4), 397–404.

For most of the twentieth century, the 15 Puzzle was credited to Sam Loyd, America’s best-known puzzle writer. Loyd said he had invented it and offered a large prize for solving the impossible 14–15 swap. Slocum and Sonneveld’s research found that Loyd first made the claim in 1891, more than a decade after the craze, and kept it up until his death in 1911. There is no evidence he had anything to do with inventing the puzzle, or that his prize was on offer during 1880.

The claim stuck because Loyd was famous, his puzzle books were widely reprinted, and later writers repeated it. It is a good reminder that puzzle history, like any history, is worth checking against the record.

Sources2Source 2Slocum, J., & Sonneveld, D. (2006). The 15 puzzle: How it drove the world crazy. Slocum Puzzle Foundation.

The next big family changed the goal. Instead of putting tiles in order, you had to move one large block to an exit through a crowd of smaller ones. A patent filed by Lewis W. Hardy in 1907 and granted in 1912 describes ten blocks of different sizes packed into a box and moved only by sliding. A closely related design was sold as the Pennant Puzzle.

Similar puzzles followed under many names. The Smithsonian’s collection holds a Dad’s Puzzler, copyrighted in 1926, with one large square block, several rectangles and two small squares. In many countries the family is known today as Klotski, and in China a version called Huarong Dao tells the story of a general escaping an ambush. Minimum solutions for the classic layouts run to around 80 moves, depending on how you count a move.

In the 1990s the idea found its most successful modern form. The Japanese puzzle designer Nob Yoshigahara created a sliding-car puzzle known as Tokyo Parking, and Binary Arts, later ThinkFun, released it in the United States in 1996 as Rush Hour. Cars and lorries block a small grid; you slide them back and forth until your car can drive out. Graded challenge cards took it from a single puzzle to a series, and it became a fixture of classrooms and family tables.

Sources4Source 4Hardy, L. W. (1912). Puzzle (U.S. Patent No. 1,017,752). U.S. Patent Office.5Source 5Smithsonian National Museum of American History. (n.d.). Dad’s Puzzler, once owned by Olive C. Hazlett [Object 2015.0027.04].6Source 6Contreras, M. (2018, February 1). The evolution of ThinkFun’s Rush Hour. ThinkFun. Archived by the Internet Archive, 25 December 2022.

Sliding block puzzles look like toys, but they are serious objects in computer science. It took until 1999 to establish that any solvable position of the 15 Puzzle can be finished in at most 80 single-tile moves; Korf and Schultze later confirmed it with a search that ran for 28 days and found exactly 17 positions that need all 80.

In 2002 Gary Flake and Eric Baum proved that the general form of Rush Hour, on a board of any size, is PSPACE-complete, a class of problems believed to be even harder than the famous NP-complete ones. Robert Hearn and Erik Demaine then showed in 2005 that general sliding-block puzzles are PSPACE-complete too, even when every block is the same small domino. In plain terms, there is no known shortcut that solves every board quickly, which is exactly why a good sliding puzzle stays interesting.

Sources7Source 7Korf, R. E., & Schultze, P. (2005). Large-scale parallel breadth-first search. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI-05) (pp. 1380–1385). AAAI Press.8Source 8Flake, G. W., & Baum, E. B. (2002). Rush Hour is PSPACE-complete, or “Why you should generously tip parking lot attendants”. Theoretical Computer Science, 270(1–2), 895–911.9Source 9Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2), 72–96.

OutBrick belongs to the get-one-block-out branch of the family, with a twist of its own: every brick has somewhere to go. A brick leaves the board only through the gate of its colour, and today it can also swap with a neighbour so that three of a colour line up and clear. Clearing a board means working out the order, as it did for Hardy’s blocks and Yoshigahara’s cars.

The modern tools help in ways the 1880 players would have envied. Every one of OutBrick’s 2,000 boards was cleared by a solver before it shipped, so no player ever meets a 14–15 swap. If you want the practical side of all this history, our guide on how to solve sliding block puzzles sets out the strategies, and you can try a board in your browser.

• Late 1870s: sliding blocks in a frame appear in US patents.
• Late 1879: the 15 Puzzle is on sale; Johnson and Story prove half of all positions unsolvable.
• 1880: the 15 Puzzle craze sweeps the United States and Europe.
• 1891: Sam Loyd first claims to have invented it.
• 1907–1912: Hardy’s get-one-block-out puzzle is patented.
• 1996: Rush Hour is released in the United States.
• 2002–2005: Rush Hour and sliding-block puzzles are proved PSPACE-complete.