Archive for date: May 12, 2006

Games, Puzzles and Computation

May 12, 2006 | General | By: Mark VandeWettering

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 […]