Rush Hour (the sliding-car puzzle)

The Japanese puzzle inventor Nob Yoshigahara (1936–2004) designed the sliding-car puzzle in the 1970s. The version most people know was sold in the United States from 1996 by Binary Arts, now ThinkFun.

One thing to hold: A 6 × 6 tray of cars and trucks that slide only along their own lane.

Why it matters: In 2002 two researchers proved that, on boards of any size, deciding whether a jam can be cleared is among the hardest kind of problem a computer can face (“PSPACE-complete”).

Sources: Wikipedia, “Rush Hour (puzzle)” and “Nob Yoshigahara” · G. W. Flake and E. B. Baum, “Rush Hour is PSPACE-complete”, Theoretical Computer Science 270 (2002)