**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.

Last updated July 23, 2024 by Erik Demaine.