(2018) How I created a database of all interesting Rush Hour configurations

Summary

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