Rush Hour (puzzle)

Last updated
The Rush Hour puzzle set Rush Hour sliding block puzzle.jpg
The Rush Hour puzzle set

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).

Contents

ThinkFun now sells Rush Hour spin-offs Rush Hour Jr., Safari Rush Hour, Railroad Rush Hour, Rush Hour Brain Fitness and Rush Hour Shift, with puzzles by Scott Kim. The game sold more than 1 million units. [1]

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 and trucks are used in all challenges.

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 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. [2] 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. [3]

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

Minimal solution of the hardest initial Rush Hour configuration. Rush Hour solution - hardest configuration.gif
Minimal solution of the hardest initial Rush Hour configuration.

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. [4] 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 [5] 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 has been shown to take 93 steps. A shortest solution can be seen on the right. [6] If you count the necessary moves instead of the steps, the most difficult start configuration in this sense requires 51 moves. [7]

See also

Related Research Articles

<i>Monopoly</i> (game) Property trading board game

Monopoly is a multi-player economics-themed board game. In the game, players roll two dice to move around the game board, buying and trading properties and developing them with houses and hotels. Players collect rent from their opponents and aim to drive them into bankruptcy. Money can also be gained or lost through Chance and Community Chest cards and tax squares. Players receive a salary every time they pass "Go" and can end up in jail, from which they cannot move until they have met one of three conditions. House rules, hundreds of different editions, many spin-offs, and related media exist. Monopoly has become a part of international popular culture, having been licensed locally in more than 103 countries and printed in more than 37 languages. As of 2015, it was estimated that the game had sold 275 million copies worldwide. The original game was based on locations in Atlantic City, New Jersey, United States.

<span class="mw-page-title-main">Sokoban</span> 1981 video game

Sokoban is a puzzle video game in which the player pushes boxes around in a warehouse, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

<i>Car Wars</i> Tabletop combat simulation game

Car Wars is a vehicle combat simulation game developed by Steve Jackson Games. It was first published in 1980. Players control armed vehicles in a post-apocalyptic future.

<i>Pit</i> (game)

Pit is a fast-paced card game for three to eight players, designed to simulate open outcry bidding for commodities. The game first went on sale in 1904 by the American games company Parker Brothers, having been developed by the clairvoyant Edgar Cayce.

<i>Sorry!</i> (game) Board game

Sorry! is a board game that is based on the ancient Indian cross and circle game Pachisi. Players move their three or four pieces around the board, attempting to get all of their pieces "home" before any other player. Originally manufactured by W.H. Storey & Co in England and now by Hasbro, Sorry! is marketed for two to four players, ages 6 and up. The game title comes from the many ways in which a player can negate the progress of another, while issuing an apologetic "Sorry!"

Concentration is an American television game show based on the children's memory game of the same name. It was created by Jack Barry and Dan Enright. The show featured contestants matching prizes represented by spaces on a game board, which would then reveal portions of a rebus puzzle underneath for the contestants to solve.

<span class="mw-page-title-main">Board (bridge)</span> Item holding a deal of bridge

In duplicate bridge, a board is an item of equipment that holds one deal, or one deck of 52 cards distributed in four hands of 13 cards each. The design permits the entire deal of four hands to be passed, carried or stacked securely with the cards hidden from view in four pockets. This is required for in-person duplicate bridge tournaments, where the same deal is played several times and so the composition of each hand must be preserved during and after each play of each deal. When bridge is played online, the functions of the physical boards are replaced by the software.

Zombies!!! is a tile-based strategy board game for two to six players. Zombies!!! won the 2001 Origins Award for Best Graphic Presentation of a Board Game, and Zombies!!! 3: Mall Walkers won 2003's Origins Award for Best Board Game Expansion.

<span class="mw-page-title-main">Poker squares</span> Patience game

Poker Squares is a patience game with the objective of building the best poker hands using just 25 cards from the deck. It rewards both lucky guessing and accurate calculation of odds.

