Rush Hour (puzzle)

Did You Know?

• The hardest possible initial configuration in terms of step length takes 93 steps.
• If counting necessary moves instead of steps, the most difficult start configuration requires 51 moves.
• ThinkFun now sells Rush Hour spin-offs including Rush Hour Jr., Safari Rush Hour, Railroad Rush Hour, Rush Hour Brain Fitness, and Rush Hour Shift, with puzzles by Scott Kim.

Game

The playing area is a six-by-six grid with grooves that let vehicles slide, plus a tray for puzzle cards, a holder for the active card, and an exit opening. Sixteen vehicles come with the game: twelve cars and four trucks, each in a different color. Cars and trucks are both one square wide, but cars are two squares long while trucks are three squares long. Vehicles can only move straight along the grid; they cannot be rotated. Forty puzzle cards show the starting positions of the vehicles, and each card has a level number indicating its difficulty. Not every vehicle is used in every puzzle. The objective is to slide only the red car out through the exit by moving other vehicles out of its way. The Regular Edition includes forty puzzles divided into four difficulty levels, from Beginner to Expert. The Deluxe Edition features a black playing board, a card box instead of a card tray, and sixty new puzzles with an added difficulty level called Grand Master. The Ultimate Collector’s Edition has a board that can store vehicles not in use and can display the active card like a billboard; it also includes 155 new puzzles and a white limo. In 2011, the board was changed to black, matching the Deluxe Edition. An iOS version came out in 2010. Three official add-on packs were released: Card Set 2, which adds a red sports car that is two squares long; Card Set 3, which adds a white limo that is three squares long; and Card Set 4, which adds a taxi that is two squares long. Each pack includes forty new challenges ranging from Intermediate to Grand Master, using the new vehicles either in place of or alongside the red car. All three expansions work with every edition of the game. In 2011, the cards for all three expansions were updated with new levels and a new design to match the Regular Edition’s new black board.

Computational complexity on larger boards

When generalized to an arbitrarily large board, deciding if a Rush Hour problem has a solution is PSPACE-complete. This was proved by reducing a graph game called nondeterministic constraint logic to generalized Rush Hour positions. In 2005, Tromp and Cilibrasi showed that Rush Hour remains PSPACE-complete when cars are of size 2 only, and conjectured it is still nontrivial when cars are of size 1 only.