Paper by Erik D. Demaine

Reference:

Josh Brunner, Lily Chung, Erik D. Demaine, Della 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.

BibTeX

@InProceedings{RushHour_FUN2020,
  AUTHOR        = {Josh Brunner and Lily Chung and Erik D. Demaine and Della Hendrickson and Adam Hesterberg and Adam Suhl and Avi Zeff},
  authororig    = {Josh Brunner and Lily Chung and Erik D. Demaine and Dylan Hendrickson and Adam Hesterberg and Adam Suhl and Avi Zeff},
  TITLE         = {$1 \times 1$ {Rush} {Hour} with Fixed Blocks is {PSPACE}-complete},
  BOOKTITLE     = {Proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020)},
  bookurl       = {https://sites.google.com/view/fun2020/home},
  MONTH         = {September 28--30},
  YEAR          = 2020,
  ADDRESS       = {La Maddalena, Italy},
  PAGES         = {7:1--7:14},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2021.7},
  dblp          = {https://dblp.org/rec/conf/fun/BrunnerCDHHSZ21},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2003.09914">arXiv:2003.09914</A>.},
}

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.

Comments:

This paper is also available as arXiv:2003.09914.

Availability:

The paper is available in PDF (748k).

See information on file formats.

[Google Scholar search]