<span class="mw-page-title-main">Sliding puzzle</span> Puzzle game involving sliding pieces to achieve certain configurations

A sliding puzzle, sliding block puzzle, or sliding tile puzzle is a combination puzzle that challenges a player to slide pieces along certain routes to establish a certain end-configuration. The pieces to be moved may consist of simple shapes, or they may be imprinted with colours, patterns, sections of a larger picture, numbers, or letters.

<span class="mw-page-title-main">Careers (board game)</span>

Careers is a board game first manufactured by Parker Brothers in 1955 for $2.97 US; it was most recently produced by Winning Moves Games. It was devised by the sociologist James Cooke Brown. Victory conditions consist of a minimum amount of fame, happiness and money that the player must gain. Players set their own victory conditions before the game begins, the total of which must be sixty or one hundred.

Buccaneer was a board game published in Britain by Waddingtons between the 1930s and 1980s.

The following outline is provided as an overview of and topical guide to games and gaming:

<span class="mw-page-title-main">Go and mathematics</span> Calculations of the game complexity of go

The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

<span class="mw-page-title-main">Mahjong solitaire</span> 1981 video game

Mahjong solitaire is a single-player matching game that uses a set of mahjong tiles rather than cards. It is more commonly played on a computer than as a physical tabletop game.

<i>San Francisco Rush: Extreme Racing</i> 1996 video game

San Francisco Rush: Extreme Racing is a video game developed and published by Atari Games. This game was first released in arcades in 1996 and was ported to Nintendo 64 in 1997 and the PlayStation in 1998. San Francisco Rush: Extreme Racing is the first game in the Rush series.

<span class="mw-page-title-main">The Lord of the Rings: The Card Game</span> 2011 fantasy strategy card game

The Lord of the Rings: The Card Game is a non-collectible customizable card game produced by Fantasy Flight Games. As part of the Living Card Game (LCG) genre, it is a cooperative and strategic card game set in Middle-earth, a fantasy world featured in literary works by J. R. R. Tolkien, including The Hobbit and The Lord of the Rings. Its digital adaptation, titled The Lord of the Rings: Adventure Card Game, is published by Asmodee Digital for cross-platform play on Microsoft Windows, macOS, PlayStation 4, Xbox One and Nintendo Switch, being the "first ever digital LCG".

In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. The constraint logic problem and its variants have been proven to be PSPACE-complete to determine whether there exists a sequence of moves that reverses a specified edge and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete.

References

  1. ↑ Jones, Jennifer (July 30, 1999). "Company toys with Web". Washington Business Journal . Archived from the original on May 5, 2003. Retrieved October 6, 2023.
  2. ↑ "Official Rush Hour Deluxe Edition Page". ThinkFun. Retrieved 2019-09-24.
  3. ↑ "Official Rush Hour Page Archive". 2011-07-09. Archived from the original on 2011-07-09. Retrieved 2019-09-24.
  4. ↑ Gary Flake and Eric Baum (2002). "Rush Hour is PSPACE-complete, or why you should generously tip parking lot attendants". Theoretical Computer Science. 270 (1–2): 895–911. doi:10.1016/S0304-3975(01)00173-6.
  5. ↑ John Tromp; Rudy Cilibrasi (2005). "Limits of Rush Hour Logic Complexity". arXiv: cs/0502068 .
  6. ↑ Collette, Sébastien; Raskin, Jean-françois; Servais, Frédéric (May 2006). "On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game". Computers and Games. Lecture Notes in Computer Science. Vol. 4630. Turin, Italy. pp. 220–233. CiteSeerX   10.1.1.91.3487 . doi:10.1007/978-3-540-75538-8_20. ISBN   978-3-540-75537-1.{{cite book}}: CS1 maint: location missing publisher (link)
  7. ↑ Michael Fogleman (July 2018). "Solving Rush Hour, the Puzzle". How I created a database of all interesting Rush Hour configurations.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.