Abstract: Subway shuffle is an addicting puzzle game created by Bob Hearn. It is played on a graph with colored edges that represent subway lines; colored tokens that represent subway cars are placed on the nodes of the graph. A token can be moved from its current node to an empty one, but only if the two nodes are connected with an edge of the same color of the token. The aim of the game is to move a special token to its final target position. We prove that deciding if the game has a solution is PSPACE-complete even when the game graph is planar.
Introduction
In the last years the study of the complexity of puzzles and (video)games has gained much attention (see for example the survey [1]). Most games can be generalized to arbitrary instance size and transformed to decision problems in which the question is usually: “Given an instance of size $m \times n$ of the game X, does it have a solution?”. It turns out that most static puzzles (sudoku, kakuro, binary puzzle, light up, …) are NP-complete and that most dynamic puzzles (sokoban, rush hour, atomix, …) are PSPACE-complete.
One of the puzzles for which the complexity was still unknown is Subway Shuffle; we proved, as conjectured in [2], that its rules are rich enough to be PSPACE-complete. The proof uses the framework of the nondeterministic constraint logic model of computation ([2], [3]): given a planar constraint graph in normal form, it is PSPACE-complete to find a sequence of edge reversals (moves) that keep the constraint graph valid, ending in the reversal of a special edge $e^*$.
We build an equivalent subway shuffle board with EDGE, AND and LATCH gadgets that has a solution (i.e. a sequence of moves that shift the special token to its final target position) if and only if there is a sequence of moves that reverses $e^*$.
You can download a preliminary draft version of the paper here:
click here to download a preliminary draft of the paper
[1] Graham Kendall, Andrew J. Parkes, Kristian Spoerer: A Survey of NP-Complete Puzzles. ICGA Journal 31(1): 13-34 (2008)
[2] Robert A. Hearn, Erik D. Demaine: Games, puzzles and computation. A K Peters 2009, ISBN 978-1-56881-322-6, pp. I-IX, 1-237
[3] Robert A. Hearn, Erik D. Demaine: The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. ICALP 2002: 401-413