HISTORY · 2026-09-23
Rush Hour (1996) — The Year a Wooden Traffic Jam Earned a PSPACE-Complete Proof
16 vehicles on a 6×6 board, each able to move only forward and back — the puzzle Nob Yoshigahara left behind
Introduction — A Board Built for One Red Car
This is the story of Rush Hour, a wooden sliding-block puzzle released in 1996 by Binary Arts Corporation, now known as ThinkFun, in the United States. The board is a 6×6 grid holding sixteen vehicles: twelve cars and four trucks. There is exactly one rule — every vehicle keeps the orientation it started in and can only slide forward or back along that line. No rotating, no lifting.
The goal is just as simple: clear a path so the single red car, parked facing the exit, can slide free of the jam. Yet moving one vehicle out of the way almost always blocks another's escape route. The puzzle has sold well over a million units since its release.
An impression of the red car boxed in by other vehicles (illustration, AI-generated)
Context — Nob Yoshigahara, the Japanese Puzzle Designer
The inventor was Japanese puzzle designer Nob Yoshigahara (1936–2004). He studied applied chemistry at the Tokyo Institute of Technology, worked as a chemist, then taught high-school math and chemistry while writing more than eighty puzzle books over his lifetime. The same hand also oversaw Hanayama's metal Cast Puzzle series, launched in 1983.
What he had designed was originally a wooden sliding puzzle called "Tokyo Parking" — the universal frustration of a gridlocked car, turned into a board. In 1995 the puzzle was brought to Binary Arts Corporation.
The development team first considered blunt working titles like "Bad Traffic" and "Move It!", naming the irritation directly. Then they reversed course entirely, reframing the puzzle around the satisfaction of escaping the jam. The red car's driver was given a name, "Rush Hour Joe," and the game shipped in 1996 as Rush Hour.
An impression of one vehicle escaping a wooden puzzle box (illustration, AI-generated)
Mechanics — One Rule: Forward and Back, Nothing Else
The board's rules are strikingly few. On a 6×6 grid sit twelve two-square cars and four three-square trucks. Every vehicle has a fixed orientation, horizontal or vertical, and can only slide along that single line — never diagonally, never rotated.
Only the red car is fixed to the exit row; the goal is simply to clear whatever blocks its path out. But moving one vehicle nearly always seals another's route. The whole board is woven from vehicles fighting each other for room to move.
The set ships with forty puzzle cards across four difficulty tiers, from Beginner to Expert. The hardest known configuration takes 51 moves to solve counting each slide as one move, or 93 steps counting single-square increments. That every move reshuffles the entire board's possibilities was the puzzle's real hook.
An impression of vehicles that can only slide forward and back (illustration, AI-generated)
Legacy — A Proof, and a Second Life on Steam
This property — that moving one vehicle reshuffles everything else — drew attention well beyond the toy shelf. In 2002, computer scientists Jeffrey Flake and Eric Baum published "Rush Hour is PSPACE-complete, or Why you should generously tip parking lot attendants" in Theoretical Computer Science, proving that deciding whether a generalized, arbitrarily large Rush Hour configuration is solvable belongs to the PSPACE-complete class.
PSPACE-complete means that, for every algorithm known today, the effort needed to find a solution explodes as the board grows — a guarantee from complexity theory itself. A plain toy about sliding a red car out of a jam had been shown to belong among computer science's hardest problem classes.
The research didn't stop there. A 2020 paper, "1×1 Rush Hour with Fixed Blocks is PSPACE-complete" (Brunner, Chung, et al., presented at the 2021 FUN conference), showed the same result holds even when every vehicle is shrunk to a single square. A quarter-century on, the 1996 wooden puzzle remains an active subject in complexity research.
The puzzle itself kept evolving too: a railroad edition, Railroad Rush Hour, arrived in 1998, and an app followed in 2009. In 2022, Germany's Markt+Technik Verlag released an official digital edition, Rush Hour Deluxe, on Steam under license from ThinkFun (Ravensburger), with sixty challenges and local multiplayer for up to four. The rules born on a wooden board now sit, unchanged, in a Steam library.
An impression of the lineage from a wooden block to a pixel grid (illustration, AI-generated)
Sources
Sources referenced in this article:
• Wikipedia: Rush Hour (puzzle)
• ThinkFun: The Evolution of ThinkFun's Rush Hour
• Brandeis University (Storer): Rush Hour's Creation — The Dramatic Story of Rush Hour's Birth
• arXiv: 1×1 Rush Hour with Fixed Blocks is PSPACE-complete (Brunner, Chung, et al., 2020)
Closing — What Nob Yoshigahara Left Behind
Nob Yoshigahara died in 2004 at the age of 68. Among the many puzzles he sent into the world, few have stayed as alive as this 6×6 board built for one single job: freeing a red car from a jam.
What this one board's history teaches is that simplicity and difficulty are not opposites. A single constraint — pick one direction and slide — was enough to make a board large enough to occupy mathematicians for decades.
An impression of one vehicle passing through the exit (illustration, AI-generated)
Reactions (no login)
Anonymous • one of each per visitor per day
Part of these series
Puzzle Incident HistoryEpisode 44 of 47
