Why Traffic Puzzles Are Mathematically Hard

Sliding block puzzle complexity is one of the few corners of recreational mathematics with a complete answer, and the answer is that the puzzles are as hard as the theory allows. Rush Hour on a large enough board is PSPACE-complete. Sliding puzzles whose pieces are all dominoes are PSPACE-hard. And the oldest member of the family, the fifteen puzzle, has a different kind of hardness: half its arrangements cannot be reached at all. Each of those statements has a precise meaning, and each explains something a player feels at the board.

This article explains the three results without notation: what the complexity classes mean, what was actually proved and by whom, and why the results say a hard Rush Hour card is hard and not merely unfamiliar. It then turns to the one-tap family, where Traffic Escape lives, and shows that the same theory says its difficulty is of an entirely different kind.

Easy, hard, and the difference that matters#

Computer science sorts problems by how the effort to solve them grows as the problem gets bigger. A problem is considered tractable if the work grows modestly with the size of the input, and intractable if the work explodes. Sorting a list is tractable; doubling the list roughly doubles the work. Trying every possible sequence of moves in a puzzle is not, because the number of sequences grows faster than any power of the board size.

The class most relevant to puzzles is PSPACE: problems that can be solved using a reasonable amount of memory, even if they may take an enormous amount of time. Puzzles fit there because a solver never needs to remember more than the current position and a path back, but may need to visit a staggering number of positions. A problem is PSPACE-complete if it is in that class and every other problem in the class can be translated into it, which makes it as hard as anything the class contains.

The practical translation is this. If a puzzle family is PSPACE-complete, there is no method that solves every position quickly unless a deep and widely doubted conjecture in computer science is false. Individual positions can still be easy, and a good player can develop strong habits. But the family cannot be reduced to a rule of thumb, and puzzle makers can always construct positions that defeat any fixed method.

Rush Hour: the 2002 proof#

Rush Hour, the board game with a red car, sliding vehicles and a six-by-six grid, was the first traffic puzzle to be placed in this hierarchy. Wikipedia records the result: when generalized so that it can be played on an arbitrarily large board, the problem of deciding if a Rush Hour problem has a solution is PSPACE-complete, proved by Gary Flake and Eric Baum in 2002.

The word generalized carries the weight. The theorem is about the family of Rush Hour boards of every size, and a hardness result needs boards that can grow, because the effort has to be measured against something that grows. On a fixed six-by-six board there are only finitely many positions, so in principle a computer can list them all. What the proof establishes is that the rule itself, sliding vehicles along their length toward an exit, is rich enough to encode arbitrarily hard problems.

For a player the meaning is direct. The reason a hard card feels like a search rather than a read is that it is a search: a sequence of moves must be found among many, some of which move away from the goal, and no local rule identifies them. The history article tells how the game arrived at the theorem; the strategy in the traffic puzzle guide is the best that can be done without the search.

Dominoes are enough: the 2005 result#

Three years later Robert Hearn and Erik Demaine asked how little was needed for a sliding puzzle to be hard, and the answer was very little. Their paper in Theoretical Computer Science, with a preprint freely available on arXiv, introduced a model of computation they called nondeterministic constraint logic and used it to prove that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes and the goal is simply to move a particular piece.

Two features of that sentence deserve attention. All dominoes: no trucks, no odd shapes, no special pieces, just two-square blocks on a grid. Simply to move a particular piece: not to solve an arrangement, merely to get one block to move at all. Even that stripped-down puzzle is PSPACE-hard. Rush Hour's cars and trucks, and Klotski's mix of block sizes, are decoration on a difficulty that the domino grid already contains.

The result also reframes what makes a traffic puzzle hard. It is not the number of vehicles or the size of the board in isolation; it is the interaction of pieces that can move back and forth and get in each other's way. Any puzzle with sliding pieces that stay on the board inherits this hardness, whatever it is called in a store, which is why the patterns article ends by saying patterns can only tell a sliding-puzzle player where to look.

A different hardness: the fifteen puzzle's parity#

