Rush Hour (Traffic Jam)
Slide the cars aside and drive the red one out. Every stated move count is proved by search, not estimated.
Every stated move count here is proved
Rush Hour has a small enough state space that a breadth-first search settles the minimum number of moves outright — so each puzzle can state its optimal length rather than estimate it, and the hint button gives the next move on a genuinely shortest path instead of a heuristic guess that might be leading you somewhere longer.
That mattered more than expected. The first draft of these puzzles carried hand-guessed lengths, and three of the four were wrong — one by double. The test now re-derives every figure from the solver, so a puzzle whose stated length drifts from its real length fails the build rather than quietly misleading anyone. It is a small thing, but a puzzle that claims six moves and needs eleven is worse than one that claims nothing.
The whole game fits in memory, so every stated length is proven
A six-by-six board with a handful of vehicles has a small enough state space that breadth-first search can enumerate all of it — unusual for a sliding puzzle, and what makes an exact solver practical here. Each level's minimum move count below is re-derived by that solver rather than typed in, so a level whose stated length drifted from its real length would fail the tests rather than quietly mislead anyone.
| Level | Vehicles | Reachable states | Legal moves | Branching | Shortest solution |
|---|---|---|---|---|---|
| Warm up | 2 | 25 | 80 | 3.2 | 1 |
| One blocker | 3 | 64 | 238 | 3.7 | 6 |
| Traffic | 5 | 200 | 980 | 4.9 | 9 |
| Gridlock | 8 | 7,221 | 49,558 | 6.9 | 11 |
Each extra vehicle multiplies the space and adds about one legal move per position. Going from 5 vehicles to 8 takes it from 200 states to 7,221 — 36 times larger for 3 more cars.
The same search makes the hint honest. Walking every level from start to finish taking only hinted moves, all 27 hints reduced the distance to the goal by exactly one — not a reasonable-looking move, a move on a genuinely shortest path, every time. And 27 is exactly the sum of the four solution lengths, so following hints never wastes a move.
And 99.3% of everywhere you can get to is a detour
A position is on a shortest path if the moves to reach it plus the moves still needed add up to the level's minimum. Counting those across the whole reachable space:
| Level | On a shortest path | Reachable | Share |
|---|---|---|---|
| Warm up | 2 | 25 | 8.0% |
| One blocker | 7 | 64 | 10.9% |
| Traffic | 33 | 200 | 16.5% |
| Gridlock | 52 | 7,221 | 0.7% |
The share collapses as the puzzle gets harder, which is exactly what makes a hard puzzle hard. It is not that the solution is long — 11 moves is not long. It is that the space of things you can do instead has grown enormously and almost none of it helps. On Gridlock only 52 of 7,221 positions are on a shortest path.
The other side of the same fact: from Gridlock's starting position you can reach a state 33 moves from the goal — 3 times further away than you began — without ever making an illegal move. Every level has a corner further from the goal than its own solution length.
How to use
- Tap a car to select it, then tap a dot to slide it.
- Cars only move along their own length — no turning.
- Get the red car out through the gap on the right.
- The hint gives the next move on a genuinely shortest path.
Frequently asked questions
How do you play Rush Hour?
Cars and lorries sit on a six by six grid and slide only forwards and backwards along their own axis — never sideways and never turning. Your red car sits on the exit row, and the puzzle is to shuffle everything else out of its way so it can drive off the right-hand edge.
How is the minimum number of moves known?
By exhaustive search. Rush Hour has a small enough state space that a breadth-first search visits every reachable position and settles the shortest solution outright, so the figures quoted here are proved rather than estimated. That is unusual for a sliding puzzle and is what makes an honest hint possible.
Is the hint actually optimal?
Yes. It returns the first move of a genuinely shortest path from wherever you are now, recomputed from the current position rather than replayed from a stored solution. Following it repeatedly finishes the puzzle in the minimum number of moves from any position you have reached.
Why are the move counts here trustworthy?
Because the tests re-derive every one of them from the solver, so a puzzle whose stated length drifts from its real length fails the build. That check earned its keep immediately — the first draft carried hand-guessed figures and three of the four were wrong, one by double.
Does a move mean one square or one slide?
One square here, which is the stricter convention. Some versions count a slide of any distance as a single move, which produces much smaller numbers for the same puzzle — worth knowing when comparing your result against a figure quoted elsewhere.
What makes a Rush Hour puzzle hard?
Not the number of vehicles but the depth of the dependency chain — how many cars must move before the one blocking you can move. The hardest known configurations need dozens of moves and involve long sequences that appear to make no progress at all, which is exactly what defeats trial and error.
Is there a good general strategy?
Work backwards from the exit. Identify what blocks the red car, then what blocks that, and so on, and you usually find the puzzle is one chain rather than a tangle. Moving a car simply because it can move is the commonest way to waste twenty moves.
Can a position become unsolvable?
Not by ordinary play — every move here is reversible, so you can always retrace your steps. What can happen is going round in circles, which is why the solver reporting the distance from your current position is more useful than it sounds: if the number has gone up, you are heading the wrong way.
How many puzzles are possible?
Millions of legal configurations exist, though only a fraction are interesting — most are trivial or unsolvable. Researchers have enumerated the solvable positions exhaustively and catalogued the hardest, which is how the famously difficult configurations were found rather than designed.
Where did the game come from?
It was invented by Nob Yoshigahara in Japan in the 1970s and later published commercially by Binary Arts, now ThinkFun. It has become a standard example in artificial intelligence courses precisely because the state space is small enough to search exhaustively while the puzzles remain hard for people.
Why is it used to teach search algorithms?
Because it is the rare puzzle where breadth-first search is both practical and clearly correct. The state space is finite and modest, every move is reversible, and the shortest path is exactly what you want — so it demonstrates the algorithm without the approximations that larger problems force on you.
Does the game save my progress?
No. Everything runs in your browser, nothing is stored or uploaded, and closing the tab loses the current position. Undo works back to the start of the puzzle within a session.
🔒 This tool runs entirely in your browser. Nothing you enter is uploaded, logged, or stored.