1 1 Rush Hour with fixed blocks is PSPACE-complete
From MaRDI portal
Publication:6487573
DOI10.4230/LIPICS.FUN.2021.7zbMATH Open1515.6815MaRDI QIDQ6487573FDOQ6487573
Authors: Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff 
Publication date: 7 February 2023
Recommendations
- Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- scientific article; zbMATH DE number 2086639
- PSPACE-completeness of Bloxorz and of games with 2-buttons
- \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)
Cited In (10)
- Title not available (Why is that?)
- Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
- On the complexity of motion planning problem of a forklift
- Parameterized complexity of graph constraint logic
- Pushing blocks is hard.
- On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game
- Ice sliding games
- Title not available (Why is that?)
- PSPACE-completeness of Bloxorz and of games with 2-buttons
- Multi-robot motion planning for unit discs with revolving areas
This page was built for publication: \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487573)
