2026-09-23 · history
Rush Hour (1996) — The Year a Wooden Traffic Jam Earned a PSPACE-Complete Proof
Released in the US in 1996, the wooden sliding-block puzzle Rush Hour starts from one simple goal: slide a red car out of gridlock. In 2002 it was proven PSPACE-complete, and a quarter-century later it is still the subject of computer-science papers. This traces the history of the single board its inventor, Nob Yoshigahara, left behind.
