Rush Hour (board game)
Rush Hour is a sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. It is now being manufactured by ThinkFun (formerly Binary Arts).
ThinkFun now sells Rush Hour spin-offs Rush Hour Jr., Safari Rush Hour, Railroad Rush Hour, and Rush Hour Brain Fitness, with puzzles by Scott Kim. An iOS version of the game has been released in 2010 with both free and paid versions (the latter with more puzzles and features).
Game
The regular version comes with 40 puzzles split up into 4 different difficulties, ranging from Beginner to Expert. The deluxe edition has a black playing board, 60 new puzzles and has an extra difficulty, the Grand Master, which is harder than Expert. Puzzles falling in this difficulty range can only be sold with expansion packs of the original game. The regular version includes a travel bag. Extra puzzle card packs (in addition to the 40 or 60 cards included with the game) are also available. The deluxe edition also comes with shiny cars. In 2011, the board was changed to black like the deluxe edition; the cards was changed to new levels and to match the board change too.
Description
The board is a 6x6 grid with grooves in the tiles to allow cars to slide, and an exit hole which according to the puzzle cards, only the red car can escape. The game comes with 12 cars and 4 trucks, each colored differently. The cars take up 2 squares each; and the trucks take up 3.
Each puzzle card shows which colored cars get placed on the board and also where they should be placed.
Each card has a different level number. The higher the level number, the more difficult the puzzle.
Cars and trucks can only be moved within a straight line along the grid. They cannot be rotated.
Objective
The goal of the game is to get the red car out of a six-by-six grid full of automobiles 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 which makes the puzzle harder.
Expansions
Three expansions were released, card set 2 which comes with a new escape car, card set 3 which comes with a white limo and card set 4 which comes with a taxi. The car sets come with 40 new challenges each, 10 intermediate, 10 advanced, 10 expert and 10 grandmaster challenges which can only be bought with the expansion sets. The expansions work with both the regular version and the deluxe edition.
Computational Complexity
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.[1] This is proved by reducing a graph game called Nondeterministic Constraint Logic, which is known to be PSPACE-complete, to generalized Rush Hour positions.
Tromp and Cilibrasi (2004)[2] 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.
See also
References
- ↑ Gary Flake and Eric Baum. "Rush Hour is PSPACE-complete, or why you should generously tip parking lot attendants".
- ↑ John Tromp and Rudy Cilibrasi. "Limits of Rush Hour Logic Complexity" (PDF).