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 computations^{1}, 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 *M _{ij}* = 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, *M*_{init}, to that of a finished position, *M*_{final}, 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 *M*_{init} or *M*_{final} 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.}

on January 10, 2008 at 2:29 am |Tim McKenzieI’m not convinced by your characterization of PSPACE-complete problems.

First, PSPACE-complete problems are in PSPACE, which means they’re solvable. If you can determine whether a specific instance of Rush Hour is solvable (which you can), then you can do it in finite time, although the time required may grow incredibly fast as the size of the problem increases.

Second, the excessive time that is (probably) required to solve PSPACE-complete problems comes only as a result of restricting yourself to an amount of memory that grows only polynomially. If you allow yourself unlimited memory, then you may be able to solve the problem faster. You still won’t be able to solve it in polynomial time, though, since it will take more than polynomial time to write to memory the excessive quantities of data that you need to refer back to.

Here’s a sample way to determine whether a given nxn Rush Hour problem is solvable:

Consider all the trucks and cars, and create a node for each possible way of placing the cars and trucks on the board so that they’re in the same line as where they started. (That is, create a node for each position that you could possibly reach if the cars and trucks were allowed to move under each other.) There are finitely many such nodes. If you like, you can reduce the number of these nodes by excluding the ones where the cars and trucks have ended up overlapping, and the ones where cars and trucks have moved past other ones that are facing the same way.

Then, starting from the node that corresponds to your actual starting position, mark that node, so you know you’ve visited it, and move on to consider every node that you can reach from that node in a single legal move. If any of those nodes is a solution, then congratulations, you’ve won!

Otherwise, mark all of those nodes, so you know you’ve visited them, and move on to consider all the unmarked nodes that you can reach in one legal move from one of the nodes that you’re currently considering. Check if any of those is a solution, mark them, move on again, and so on.

If you find a solution, then obviously, the original problem was solvable. However, if you find that you can’t reach any unmarked nodes in one legal move from the set of nodes that you’re currently considering, then the Rush Hour problem you were given can’t have been solvable, since you’ve considered every position that can possibly be reached from the starting position.

One of these two outcomes (finding a solution or getting stuck) must eventuate in finite time, since there’s a finite number of nodes, and you’re visiting at least one new one at each step, until you get stuck or win.

I’ve described a fairly generalized breadth-first search, but there are probably some optimizations that you can make, if you’re inclined to do so.

Of course, your post was really (well, partly) about complexity, and I’ve said nothing about the complexity of my solution yet. Let’s see; in an n x n grid, there are O(n^2) squares, and all the cars and trucks take either 2 or 3 squares, so there can be O(n^2) of these. If we let them move under each other, then each car or truck can move along its whole line, so it has O(n) possible positions. All the combinations of cars and trucks in all their conceivable positions gives us O(n^(k * n^2)) nodes, if we don’t weed any out. Now we’re past polynomial space.

Of course, you don’t actually need to create all the nodes at the beginning; you only need to create the nodes that you visit, as you visit them, but you need to be able to check a certain position, to see if you’ve visited (i.e. created) its node, which could take quite some time when you’ve created a lot of nodes.

on February 25, 2008 at 2:32 am |CuspMy son had one as a toy when he was 4.

http://www.puzzles.com/products/rushhour.htm