Rush hour is a block sliding puzzle where the objective is to rearrange cars in a park to make way for one particular car to get out.  I've installed one implementation of the game on my N900 some time ago and was tempted to do my own, perhaps with a generator. I found it a bit weird that almost all implementations of Rush Hour came with pre-built puzzles and lacked puzzle enumeration functionality (which I think would be really cool).



I coded a little solver and a GUI frontend for the game and ran a number of experiments to generate puzzles. For my lack of knowledge of any alternative method, I've set my tool to search for puzzles by generating and evaluating random configurations. While  computing solutions for Rush Hour puzzles is straight-forward, generating good puzzles is a complex problem. This is because apart from testing for the existence of a solution, the puzzle must satisfy a minimum (steps to solution) criteria. To illustrate this, consider the following state graph for a minimalistic Rush Hour puzzle:


Each randomly generated configuration represents a single state (say state R) on a graph of reachable configurations for the puzzle being evaluated. First, the graph must be traversed in full to locate all solution nodes (if there are any) and then the node which is furthest away from the closest solution node must be determined (node Q in the above example). This node will be the ideal initial configuration for the puzzle because it would maximize the number of steps required to solve the puzzle.

For the original setup of the puzzle; a 6x6 grid with cars occupying 2 or 3 blocks  horizontally/vertically and with the 'special car' being placed horizontally on the 3rd row, one would be surprised to see that some configurations result in graphs with 25k+ states. Traversing such state graphs can be computationally expensive and even tricky to implement programmatically. These challenges make the following an interesting problem for a computer to tackle ...


Me and a couple of colleagues at our research group were considering answering this question by brute forcing all puzzle configurations for the original game setup. However, my colleague was able to determine the number of these configurations through dynamic programming and a simple calculation revealed that it would take us about 124 years to evaluate all of them. Therefore we decided to settle for random search for the time being (any other suggestions would be appreciated).

The analysis of Rush Hour seems to have attracted some research interest with few papers being published on the complexity of the problem (example) and also some hard configurations of the puzzle being listed online (such as this list on the University of Brussels' website).

It would appear that a generally accepted definition of a 'very difficult' Rush Hour puzzle is one that needs 40+ moves to solve. Some configurations (such as the ones published by the University of Brussels) maximize the number of single-step slides (where moving a car by 3 blocks is considered 3 separate moves) but this notation isn't widely acclaimed.

I have dedicated a separate machine at work to carry on with this investigation. It has been running continuously for over a week now and has evaluated over 50 million puzzles. The tool was able to obtain a long list of puzzles that are solvable in 40+ moves (very difficult ones). The hardest puzzle that the tool was able to generate (presented below) requires 50 moves to solve. It would appear that this is the hardest Rush Hour configuration ever obtained.