Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles

Oriented Subway Shuffle is a game played on a directed graph with colored edges and colored tokens present on some vertices. A move consists of moving a token across an edge of the matching color to an unoccupied vertex and reversing the orientation of that edge. The goal is to move a token across a target edge. We show that it is PSPACE-complete to determine whether a particular target edge can be moved across through a sequence of Oriented Subway Shuffle moves. We show how this can be interpreted in the context of the motion-planning-through-gadgets framework, thus showing PSPACE-completeness of certain motion planning problems. In contrast, we show that polynomial time suffices to determine whether a particular token can ever move. This hardness result is motivated by three applications of proving other puzzles hard. A fairly straightforward reduction shows that the puzzle game Rush Hour is PSPACE-complete when all of the cars are 1 × 1 and there are fixed immovable cars. We show that two classes of cooperative Chess puzzles, helpmates and retrograde Chess, are also PSPACE-complete by reductions from Oriented Subway Shuffle.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Brunner, Josh

Advisor dc:contributor.advisor

• Demaine, Erik

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139145

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139145