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]