Paper by Erik D. Demaine

Reference:
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.

Abstract:
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.

Length:
The paper is 7 pages.

Availability:
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 BibTeX file.
Last updated August 19, 2022 by Erik Demaine.