On the parameterized complexity of the generalized rush hour puzzle.
Henning Fernau, Torben Hagerup, Naomi Nishimura, Prabhakar L. Ragde, Klaus Reinhardt · OPUS (Augsburg University) · 2003
We consider the parameterized complexity of a generalized version of the game Rush Hour, which is a puzzle requiring the player to find a sequence of moves by vehicles to enable a special target vehicle to escape from a grid-shaped game board that may contain obstacles. Although the problem is PSPACE-complete, we demonstrate algorithms that work in polynomial time when either the total number of vehicles or the total number of moves is bounded by a constant. Our contributions are two-fold, entailing the application of ideas of parameterized complexity to games and to motion-planning problems (albeit motion-planning problems of a very constrained nature).