LIPIcs.FUN.2021.7.pdf
- Filesize: 0.73 MB
- 14 pages
Document
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete
Authors
-
Part of:
Volume:
10th International Conference on Fun with Algorithms (FUN 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-16
File
Document Identifiers
Acknowledgements
We thank the many colleagues over the years for their early collaborations in trying to resolve the 1 × 1 Rush Hour problem (when E. Demaine mentioned it to various groups over the years): Timothy Abbott, Kunal Agrawal, Reid Barton, Punyashloka Biswal, Cy Chen, Martin Demaine, Jeremy Fineman, Seth Gilbert, David Glasser, Flena Guisoresac, MohammadTaghi Hajiaghayi, Nick Harvey, Takehiro Ito, Tali Kaufman, Charles Leiserson, Petar Maymounkov, Joseph Mitchell, Edya Ladan Mozes, Krzysztof Onak, Mihai Pǎtraşcu, Guy Rothblum, Diane Souvaine, Grant Wang, Oren Weimann, Zhong You (MIT, November 2005); Jeffrey Bosboom, Sarah Eisenstat, Jayson Lynch, and Mikhail Rudoy (MIT 6.890, Fall 2014); and Joshua Ani, Erick Friis, Jonathan Gabor, Josh Gruenstein, Linus Hamilton, Lior Hirschfeld, Jayson Lynch, John Strang, Julian Wellman (MIT 6.892, Spring 2019, together with the present authors).
Cite As Get BibTex
Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.7
Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Subject Classification
ACM Subject Classification
- Theory of computation → Problems, reductions and completeness
Keywords
- puzzles
- sliding blocks
- PSPACE-hardness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Marzio De Biasi and Tim Ophelders. Subway Shuffle is PSPACE-complete. Manuscript, February 2015. URL: http://www.nearly42.org/cstheory/subway-shuffle-is-pspace-complete/.
-
Erik D. Demaine, Robert A. Hearn, and Michael Hoffmann. Push-2-F is PSPACE-complete. In Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG 2002), pages 31-35, Lethbridge, Alberta, Canada, August 12-14 2002.
-
Erik D. Demaine and Mikhail Rudoy. A simple proof that the (n²-1)-puzzle is hard. Theoretical Computer Science, 732:80-84, July 2018.
-
Gary William Flake and Eric B. Baum. Rush Hour is PSPACE-complete, or "Why you should generously tip parking lot attendants". Theoretical Computer Science, 270(1-2):895-911, 2002.
-
Martin Gardner. Sliding-block puzzles. In Martin Gardner’s Sixth Book of Mathematical Diversions from Scientific American. W. H. Freeman and Company, 1971. Republished by MAA, 2001.
- Robert A. Hearn. Games, Puzzles, and Computation. PhD thesis, Massachusetts Institute of Technology, 2006. URL: http://erikdemaine.org/theses/bhearn.pdf.
-
Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, October 2005. Originally appeared at ICALP 2002.
-
Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation. AK Peters/CRC Press, 2009.
- Patentarcade.com. Case update: Rubin v. Apple Inc. Blog post, 7 July 2011. URL: http://patentarcade.com/2011/07/new-case-rubin-v-apple-inc.html.
- Daniel Ratner and Manfred Warmuth. The (n²-1)-puzzle and related relocation problems. Journal of Symbolic Computation, 10:111-137, 1990. URL: http://users.soe.ucsc.edu/~manfred/pubs/J15.pdf.
- Don Rubin. The Parking Lot. http://www.donrubin.com/parking_lot.html, 2012.
- Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. URL: https://doi.org/10.1016/S0022-0000(70)80006-X.
-
Jerry Slocum and Dic Sonneveld. The 15 Puzzle. Slocum Puzzle Foundation, 2006.
- Kiril Solovey and Dan Halperin. On the hardness of unlabeled multi-robot motion planning. The International Journal of Robotics Research, 35(14):1750-1759, November 2016. URL: https://doi.org/10.1177/0278364916672311.
- James A. Storer. Tokyo Parking / Rush Hour. Jim Storer Puzzles Home Page, 2015. URL: https://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzTokyoParking.html.
- ThinkFun. The evolution of ThinkFun’s Rush Hour. Blog post, February 2018. URL: http://info.thinkfun.com/stem-education/the-evolution-of-thinkfuns-rush-hour.
- John Tromp and Rudi Cilibrasi. Limits of Rush Hour Logic complexity. arXiv preprint cs/0502068, 2005. URL: https://arXiv.org/abs/cs/0502068.
- Stephen A. Wagner. Manipulable puzzle. U.S. Patent D395,468, June 1998. URL: https://patents.google.com/patent/USD395468S/en?oq=d395468.