Rush Hour

John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in gridlock. A nice description of the problem is presented in a Science News article.

The general problem is PSPACE complete shown by Eric Baum and Gary Flake when they were at NEC. Tromp tells me that he has shown the problem is still PSPACE-complete when the cars are 2x1. Oddly enough the 1x1 case is the hardest to analyze and its complexity remains wide open.

Also check out Tromp's Rush Hour mazes.