2021/12/15 by Sagnik Saha, Erik D. Demaine, Saha, Sagnik +1
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Topological and Geometric Data Analysis #Geometric and Algebraic Topology
paper · pdf · doi:10.48550/arxiv.2112.07914
We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1 tiles. Such a puzzle is defined by a set of unit-square 1 tiles in a square grid, and a target square of the grid. A move consists of selecting an unselected 1 tile and then filling the next unfilled square in a chosen direction from that tile (similar to Tipover and Cross Purposes). We prove NP-completeness of deciding whether the target square can be filled, by a reduction from rectilinear planar monotone 3SAT.