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.

BibTeX

@InProceedings{Zhed_CCCG2022,
  AUTHOR        = {Sagnik Saha and Erik D. Demaine},
  TITLE         = {{ZHED} is {NP}-complete},
  BOOKTITLE     = {Proceedings of the 34th Canadian Conference on Computational Geometry (CCCG 2022)},
  bookurl       = {https://www.torontomu.ca/canadian-conference-computational-geometry-2022/},
  ADDRESS       = {Toronto, Ontario, Canada},
  MONTH         = {August 25--27},
  YEAR          = 2022,
  PAGES         = {to appear},

  withstudent   = 1,
  unrefereed    = 1,
  length        = {7 pages},
  dblp          = {https://dblp.org/rec/conf/cccg/SahaD22},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2112.07914">arXiv:2112.07914</A>.},
}

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.

Comments:

This paper is also available as arXiv:2112.07914.

Length:

The paper is 7 pages.

Availability:

The paper is available in PDF (622k).

See information on file formats.

[Google Scholar search]