HTTPS SSH

Rush Hour

A command-line solver for the Rush Hour game.

The Game

Rush Hour is a tiny sliding board game played on a board of 6x6 squares. The objective in the game is to free the red car from the surrounding traffic by sliding the cars out of the way onto free squares until the red car can drive out of the exit on the right side of the board. Note that cars can only go forward of reverse, not to the side.

Installing

Requirements:

  • bash
  • python 3
  • git
  • nose (for running unit tests)
  • inotifywait (for running the development script)

Installation:

Usage

Rush Hour boards are provided and output as text files, each character representing one cell in the grid. For example:

....AA
..BBCC
rr..EF
GGHHEF
...IEF
...IJJ

(This example can also be found in the file boards/testcase.board.)

Cell values can be:

  • Upper-case letters, representing regular cars
  • Lower-case 'r', representing the red car (the one that needs to be moved out to the right)
  • Other lower-case letters, representing regular cars
  • The dot character ('.'), representing an empty cell

No two cars should share the same letter, and there must be exactly one 'r' car in the board (otherwise it cannot be solved).

The rushhour program takes the following arguments:

  • - Read input from stdin
  • -debug Print debug information about the internals of the solver algorithm
  • -animate Rather than just printing the sequence of moves and the final board position, display an ASCII art animation of the winning moves.
  • -delay {d} Delay d between moves in -animate mode, in seconds. Default is 0.5. -delay 0.25 displays 4 moves per second.
  • Any non-dashed arguments are considered input filenames.

Example:

> ./rushhour boards/testcase.board -animate -delay 1

Parse the file boards/testcase.board, solve it, and animate the solution at one move per second.

Known Shortcomings

  • For large boards, the algorithm takes quite a while; some optimization would be in order for that use case, e.g. finding ways of reducing the number of candidate moves to investigate, making collision detection more efficient, etc.
  • Boards where multiple cars share the same symbol are not gracefully reported as errors, even though such a situation is invalid and probably leads to incorrect results.
  • Cars with length 1 are not rejected, and default to being aligned in X direction. This is probably not desirable, and such cars should be rejected instead.
  • In some situations, the program dumps raw Python exceptions; catching and handling them more gracefully would be better.
  • Not tested on anything other than x64 Debian 7.