Rush Hour

Rush Hour is the plastic puzzle on a 6×6 grid where cars and trucks can only slide along their own lane. One car is red, and your single goal is to slide everything else out of its way so the red car can drive out the exit on the right.

Each individual move is laughably simple: a car shifts one square forward or back, if nothing blocks it. There is no scoring, no hidden information, no randomness — you can see the whole board.

And yet a packed board can leave you stuck for an hour. Every car you nudge forces three others to move first, which forces others still. The question "can the red car ever get out?" turns out to have no shortcut — answering it is as hard as any problem that fits in a reasonable amount of memory.

Here is a small Rush Hour board. The red car wants to reach the exit on the right edge. Click a car to select it, then use the arrows to slide it along its lane. A car can only move into empty squares, and only along the direction it is oriented.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="left"  type="button">◀</button>
  <button id="right" type="button">▶</button>
  <button id="up"    type="button">▲</button>
  <button id="down"  type="button">▼</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { position: relative; width: 280px; height: 280px; background: #e8eef3;
         border: 2px solid #cdd9e3; border-radius: 10px; margin: .4rem 0; }
.exit { position: absolute; right: -2px; width: 6px; height: 46px; background: #0a7d33;
        border-radius: 3px; }
.car { position: absolute; border-radius: 8px; cursor: pointer; transition: all .12s ease;
       border: 2px solid rgba(0,0,0,.18); }
.car.sel { outline: 3px solid #1d3557; outline-offset: 1px; z-index: 2; }
.car.red { background: #e63946; }
.car.c1 { background: #4895ef; } .car.c2 { background: #f4a261; }
.car.c3 { background: #8d99ae; } .car.c4 { background: #b5838d; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 15px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; min-width: 42px; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Try to free the red car by hand — then press Solve and watch the computer do a breadth-first search over every reachable arrangement of cars. The counter shows how many distinct board states it had to explore. Even on this tiny board the number is surprising; on a full 6×6 board it explodes, because the only known way to be sure a board is unsolvable is to walk the whole state space.

How hard is Rush Hour, really? Not sliding one car — deciding whether the red car can escape at all.

• Each move is trivial. Sliding a single car is instant, and checking whether a given board is already solved is just looking at the red car's row.
• Brute force walks the state space. The honest method is breadth-first search over every reachable arrangement of cars. On an n×n board the number of states grows exponentially, so this is hopeless at scale.
• It's PSPACE-complete. In 2002, Gary Flake and Eric Baum proved that generalized Rush Hour (on boards of arbitrary size) is PSPACE-complete. They built sliding "logic" gadgets out of cars and showed that any computation using polynomial memory can be encoded as a Rush Hour board whose red car escapes exactly when that computation accepts.
• So PSPACE-complete means Rush Hour is at least as hard as every problem solvable with a polynomial amount of memory — a class that contains all of NP and is widely believed to be even larger.

That is the punchline. Unlike a one-shot puzzle like SAT, Rush Hour's difficulty comes from the long sequence of moves you must plan ahead — the hallmark of PSPACE. Many two-player games and reachability puzzles share exactly this flavor of hardness, where the challenge is not one clever guess but a whole reachable space you cannot shortcut. It is a cousin of the questions behind P vs NP.

"Can I reach a goal configuration by a long chain of legal moves?" is one of the most common shapes a real problem takes, and Rush Hour is its friendly face:

• Motion and rearrangement planning: a robot shuffling boxes in a cluttered warehouse, or parking cars in a tight lot, faces exactly this sliding-block reachability question.
• Model checking: verifying that software or hardware can never reach a bad state is a giant reachability search over configurations — the heart of PSPACE.
• Logistics and routing: moving containers, train cars or aircraft on the ground often reduces to "clear the blockers, in the right order."
• Teaching complexity: because the rules fit on a card, Rush Hour is one of the clearest ways to feel why sequential planning can be harder than a single yes/no puzzle.

Learn why Rush Hour is hard and you've met reachability in a configuration space — the engine under motion planning, automated verification, and countless logistics problems, and a relative of the puzzles around P vs NP.

Rush Hour hides a beautiful secret: the same little cars that you nudge one square at a time can be wired into logic gadgets, and through them into any computation that fits in polynomial memory. Making one move stays trivial; deciding whether the red car can ever escape is PSPACE-complete — as hard as anything in that vast class.

So the next time a board has you gridlocked, take comfort. You are not bad at puzzles. You have run straight into PSPACE-completeness, a hardness deeply tangled with P vs NP, and there may simply be no shortcut to planning your way out.