During the recent holiday period, I was introduced to a puzzle game called ‘Rush Hour’. It’s very simple: a 6-by-6 grid is populated along rows and columns with cars and trucks; the player must manoeuvre a car to the exit by sliding the other vehicles out of the way, moving everything only either forward or backward. The reader should attempt a few configurations from this online implementation by Fred Vonk (hat-tip to a nonetheless thin-on-content Wikipedia article) before reading further.

Offline, AF Heavens has suggested that the beginner levels are very straight-forward but that they increase sharply in difficulty after that; I have been unable so far to solve some the intermediate ones, and all but one of the advanced puzzles, so I am inclined to agree with him. But of course, after attempting five or so puzzles, one immediately tires of specific configurations and starts trying to solve the general problem.

Unfortunately, it turns out to be difficult. There is one article in the literature I’ve found: a paper by Gary Flake and Eric Baum, who address the problem of how hard it is to decide whether an initial configuration of ‘Generalised Rush Hour’, on an n-by-n board, has a solution or not. That question is solvable only though an unlimited sequence of computations1, a result they find surprising given the puzzle’s apparent simplicity.

I find this alternately interesting and frustrating. Perhaps because I would like to address a question that doesn’t require me to learn entire new fields—though complexity theory is of course a fascinating subject—studying the 6-by-6 game seems more attractive. Can it really be that even on a 6-by-6 grid, one can’t decide whether an arbitrary configuration is solvable in finite time? What about finding the solution to puzzles—like those in the online version—where we know that one exists? It is this last question that interests me the most.

I will therefore blunder on, pretending I do not know about the result on the generalised Rush Hour board. Solving a puzzle with software like Matlab or Excel requires a language interface to translate the problem in an array; the fact that the game is on a grid to begin with makes it pretty easy: we require only a concept of grid cells being ‘linked’ (if the same vehicle lies over them) or not. To be crude, this can be done with a 36-by-36 binary matrix M where Mij = 1 if squares i and j of the Rush Hour grid are covered by the same vehicle, and 0 otherwise. This is inefficient because some elements of M must always be zero regardless of the configuration, as the vehicles can only be placed horizontally or vertically. Also it doesn’t mark cells that are empty, rather than unlinked, though a moment’s thought will convince you that this information is present implicitly: because all vehicles extend across cells, a cell that is not linked to any other is empty.

With an encoding for the configuration now in place, we ask what we would like to achieve. A Rush Hour game is solved when the path of the red car to the exit is clear. What would this look like in the matrix M? It would mean that the cells corresponding to the path between the red car and the exit are empty, i.e. not linked to another cell. Because the red car can move along its row, this is a little trickier than one might like, because the cells behind the red car can be blocked even if the path to the exit is clear. Nevertheless, it seems straight-forward to see what effect this property of the final configuration will have on M.

The problem is now reduced to that of transforming the matrix of the initial position, Minit, to that of a finished position, Mfinal, using only a set of allowed operations. What are these operations? Shifting vehicles forward and backward on the Rush Hour grid has the effect of linking and unlinking cells in a well-defined way. If a vehicle two cells in size is moved from the right of the top row to other end, cells (1,1) and (1,2) become linked and cells (1,5) and (1,6) become unlinked, so M(1,2) goes from zero to one and M(5,6) goes from one to zero. In general, this vehicle moves from (i,{j,k}) to (i,{m,n}) if moving horizontally and from ({i,j},k) to ({m,n},k) if moving vertically. In the former case, M(6(i-1)+j,6(i-1),k) becomes zero and M(6(i-1)+m,6(i-1)+n) becomes one; the latter is similar but of course in the other index.

‘All’ that remains is to construct an algorithm to move from Minit or Mfinal using only the allowed operations. I will not be solving this today, though if you would like to leave me hints in the comments, don’t stop yourself on account of lessening my enjoyment. What would ultimately be required to solve a Rush Hour board using, e.g. Matlab, would be: i) a function to convert a set of vehicle positions to a linking matrix M; ii) a function corresponding to an operation, where the input would be the start and end coordinates of the vehicle that is moved; iii) an algorithm, much like Gaussian row reduction—only, you know, significantly harder—that transmogrifies the input configuration linking matrix to one for an acceptable output configuration—that is, which satisfies the condition of a clear path from the red car to the exit. The rest is minutiae.

1. Though the memory required to do this is finite, and increases polynomially in the size of the board: problems like these are called PSPACE, to be contrasted with the more well-known P and NP problems, which require only finite numbers of computations.