Table of Contents

Terminology

• Piece: a vehicle on the puzzle board. Each piece has a position, a size, and an orientation (horizontal or vertical). In Rush Hour there are 2-pieces (cars) and 3-pieces (trucks).
• Primary Piece: the "red car" in the puzzle, the piece that must reach the exit on the right side of the board.
• Step: moving a piece by one unit.
• Move: moving a piece by N steps at once.
• Goal State: any state where the primary piece is on the target square (all the way to the right). Note that there's no need to model the primary piece actually exiting the board.
• Unsolved: a state that is further from a goal state than any other reachable state. The puzzle cannot be made any harder by moving the pieces around. Note that this does not mean unsolvable!
• Minimal: a state where each piece is important. No piece can be removed without altering the solution.
• Hardest: requiring the most moves to solve.
• Cluster: a set of puzzle states that are all reachable from one another - a connected graph of all reachable states.
• Wall: a fixed (unmovable), single-cell obstacle. Not part of the original Rush Hour game, but included in some clones and in my code.

Prior Art

I didn't do a whole lot of research or anything, but did find these papers:

The first one was rather academic and not particularly helpful. It seemed they were more interested in taking an unusual approach rather than just solving the problem. Also it was optimizing number of "steps" (versus "moves" - steps being unit moves) which seemed an unnatural way of thinking about it to me. The second was more interesting and gave me some ideas. But no where did I find any sort of complete database, just a handful of the hardest configurations and a few charts. The second paper mentioned that it took on the order of 100 hours for their code to run. My code takes about 3 hours.

Interesting Puzzles

So, what do I mean by "interesting"? I established a set of rules to filter out a lot of nonsense puzzles. Interesting puzzles follow these rules:

• No row may be completely filled with horizontal pieces and no column may be completely filled with vertical pieces. These just form walls of pieces that can never move. Not very interesting.
• No horizontal piece may appear on the primary row except for the primary piece itself. That would allow other cars to exit the board too. However, walls may be present to the left of the primary piece.
• There should only be one database entry per cluster - no two entries in the database should be reachable from one another.
• Database entries should be fully "unsolved" - they cannot be made any harder by moving pieces around.
• Database entries should be "minimal" - each piece in the puzzle is important. Removing any piece will alter the solution. (This rule drastically reduces the size of the database but adds some processing time.)
• The database should be complete - any cluster that satisfies the above rules should be included.

Combinatorial Explosion

Bitboards

Enumerating States

To examine all possible puzzles, we need an efficient way to enumerate all possible piece placements based on our rules. Let's break it down by looking at individual rows and columns first. For the 6x6 puzzle with 2-pieces and 3-pieces, the following table shows all of the possible ways that horizontal pieces may appear on a row (or vertical pieces on a column).

The primary row (the row with the red car) is special and is limited to the [2] set.

We can choose any of these placements for every row. But then when we begin choosing placements for the columns, we must check that we aren't making vertical pieces overlap the horizontal pieces. In my implementation, I use bitboards that are progressively updated as piece assignments are made to check for these collisions efficiently. As soon as a collision is identified, that subtree no longer needs to be considered.

Lexicographical Ordering

The enumeration scheme above will produce billions of states that we can then evaluate. But we only need to evaluate each distinct cluster (connected graph of mutually reachable states) once. We really only need the enumerator to give us one state per cluster, and then we can find the other reachable states during further evaluation.

In theory, we could maintain a giant set of seen positions to avoid duplicating work. But given the size of the search space I considered this a bad approach.

So I created the notion of having a single "canonical" state for each cluster. The canonical state is the one that compares less than every other reachable state. Less than, you may ask? Recall that the Board class maintains three bitboards, respectively indicating the presence of 1) all pieces, 2) horizontal pieces, and 3) vertical pieces. With these, defining the less-than operator is simple:

I used lowercase o instead of periods . for the empty cells in the database so that the entire board description can be selected with a double-click. My code can parse either format.

Database Download

The database contains every "interesting" 6x6 Rush Hour puzzle with up to two walls. There are 2,577,412 puzzles in the database, covering 9,698,093,879 reachable states. Walls are lowercase x so you can easily grep them in or out as desired.

Utilities

My code includes several utility binaries written in Go for solving puzzles, rendering puzzles, etc.

To render a board:

$ go run cmd/render/main.go GBB.L.GHI.LMGHIAAMCCCK.M..JKDDEEJFF. out.png

To create a .dot file for Graphviz and then render it:

$ go run cmd/graph/main.go ..xCCLDD.K.LIAAK..I.JKEEFFJ..MGGGHHM > graph.dot
$ dot -Tpng graph.dot > graph.png

To solve a puzzle:

$ go run cmd/solve/main.go GBB.L.GHI.LMGHIAAMCCCK.M..JKDDEEJFF.
{true [F+1 K+1 M-1 C+3 H+2 J-1 E+1 G+3 B-1 I-1 A-3 I+1 L+1 B+3 I-1 A+2 G-3 E-1
H-3 A-1 J+1 C-3 M+1 B+1 K-4 A+1 C+2 D-1 F-1 H+3 A-1 K+1 B-1 M-1 C+1 J-1 E+1 G+3
A-1 I+1 B-3 I-1 A+1 G-1 E-1 J+1 C-1 K-1 L-1 M+3 A+3] 51 81 51 2756 229984}

Negative moves are up or left, positive moves are down or right.

Online Play

Try It Yourself

Top 23

The top 23 puzzles in the database require 50 or more moves to solve. Here they are.

Click on one to play it in your browser!

Conclusion

I believe that the techniques described in this article advance the current "state of the art" for solving the game of Rush Hour. Prove me wrong and I'll be thrilled!

Let me know if you do anything interesting with the code or the database!