Programming Puzzle: Rush Hour Traffic Jam

We recently purchased a puzzle game for our son, Rush Hour Traffic Jam, but eventually chewed through the forty included puzzles to solve. I realized the game is simple enough that I could write a Python script to generate and solve more puzzles, so this is that story. I like solving physical problems like this with code since pure algorithms might seem disconnected from the real world, but applying them to something you can get your hands on helps bring them to life.

A picture of the game’s puzzle #1 in initial configuration (left) and solved configuration (right).

A primer on the game mechanics. An ice cream truck is placed on a 6-by-6 grid and has to drive off of the grid for the puzzle to be solved. The ice cream truck is two squares long, and the grid is populated by other vehicles, each two or three squares long. Vehicles can only slide forwards or backwards in the direction they’re pointing, and cannot move diagonally or to the side. Solving the puzzle consists of sliding cars back and forth to clear a way for the ice cream truck to escape.

Plan of Attack

The general approach for my Python script was to use the Monte Carlo method: randomly generate a puzzle, attempt to solve it, and only keep the solvable ones. For search I would use a breadth-first search, which has the advantage of finding the shortest solution, so there won’t be any “dance of the engines” effect where the computer twiddles several different cars back and forth before making progress. I would also use hash memoization to avoid repeatedly examining states.

This strategy is of course a brute force search, so before writing it one should estimate the problem size and be sure it’s not going to just run forever and leave you Entscheidungsproblem’ed. If that happens, you’ll have to upgrade to a more powerful algorithm like A* search, which means you’ll have to devise an admissible heuristic function, and who has time for that when they’re hacking?

For the Rush Hour puzzle, it’s played on a 6-by-6 grid and there’s a max of about eight vehicles on the grid, each of which could move in one or two directions. A branching factor of only 8 would quickly become intractable for BFS: just 10 ply in and you’d be dealing with a billion states. But from playing the physical game my intuition was that usually only three cars could move in any given configuration, and a branching factor of 3 means you can go 15-ply deep and still only be dealing with tens of millions of states. Thus your script can easily be run on a laptop.

Search Algorithm

Writing this kind of tree search involves three pieces of code:

1. Model the game state
2. From a given game state, find all possible next valid game states
3. Write the search algorithm

Many might think that the hardest part is #3 of writing the search algorithm, but that’s actually the easiest. A BFS can be written using the skeleton code below no matter what problem you’re tackling:

def bfs_search(start_state, goal_state):
  queue = [start_state]
  while queue:
    state = queue.pop(0)
    if state == goal_state:
      return True
    queue.extend(get_next_states(state))
  return False

The steps are:

1. Initialize a queue containing just the start state.
2. Dequeue the next state from the front of the queue.
3. Check if that’s the goal and return True if so.
4. Otherwise, get all possible next states and enqueue them at the back of the queue.
5. If the queue is exhausted, all states were examined and the goal was never reached, so return False.

Adding hash memoization can be accomplished with just three more lines of code:

def bfs_search(start_state, goal_state):
  queue = [start_state]
  seen_states = set()
  while queue:
    state = queue.pop(0)
    if state == goal_state:
      return True
    for next_state in get_next_states(state):
      if next_state not in seen_states:
        seen_states.add(next_state)
        queue.append(next_state)
  return False

One problem with this scaffolding code, however, is that it will only tell you whether there is a solution, not what it is. What we want to know is all of the moves we’re supposed to make in order to solve the puzzle. This is the list of all the states in between the start state and the goal state. We can easily add this to our skeleton code by changing the queue from storing states to storing paths, i.e., lists of states:

def bfs_search(start_state, goal_state):
  queue = [[start_state]]
  seen_states = set()
  while queue:
    path = queue.pop(0)
    if path[-1] == goal_state:
      return True
    for next_state in get_next_states(path[-1]):
      if next_state not in seen_states:
        seen_states.add(next_state)
        queue.append(path + [next_state])
return False

Now we initialize the queue with a path containing just the start state. When we dequeue, we dequeue a path and look at the last state (path[-1]) that it was in. When we enqueue, we append the next state onto the existing path, which creates a new array. But this doesn’t deep-copy the inner lists, so we’re not overly wasting memory.

By the way, depth-first search uses the exact same skeleton code as breadth-first search, with the only difference being you don’t pop from the front of the queue with queue.pop(0) but rather from the back of the queue with plain old queue.pop().

Modeling State

Part #1 of modeling state is actually the next hardest part. Whereas writing a BFS is completely prescriptive, now we have to start using our imagination for how we’re going to model the problem. Here I knew I was going to be making many edits to the boards and doing matrix indexing, so I just decided to model the board as a matrix of characters, with a period as my placeholder for an empty space. Cars would be modeled as letters of the alphabet, with 'A' being reserved for the ice cream truck:

N = 6
EMPTY_SPACE = '.'
board = [[EMPTY_SPACE] * N for _ in range(N)]
# Potential board:
#   [
#     ['.', '.', '.', 'B', 'C', 'C'],
#     ['.', '.', '.', 'B', '.', '.'],
#     ['.', 'A', 'A', 'B', '.', '.'],
#     ['E', 'D', 'D', 'D', '.', '.'],
#     ['E', '.', '.', '.', '.', '.'],
#     ['F', 'F', 'G', 'G', '.', '.'],
#   ]

In the real game, the goal state is when the ice cream truck is no longer on the board. To avoid having to model the ice cream truck driving off the board, I simplified and made the goal state: “The state where there is nothing but empty space left between the ice cream truck and the right edge of the board.” I could have also made the goal state where the ice cream truck has actually reached the right edge of the board, but that would mean the solver still had to keep searching more full ply just to advance the ice cream truck those last few steps to victory. In a brute force search where we have no heuristic function, it’s important to avoid those inefficiencies. For the above puzzle, the goal state is reached as soon as the 'BBB' vehicle slides out of the ice cream truck’s way, which finds a solution three ply faster:

