04 May 2010

Rush Hour is PSPACE-complete

A friend got me playing the Traffic Jam game for Android, which is a clone of the children's game Rush Hour:

The object is to move the cars around so that the yellow car can exit the board; each car may move vertically or horizontally but not both.

I was amused (though not totally surprised) to learn that when one considers the generalization of this game to larger boards, it is NP-hard and PSPACE-complete to decide whether a configuration is solvable or not. Flake and Baum, in a 2002 paper (subtitle: "Why you should generously tip parking lot attendants"), prove this by showing how to emulate certain classes of digital circuitry in Rush Hour. This paper is worth a look even if you are only inclined to glance at the pictures of the constructions. The authors built freaking digital logic out of cars.

As with many good games, it seems there is more to Rush Hour than meets the eye.

No comments:

Post a Comment