Michael Fogleman

ProjectsArtworkAboutResumeMore

Solving Rush Hour, the Puzzle July 2018

How I created a database of all interesting Rush Hour configurations.

Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996.

I played a clone of this game on my first iPhone several years ago. Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles.

After writing a solver, I wrote a puzzle generator that would create more starting positions for us to try (the game comes with 40 levels printed on playing cards). The generator used simulated annealing to try to maximize the number of moves required to solve the puzzle.

Unsatisfied with the results, I then decided to try generating all possible puzzles. Ultimately I ended up with a complete database of every "interesting" starting position. It was quite challenging (and exciting!) and that's what I want to talk about in this article. My code is open source with a permissive license and the resulting database is available for download.

Rush Hour (Regular Edition)

Table of Contents

Terminology

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:

Combinatorial Explosion

Rush Hour is a perfect example of combinatorial explosion.

Board Size

Time to Solve*

Interesting Puzzles

Number of States

Number of States (One Wall)

4x4

0.01s

32

9,303

43,927

5x5

6.2s

1,730

6,795,363

51,444,144

6x6

3h10m

476,118

27,103,652,325

287,592,039,683

7x7

???

???

???

???

So, writing efficient code and using clever algorithms will be important but will only get us so far. I think solving the 7x7 case may be doable but would require extensive computing resources that I can't afford! (It would probably require decades of CPU time.) Even adding walls increases complexity significantly, so I have only solved the case of zero or one walls. Note that while there are tens of billions of possible states, there are only about half a million puzzles that meet our criteria of interesting-ness.

* times are from an iMac with a 3.4 GHz Intel Core i5 (4 cores)

Bitboards

My code uses bitboards heavily. These are commonly used in chess engines and for other board games. In the case of Rush Hour, the bitboards represent which squares are occupied by pieces. The code also maintains a bitboard for just horizontal pieces and a bitboard for just vertical pieces. There are 6x6 = 36 squares, so a 64-bit unsigned integer is used for the bitboards.

The following diagram shows which bits map to which squares.

00 01 02 03 04 05
06 07 08 09 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35

The following diagram shows the bitboards for a sample board.

All Horz Vert GBB.L. 111010 011000 100010 GHI.LM 111011 000000 111011 GHIAAM => 111111 = 000110 | 111001 CCCK.M 111101 111000 000101 ..JKDD 001111 000011 001100 EEJFF. 111110 110110 001000

Solving a 51-move Puzzle

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

[]

[2]

[2, 2]

[2, 3]

[3]

[3, 2]

......

AA....
.AA...
..AA..
...AA.
....AA

AABB..
AA.BB.
AA..BB
.AABB.
.AA.BB
..AABB

AABBB.
AA.BBB
.AABBB

AAA...
.AAA..
..AAA.
...AAA

AAABB.
AAA.BB
.AAABB

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:

bool operator<(const Board &b1, const Board &b2) {
    if (b1.HorzMask() == b2.HorzMask()) {
        return b1.VertMask() < b2.VertMask();
    }
    return b1.HorzMask() < b2.HorzMask();
}

Simply comparing the All masks would not work, because two different states in the same cluster could have the same value.

So now, when evaluating a new cluster as a potential database entry, we can immediately exit early if we find that the initial state was not less than every other reachable state in the cluster. We trade in a small bit of processing time for a huge relief in memory consumption and inter-thread communication.

But there's more! We can make the enumerator smarter such that it usually produces canonical states that won't fail this check. If any piece can move up or to the left, then we know that some reachable state is less than the current state. Bitboards are put to good use here. As the enumerator is building up candidate states, it maintains a bitboard indicating squares that must be occupied to prevent any pieces from moving up or left. These are the squares immediately above vertical pieces and immediately to the left of horizontal pieces. Here's an example to demonstrate how just a few bitboard operations can identify if any pieces can move up or left. The standalone formula is: (((Horz >> 1) & ~RightColumn) | (Vert >> 6)) & ~All

H>>1&~RC V>>6 ~All GBB.L. 110000 111011 000101 000001 GHI.LM 000000 111001 000100 000000 GHIAAM => 001100 | 000101 & 000000 = 000000 CCCK.M 110000 001100 000010 000000 ..JKDD 000110 001000 110000 000000 EEJFF. 101100 000000 000001 000000

Shifting the horizontal mask by 1 emulates moving horizontal pieces to the left, but we must clear out the rightmost column due to the bits wrapping around. Shifting the vertical mask by the board width (6) emulates moving vertical pieces up. In this case we don't need to worry about wrapping. Finally, the & ~All operation removes bits that will be prevented from moving due to obstacles.

