Rush Hour 'Traffic Jam' Solver


This is a C++ program that reads a Rush Hour board from a text file, solves it, and produces a nice PostScript file that shows the shortest solution. So you can cheat when you can't solve the problem yourself. :-)

(Rush Hour Traffic Jam Puzzle is a board game by Binary Arts.)

aaobcc
..ob..
xxo...
deeffp
d..k.p
hh.k.p

It also dumps the solution in the format found on the backside of the game cards.

bd1 cl1 pu3 fr1 ku1
hr4 dd1 el1 od3 kd1
fl1 pd1 cr1 bu1 xr3
ou3 er1 du3 el1 od3
ar1 du1 xl3 ou1 bd1
cl1 pu1 fr1 ku1 hl4
od1 kd1 fl1 pd3 cr1
bu1 xr5
Shortest Rushhour Solution for Level 32
GDL-Output (visualised with aiSee) for the above solution of level 32:

Rushhour / Traffix Jam Solved, Shortest Path Highlighted


The README file

Rush Hour Puzzle Solver

(c) Henrik Theiling

http://www.theiling.de/projects/rushhour.html

This solves Rush Hour boards and saves them as nice PostScript files.

Needed

Compilation

Unpack the tarball archive
tar xzvpf rush_hour-*-src.tar.gz
Switch to the new directory
cd rush_hour-*-src
build the program
./configure --prefix=/usr/local
make

It will materialise as ./rush_hour.

Usage

In the directory where rush_hour was created, and where the file level.txt or level32.txt is found, invoke

./rush_hour 32

It will produce a solution for level 32 and store the result in solution32.ps. You can look at that now:

gv solution32.ps

Or print it:

lpr solution32.ps

Level File Format

For level number X, you can store the level in either the file level|X|.txt or in the generic file level.txt.

Look at level32.txt. It reads:

32:
aaobcc
..ob..
xxo...
deeffp
d..k.p
hh.k.p
-
This is a comment
This is also a comment.

The 32: is the level number. There must be a level number even in the special file named after the level it containts. A level body contains the board setup. The following characters are used:

a,...,klength-2 cars
o,...,rlength-3 cars
x, y, zyour own cars
.empty board cell

After the board cells are defined, there may be an optional comment, starting with line starting with a minus characters. After the optional comment, the board definition is terminated by an empty line.

There may be several boards in one file, each in the format described above.

Currently, the board has a fixed size of 6x6 cells. This can be changed in the source code, but it is untested.

Solving Technique

Brute force breadth first search.

That's generally a complex approach, but it works here since the boards are small.

Enjoy!


Source Code

rush_hour-0.2.9.tar.bz2
rush_hour-0.2.9.tar.bz2.md5

LibError is required for compilation:

liberror-2.1.89882.tgz
liberror-2.1.89882.tgz.md5

Content

Index

August 28th, 2008
Comments? Suggestions? Corrections? You can drop me a line.
zpentrabvagiktu@theiling.de
Schwerpunktpraxis
Datenschutz