Paper by Erik D. Demaine
- Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff, “1 × 1 Rush Hour with Fixed Blocks is PSPACE-complete”, in Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020), La Maddalena, Italy, September 28–30, 2020, 7:1–7:14.
Consider n2 − 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.
- This paper is also available as arXiv:2003.09914.
- The paper is available in PDF (748k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 3, 2020 by