Rush Hour

When I get real bored, I like to drive downtown and get a great parking spot, then sit in my car and count how many people ask me if I'm leaving. —Steven Wright

My Life as a NY City Cab Driver: Rush Hour

Rush Hour is children's game that takes all of thirty seconds to learn how to play. The game is played on a 6 x 6 grid that is filled with cars that can slide either up/down or left/right. Once a car is aligned vertically or horizontally, it must always remain aligned in the same manner. The goal of the game is to move the cars around so that one special car (the target car) is free to leave the grid from the one exit on the perimeter. Magically teleporting cars around the grid is obviously illegal. In other words, Rush Hour could be played by insane parking lot attendants with real cars in a real parking lot.

Figure 1 shows a typical example of what an instance of the game could look like. In this case, seven moves are required to change the configuration from Figure 1a to Figure 1b. Even on a 6 x 6 grid, some games may require over forty moves to free the target car.

Finding a solution can be difficult because a complicated and dynamic set of relationships can exist among the cars. For example, car A may be blocked by car B, which may be blocked by car C, which, in turn, can only be unwedged by moving car A. Thus, the dependencies among the cars can be circular and even recursive.

In this column, we are going to consider a slight generalization of Rush Hour, which I'll refer to as GRH for Generalized Rush Hour. The only difference between GRH and Rush Hour is that GRH can be played on a big grid. Despite the minor difference (and the fact that Rush Hour is rated for ages 8 and above), GRH is as complicated as some of the most profound and famous computational problems ever studied.

By the end of this column we are going to see that the seemingly simple question:

Does there exist a solution to a GRH instance?

can be answered (in the worst case) only by having the cars in the game emulate portions of a general purpose computing device. In so doing, we will examine Boolean logic (which is the basis of all computers), digital circuitry, and the mysterious topic of NP-completeness.

Calling Mr. Spock: Boolean Logic

When you get right down to it, all digital circuitry (such as the guts of calculators, watches, or home PCs) can be built from nothing more than primitive Boolean logic. In Boolean logic, values are either true or false, and they are either constant values or are computed as Boolean function of other Boolean values.

Table 1 shows how the three most basic Boolean functions (NOT, AND, and OR) work as a function of their inputs. These three Boolean functions work almost like they do in plain English except that most people use a slight variant for the English word "or".

By combining Boolean functions in a clever manner, one can duplicate any of the familiar mathematical operations, such as addition, division, exponentiation, equality tests, etc. Because Boolean logic can express these mathematical operations, it is extremely general and powerful. Interestingly, no one really understood the connection between Boolean logic and electronic circuitry until Claude Shannon proved in his 1938 master's thesis that Boolean logic is equivalent to digital electronic circuitry. This discovery allowed engineers to study the properties of electronic circuits by manipulating the equivalent Boolean expressions.

For example, Figure 2 shows an exclusive-OR circuit, which is identical to the Boolean expression (((NOT A) AND B) OR (A AND (NOT B))). Since Boolean expression can be manipulated algebraically, an identical circuit can be discovered by simply manipulating the Boolean expression. Today, virtually all digital electronic circuits are simulated with Boolean logic before they are committed to hardware.

This connection between Boolean logic and digital circuitry leads us to an important mathematical problem known as Satisfiability or SAT, for short. Given a Boolean expression, the problem is Does there exist an assignment of true/false values to the variables that makes the entire expression true? In other words, can the expression be satisfied? Notice that if you can answer this question, you can answer the same question about the equivalent digital circuit.

Obviously, one can do a brute force search and look over all possible combinations of true/false values for every variable. The fault with such an approach is that if you had a mere 100 variables, you would have to consider more assignments then there are electrons in the universe! No one knows how to solve SAT without looking at most of the possible assignments. Hence, programs that attempt to solve SAT can only do so very slowly since the number of candidate solutions that they must try grows exponentially in the number of variables in the original Boolean expression.

The bottom line: solving SAT is extremely difficult. But as hard as SAT is, GRH is harder. In the next section, we will see that any program that can solve GRH can also solve SAT, which proves that GRH is at least as hard as SAT.

How to Compute With Parked Cars

We will now see that GRH can "solve" SAT in the sense that for every Boolean expression, there exists a GRH game instance such that the game can be solved if, and only if, the Boolean expression can be satisfied. Moreover, the solution to the GRH game tells you the exact assignment needed to satisfy the Boolean expression. Our plan for this section is to build little gadgets out of cars that can be used to build more complicated devices. In the end, we will see how any Boolean expression can be mapped into a GRH game. We start with how to represent a Boolean variable in GRH.