The oldest sliding puzzle is hard in a way that has nothing to do with search. The fifteen puzzle, patented in 1880 by Noyes Chapman, has sixteen positions for fifteen tiles and a gap, and every slide swaps the gap with a neighboring tile. That structure preserves a property of the arrangement, and MathWorld records the consequence, proved in 1879: odd permutations of the puzzle are impossible to solve (Johnson 1879), all even permutations are solvable (Story 1879).

Half of all possible arrangements can therefore never be reached from the solved state, no matter how many moves are made. Sam Loyd, who falsely claimed to have invented the puzzle, famously offered a prize for solving an arrangement with two tiles swapped, and the prize was safe: that arrangement is an odd permutation. The puzzle is not hard to solve when solvable; it is impossible when not, and the difference is invisible to a player who does not know the rule.

This is a reminder that hardness comes in kinds. The fifteen puzzle's barrier is a conserved quantity; Rush Hour's is the size of the search. A traffic puzzle player rarely meets the first kind, because vehicles constrained to lanes do not permute freely, but the distinction matters when reading claims about any puzzle being hard: hard to search, hard to reach, and hard to read are three different things.

Puzzle family	Kind of hardness	Result	Who and when
Fifteen puzzle	Unreachable positions	Odd permutations unsolvable; even ones solvable	Johnson and Story, 1879
Rush Hour, generalized	Search	Deciding solvability is PSPACE-complete	Flake and Baum, 2002
Sliding blocks, all dominoes	Search	Moving a given piece is PSPACE-hard	Hearn and Demaine, 2005
One-tap escape (Traffic Escape)	Reading	Every position solvable; order sets the cost	Follows from the rule

Why the one-tap family is not hard in this sense at all#

Traffic Escape and its arrow-drawing sibling on this site look like traffic puzzles and are, by the theory above, something else. Their vehicles do not slide within the grid; a vehicle leaves the board, once, when the straight lane ahead of its nose is clear, and the goal is to empty the board. The move only empties cells. So a vehicle that can leave now can still leave later, the set of free vehicles only grows, and any sequence of legal moves clears the board eventually.

That makes the decision problem trivial. There is no arrangement to reach and no search to run; the answer to "can this position be solved" is always yes. The formal machinery that makes Rush Hour hard, pieces that move back and forth and interfere, has been removed by the rule that nothing comes back. The move-order article works through that property on the arrow version, where the boards have been measured, and it holds for the vehicle version by the same rule.

What remains is a hardness the theory does not measure: reading. A board of a hundred packed vehicles has a small number that are free right now, and the player has four seconds per vehicle on the clock to find them. The difficulty is perceptual, and it is real; players lose hearts on boards a computer would clear without pause. But it is not computational, and the honest description of a one-tap puzzle is a fast reading test on a structure that cannot fail, not a search problem in disguise.

What the theory says to a player#

The results above sort every traffic puzzle into one of two experiences, and knowing which one you are in changes how to play. In a sliding puzzle, a position that resists you may genuinely require a long, partly backward sequence, and there is no shame in it: the family is PSPACE-complete, and no method short of search is guaranteed. Patience, memory and the backward chain from the exit are the tools, and a retry that restores the position is a fresh search, not a failure.

In a one-tap puzzle, a position that resists you is a lane you have not read. The board cannot be stuck, so being stuck means looking in the wrong place, and the fix is procedural: scan the edges, follow the lane the last vehicle vacated, stay with a blocked vehicle rather than switching. Hearts and clock are the only costs, and both are spent by reading slowly, not by reasoning badly.

The two experiences share a theme and a vocabulary, which is why they are confused, and share almost nothing else. The theory settles the question that store listings blur: one family is hard because of what the pieces can do, the other because of how fast the eye can work. A player who knows which is which has, in either family, already made the first correct move.

What to read next#

The strategies that follow from each family's kind of hardness are laid out side by side in how to solve traffic jam puzzles. Where the theorems came from, and how a 1970s board game ended up in a 2002 complexity paper, is in the Rush Hour history article.

The recurring structures that both families reuse, and which of them belong only to the sliding family because they depend on pieces moving within the grid, are named in seven board patterns every unblock car puzzle reuses.

And to feel the difference between search and reading, play Traffic Escape: the first board has no clock, nothing on it can trap you, and the only thing between you and a clear board is finding the noses that face off the edge. That is what a puzzle looks like when the theory has nothing left to say about it, and the eye has everything.