Paper by Erik D. Demaine
- Sagnik Saha and Erik D. Demaine, “ZHED is NP-complete”, in Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG 2022), Toronto, Ontario, Canada, August 25–27, 2022, to appear.
We prove that the 2017 puzzle game ZHED is NP-complete, even with just tiles
numbered 1. Such a puzzle is defined by a set of unit-square tiles in a
square grid, and a target square of the grid. A move consists of selecting a
previously unselected tile and then filling the next unfilled square in a
chosen direction from that tile (similar to Tipover and Cross Purposes). We
prove the NP-completeness of deciding whether the target square can be filled,
by a reduction from rectilinear planar monotone 3SAT.
- The paper is 7 pages.
- The paper is available in PDF (622k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by