In GRH, we can pass information around in the form of empty grid cells because the presence (or absence) of an empty cell can permit (or inhibit) motion in other cars. A packed line of cars can be used to pass information around (like a wire) because an empty cell can be moved by shifting the cars. However, to represent a Boolean variable, we need two solid lines of cars; one line represents that a variable is true, and the other represents that the variable is false.

Figure 3 shows a GRH variable in three stages. When the variable has a value of true or false, one of its two output lines will be in a downward position that allows other cars to back into the created hole. Figure 3b shows the transition from true to false. Since the two car lines are tied together by the horizontal row of reddish cars, it is impossible for a GRH variable to assume simultaneously a true and false state; however, a GRH variable can assume a nonsense value during a transition.

One nice side effect of this representation is that logical negation (i.e., the Boolean NOT function) can be accomplished by swapping the two packed lines of cars. But, to build AND and OR circuits, we need more complicated ways to manipulate cars.

Figure 4 contains the remaining gadgets required to build GRH circuits. In the first three sub-figures, the reddish cars act as trigger lines that can toggle activity in other portions of the game. The intersection gadget, in 4a, is the most complicated piece of plumbing needed. It allows two lines to cross. The intersection "inputs" are on the bottom and on the left. The "outputs," on the top and right sides, can backup only when the corresponding inputs are open. Note that we can compute the negation of a variable with a single intersection gadget.

Figure 4b and 4c show two types of switching gadgets. The conjunctive block's output, in 4b, can open only (i.e., back up) when both of its inputs are open. Similarly, the output of the disjunctive block, in 4c, can open if either of its inputs are open.

Now, suppose you want to compute the AND of two variables. Figure 5a shows how you could construct a GRH game that can effectively compute an AND function. The AND gadget has exactly one of each of the smaller gadgets from Figure 4, which are now shown in iconic form. Since each Boolean variable is represented by two lines of packed cars, the AND gadget has four inputs and two outputs.

The AND gadget works because it allows cars to back up only in a manner that is consistent with the AND Boolean function. If we want the AND_t output to open, then both A_t and B_t must be open. But if we want AND_f output to open, then one of A_f or B_f must be open. In this way, the output of the conjunctive and disjunctive gadgets represent the competing hypotheses that the AND function should take a value of true or false, respectively. The answer to the question How can I make the true (or false) output of the AND gadget open? is identical to How can I make A AND B true (or false)?

We can similarly build an OR gadget by swapping the disjunctive and conjunctive gadgets from the AND gadget. The basic idea is shown in Figure 5b.

To represent an arbitrary Boolean expression, use as many gadgets as is needed. Notice that all of the gadgets in Figure 4 are the same size. This means that we can tile them together, with input ends matching up to output ends. The final step is to orient a single target car so that it can only exit the game grid if the output of the final GRH gadget can open.

In the end, the only way to get the target car out is to have every GRH gadget behave like a digital circuit.

And Now For Something Completely Different: NP-Completeness

In 1970, Steven Cook proved one of the most important mathematical results of the millennium. He showed that SAT was essentially the hardest problem in a broad problem class known as NP, which stands for nondeterministic polynomial. The name refers to the fact that all problems in NP have the property that guesses at solutions can be confirmed with a number of steps that is polynomial in the problem size. In other words, finding a solution may be easy or hard, but verifying a solution is always easy.

The class of NP includes many important problems such as the Traveling Salesperson Problem and Graph Coloring. What is important about Cook's result is that any problem in NP can be reduced into a SAT problem, so that the solution to the SAT instance solves the original problem for you. Intuitively, SAT is so general and powerful because SAT instances are equivalent to digital circuits without loops. If a problem can be encoded and solved by a smallish digital circuit, then it can be encoded and solved by SAT as well.

SAT is said to be NP-complete because it is in NP, but it is as hard or harder than anything else in NP. Surprisingly, GRH is harder than SAT because it is too difficult a problem to be reduced into a SAT instance. Here's some intuition as to why: SAT deals exactly with digital circuits that have no loops in them; however, digital circuits with loops can be encoded into a GRH problem. This means that it is also possible to encode an entire computer with finite memory into a GRH problem.

To appreciate just how profound a result this is, the following question can be encoded into a single GRH game:

Is my least favorite operating system bug free for computers with 128M of memory or less?

Now, that's a GRH game that I'd love to see someone solve.

For more information about computational complexity, see the bible of the field, Computers and Intractability : A Guide To The Theory Of NP-Completeness, by M. R. Garey and D. S. Johnson. Also, Winning Ways For Your Mathematical Plays, by Elwyn R. Berlekamp, Richard K. Guy, and John H. Conway, is a magnificent collection on the intersection between games and computer science.

Acknowledgements

I thank Jennifer Goldberg, Harold Stone, and Eric Baum for helpful discussions about Rush Hour, PSPACE-completeness, and other cool things.

One Response to “Brain Candy: Rush Hour”

Leave a reply