Rush Hour (puzzle)

Game

The board is a 6×6 grid with grooves in the tiles to allow cars to slide, card tray to hold the cards, current active card holder and an exit hole. The game comes with 16 vehicles (12 cars, 4 trucks), each colored differently, and 40 puzzle cards. Cars and trucks are both one square wide, but cars are two squares long and trucks are three squares long. Vehicles can only be moved along a straight line on the grid; rotation is forbidden. Puzzle cards, each with a level number that indicates the difficulty of the challenge, show the starting positions of cars and trucks. Not all cars or trucks are used in each challenge.

Objective

The goal of the game is to get only the red car out through the exit of the board by moving the other vehicles out of its way. However, the cars and trucks (set up before play, according to a puzzle card) obstruct the path of both the red car and each other, which makes the puzzle even more difficult.

Editions

The Regular Edition comes with forty puzzles split into four different difficulties, ranging from Beginner to Expert. The Deluxe Edition has a black playing board, card box in place of the Regular Edition's card tray, and sixty new puzzles with an extra difficulty: the Grand Master. The Ultimate Collector's Edition has a playing board that can hold vehicles not in play and can display the active card in a billboard-like display. The Ultimate Collectors Edition also includes 155 new puzzles (with some of them being from card set three) and a white limo. In 2011, the board was changed to black, like the Deluxe Edition.

An iOS version of the game was released in 2010.

Expansions

Three official expansions, called "add-on packs", were released: Card Set 2, which comes with a red sports car that takes up 2 squares; Card Set 3, which comes with a white limo that takes up 3 squares; and Card Set 4, which comes with a taxi that takes up 2 squares. Each set also comes with 40 new exclusive challenges—from Intermediate to Grand Master—that make use of the new vehicles in place of (or in addition to) the red car. All three of the expansion packs will work with all editions of the game. Also, like the Regular Edition of the game in 2011, the cards of all three expansions were changed to have new levels and design to match the new board color of the Regular Edition.

Computational complexity on larger boards

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

Most difficult configurations

The hardest possible initial configuration in terms of step length has been shown to take 93 steps. A shortest solution can be seen on the right. If one counts the necessary moves instead of steps, the most difficult start configuration requires 51 moves.

References

References

1. Jones, Jennifer. (July 30, 1999). "Company toys with Web".
2. "Official Rush Hour Deluxe Edition Page".
3. (2011-07-09). "Official Rush Hour Page Archive".
4. Gary Flake and Eric Baum. (2002). "Rush Hour is PSPACE-complete, or why you should generously tip parking lot attendants". Theoretical Computer Science.
5. (2005). "Limits of Rush Hour Logic Complexity".
6. (May 2006). "Computers and Games".
7. Michael Fogleman (July 2018). [https://www.michaelfogleman.com/rush/#HardestPuzzles "Solving Rush Hour, the Puzzle"]. How I created a database of all interesting Rush Hour configurations.