Rush Hour is a logic puzzle based on sliding blocks with the goal of moving one of the blocks across the board. In this project, I model Rush Hour with graphs where each vertex represents a state of the board and an edge is drawn between two vertices if the rules allow you to make a single move from one state to the other. Though there is a much larger space of these graphs (there are a huge number of vertices that will be unreachable from a given starting vertex), we can still study the graphs starting with the 40 standard boards and try to see what aspects of certain starting configurations make some boards harder than others. Some configurations are harder because it takes more moves to reach a solution. However, that is not universally the case (that is, there are some boards that take fewer moves to solve but are still harder). The goal was to see if the topology and overarching structure of these graphs tells us about the ease of solving for a human.
The graph shown here was generated from board #2, one of the easiest. Among the standard boards, that board is particularly interesting (along with board #14) because it has a large number of vertices and complicated topology. In board #1, it seems like moves are similar to moves on a sphere. In other boards, moves might be similar to moves on a torus. In board #2, moves are similar to moves on a much more topologically complicated surface.