#   [
#     ['.', '.', '.', '.', 'C', 'C'],
#     ['.', '.', '.', '.', '.', '.'],
#     ['.', 'A', 'A', '.', '.', '.'],
#     ['D', 'D', 'D', 'B', '.', '.'],
#     ['E', '.', '.', 'B', '.', '.'],
#     ['E', 'F', 'F', 'B', 'G', 'G'],
#   ]

Finding Next Valid States

Step #2 of finding all next possible states from a given state is actually the most intricate part of the programming. My approach was:

1. Iterate through every square on the board and find the next letter, e.g., 'B'.
2. Search all adjacent squares for the same character to find where all the 'B's are.
3. Based on the orientation of the vehicle, find out if it’s possible to slide forward or backwards (or left or right).
4. Calculate the potential board configurations of moving the vehicle one step in either direction, if possible, and add them to the list of possible next states.
5. Record that we’ve dealt with vehicle 'B' in a set and skip all further recurrences of 'B' in this pass of the board.

This part took me the longest to write and debug. I won’t excerpt it here since, unlike the BFS prototype code above, there’s nothing instructive in how I implemented this exact puzzle. Though one thing to call out is a hack I made to the state representation. This part was already getting so complicated I realized I didn’t want to write extra code to determine whether each vehicle was oriented horizontally or vertically. That meant I needed to store the orientation of each vehicle, which I could have done by adding an extra data structure, like a map with keys of vehicle letters and values of booleans for whether that vehicle was oriented horizontally or not:

board = [['.', ..., '.'], ..., ['.', ..., '.']]
vehicles_horizontal = {'A': True, 'B': False, ..., 'G': True} 

But this would require passing an extra variable around (even though it was a constant). Instead I employed the old uppercase–lowercase hack to add an extra dimension of information to my existing board: now uppercase letters meant the vehicle was horizontal while lowercase letters meant the vehicle was vertical. This extra information could be set while initializing the board when each vehicle’s orientation was known, and then it would never need to be calculated again:

# Board with vehicle orientations encoded in the case dimension:
#   [
#     ['.', '.', '.', 'b', 'C', 'C'],
#     ['.', '.', '.', 'b', '.', '.'],
#     ['.', 'A', 'A', 'b', '.', '.'],
#     ['e', 'D', 'D', 'D', '.', '.'],
#     ['e', '.', '.', '.', '.', '.'],
#     ['F', 'F', 'G', 'G', '.', '.'],
#   ]

Results

I had the script add a random number of other cars as obstacles and then search for the solution. As expected, most of these random puzzles are either trivially over-constrained or trivially under-constrained, meaning the solver can verify that the ice cream truck either can or can’t get out in only a few steps. But sometimes it would generate longer puzzles that took more steps to solve. Here is one puzzle that took 15 step to solve, which the script found in a few seconds:

BB__d_   BB____   BB____   BB____   BB____   BB____   BB_g__
____d_   ____d_   ____d_   ____d_   ____d_   ___gd_   ___gd_
_cAAdh   _cAAdh   __AAdh   _AA_dh   _AAgdh   _AAgdh   _AA_dh
fc_g_h   fc_gdh   fc_gdh   fc_gdh   fc_gdh   fc__dh   fc__dh
fc_gII   fc_gII   fc_gII   fc_gII   fc__II   fc__II   fc__II
___EEE   ___EEE   _c_EEE   _c_EEE   _c_EEE   _c_EEE   _c_EEE
BB_g__   BB_g__   BB_g__   BB_g__   BB_g__   BB_g__   BB_g__
___gd_   ___gd_   ___gd_   ___gd_   ___gd_   ___g__   ___g__
__AAdh   _cAAdh   _cAAdh   _cAAd_   _cAAd_   _cAAd_   _cAAd_
fc__dh   fc__dh   fc__dh   fc__dh   fc__dh   fc__dh   fc__dh
fc__II   fc__II   fc_II_   fc_IIh   fcII_h   fcIIdh   fcIIdh
_c_EEE   ___EEE   ___EEE   ___EEE   ___EEE   ___EEE   __EEE_
BB_g__   BB_g__   
___g__   ___g__
_cAAd_   _cAA__
fc__dh   fc__dh
fcIIdh   fcIIdh
_EEE__   _EEEd_

Recreated with the actual game:

Our first procedurally generated puzzle on the physical game board: start state (left) and goal state (right).

Next Steps and Analysis

There are a couple improvements that could be made. First, my early version of the script would run for a while before seeming to deadlock. I originally thought this was because it found a puzzle too hard to solve, but it turned out that the deadlock was in the random puzzle generation step. Apparently it was stuck trying to put another vehicle on a map that was already jammed full. I fixed this by having it abort placing more cars after 1000 random unsuccessful attempts, but there are definitely more artful approaches to generating puzzles.

Second, note how, in the puzzle above, car 'BB' never moves in the course of solving the puzzle, nor does anything ever touch it, meaning it serves no purpose as an obstacle. So it’s completely extraneous and could be removed. This could be done with a post-processing step on the completed puzzle that finds such isolated stationary cars and removes them. Although such cars could function as red herrings that people waste time manipulating and gumming up the actual solution with, so in some cases they might actually make the puzzle more challenging.

I was also interested in collecting some numbers on how complex the problem gets depending on how deeply you search. So I had the algorithm count the number of states it saw at each ply over thousands of random puzzles and got this:

Complexity of the puzzles I’m generating peaks around 6- or 7-ply deep, but after that they become trivially constrained again and the “ply function" collapses as we either find a solution or prove that one does not exist.