brainwagon

An as-yet unfinished draft of Bob Hearn’s MIT PhD thesis Games, Puzzles and Computation is online.   I first became aware of some of these results at a conference a couple of years ago, which showed that sliding block puzzles like Rush Hour belong to the class of PSPACE-complete problems.   What does that mean?  From the [...]