Rush Hour Game Graph Analysis

December, 2017

Rush Hour is a logic puzzle board game in which a solitary player slides "cars" around a grid with the goal of driving a particular target car to the exit. The number of legal moves from a given configuration is small, so it is pretty easy to tree out all possible moves and find the graph of reachable configurations.

My copy of the game came with 40 starting configurations of increasing difficulty. In this project, I generated the graphs of reachable configurations from each of those 40 starting configurations, with the goal of measuring whether differences in the topology of the game graphs correlate with the subjective difficulty of the puzzles for humans.

There were some simple correlations, like that the shortest path from the starting configuration to a solved one increased with the difficulty of the puzzles. However, looking at the game graphs, it is clear that the large-scale topology also plays a role. That is, the simplest puzzles have "spherical" game graphs where there is effectively a single path to a solution. In other puzzles, however, there might be several different paths which represent genuinely different solving strategies.

The image below shows a game graph with a lot of large-scale structure:

For more information, you can look at this PDF of my working notebook.