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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139145 |
| _version_ | 1826203035120959488 |
|---|---|
| author | Brunner, Josh |
| author2 | Demaine, Erik |
| author_facet | Demaine, Erik Brunner, Josh |
| author_sort | Brunner, Josh |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:30:40Z |
| format | Thesis |
| id | mit-1721.1/139145 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:30:40Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1391452022-01-15T03:33:37Z Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles Brunner, Josh Demaine, Erik Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. M.Eng. 2022-01-14T14:52:37Z 2022-01-14T14:52:37Z 2021-06 2021-06-17T20:12:57.020Z Thesis https://hdl.handle.net/1721.1/139145 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Brunner, Josh Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles |
| title | Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles |
| title_full | Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles |
| title_fullStr | Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles |
| title_full_unstemmed | Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles |
| title_short | Subway Shuffle, 1 × 1 Rush Hour, and Cooperative Chess Puzzles: Computational Complexity of Puzzles |
| title_sort | subway shuffle 1 1 rush hour and cooperative chess puzzles computational complexity of puzzles |
| url | https://hdl.handle.net/1721.1/139145 |
| work_keys_str_mv | AT brunnerjosh subwayshuffle11rushhourandcooperativechesspuzzlescomputationalcomplexityofpuzzles |