The result in this example is nonzero, so some piece is able to move up or left. (We can see that the M piece can move up.) This board is not canonical and can be skipped. (We'll visit this cluster when the enumerator produces the canonical form.)

Thanks to this technique, the code uses very little memory and doesn't need to maintain a huge lookup table of already-seen positions. In the 6x6 case, the enumerator produces perfectly "canonical" states 33% of the time. Without this trick it would be less than 1%.

Visualizing Clusters

Clusters are just directed graphs where each node is a puzzle state and each edge is a valid move. (Actually, all moves are reversible, so it could be considered an undirected graph as well.) So we can render them using Graphviz. Here are some examples (click to enlarge).

In these graphs, unsolved states are red, goal states are green, and an optimal shortest path is shown in blue. All other nodes are yellow. We can see that different clusters have different "shapes" and there are often bottleneck points. Perhaps this could somehow be used to estimate the difficulty of the puzzles?

Cluster Analysis

For each state produced by the enumerator, we want to analyze its cluster to figure out what we ultimately care about:

  • Is this cluster solvable? That is, are any reachable states goal states? If not, we can abort early.
  • Which state(s) are furthest from a goal state? That is, which states are most "unsolved"? How many moves are required to solve that state?
  • Is the unsolved puzzle minimal? That is, are all of the pieces important? If removing any piece has no effect on the solution, then the puzzle is not minimal and is discarded.
  • Bonus: how far from a goal state are all of the intermediate states? That is, what does the histogram look like with X being # of moves left and Y being # of states within the cluster. Stated yet another way, how many nodes appear on each rank in the Graphviz visualizations?

This part of the code is actually pretty simple. See cluster.cpp if you're interested!

The largest cluster, by far. This puzzle has 541,934 reachable states. No 3-pieces and lots of space to move around. Only requires 15 moves to solve.

Go vs. C++

All of my code was initially written in Go. But when I started trying to "solve" the entire game I decided to use C++ to get the most performance possible.

I made a lot of improvements along the way in porting my code to C++, so I don't have a direct apples-to-apples comparison between Go and C++ for the full program. But I did run benchmarks on several sub-problems, such as repeatedly solving the same puzzle. In most of these benchmarks C++ came out about 2x faster than Go.

Special thanks to Matt Godbolt (of Compiler Explorer fame) for giving me some C++ performance tips!

The Cloud

Solving the 6x6 case with no walls took 3h10m on my iMac. But for the case with one wall, I used an EC2 instance with 72 cores (3.0 GHz Intel Xeon Scalable) to crank through it faster. It took 14.5 hours to complete and cost me about $45, but I have since made several performance improvements and it would probably take about 6 hours now. But it sure was fun!

htop on EC2

Hardest Puzzles

Quantifying the difficulty of Rush Hour puzzles is... difficult... so normally when I say "hardest" I mean "requiring the most moves." I now present to you the hardest 6x6 puzzle and the hardest 6x6 puzzle with one wall.

Hardest 6x6 Puzzle, Requiring 51 Moves
(click for solution)

Hardest 6x6 Puzzle with One Wall, Requiring 60 Moves
(click for solution)

Top 12

Click on one to play it in the browser!

60 moves, 2332 states

55 moves, 8257 states

54 moves, 1845 states

53 moves, 4228 states

52 moves, 5717 states

51 moves, 4780 states

50 moves, 14385 states

50 moves, 4643 states

50 moves, 3169 states

50 moves, 2966 states

50 moves, 1845 states

50 moves, 1066 states

Analyzing the Results

It is interesting to look at the cluster statistics in aggregate. The most common number of moves in the database is 11 and hard puzzles are rare. We see a very nice normal distribution when plotting log(cluster size). I didn't dive in too deeply here, so there might be more worth exploring.

Database Format

The database is a simple text file with just a few columns. There is one row for every valid (solvable, minimal) cluster. The columns are: # of moves, board description, and cluster size (# of reachable states).

60 IBBx..I..LDDJAAL..J.KEEMFFK..MGGHHHM 2332
55 ..BBMxDDDKM.AAJK.N..JEENIFFL..IGGLHH 8257
54 BBBKCCDD.K.LIAAK.LI.JEEMFFJ..M..x.HH 1845
53 ..BB.xDDDK..AAJK.M..JEEMIFFL..IGGLHH 4228
52 .xCCMNDDDKMNAAJK....JLEEIFFL..IGGHH. 5717
51 GBB.L.GHI.LMGHIAAMCCCK.M..JKDDEEJFF. 4780
50 BBI..MGHI.LMGHAALNGCCK.N..JKDD..JEEx 14385
50 BBBJCCH..J.KHAAJ.K..IDDLEEI..L..x.GG 1066
50 ..xCCLDD.K.LIAAK..I.JKEEFFJ..MGGGHHM 1845
50 ..IBBB..IK..AAJK.LCCJDDLGHEE.LGHFF.. 4643

The board description is a 36-character string representing the state of the unsolved board. It is a 6x6 2D array in row-major order. The characters in the description follow these simple rules:

Database Download

The database contains every "interesting" 6x6 Rush Hour puzzle with zero or one walls. There are 1,585,616 puzzles in the database, covering 6,529,634,986 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.

Try It Yourself

The code is on GitHub at https://github.com/fogleman/rush.

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!