Paper by Erik D. Demaine
- Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy, “Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible”, in Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy, June 13–15, 2018, 3:1–3:21.
We analyze the computational complexity of the many types of
pencil-and-paper-style puzzles featured in the 2016 puzzle video game The
Witness. In all puzzles, the goal is to draw a path in a rectangular grid
graph from a start vertex to a destination vertex. The different puzzle types
place different constraints on the path: preventing some edges from being
visited (broken edges); forcing some edges or vertices to be visited
(hexagons); forcing some cells to have certain numbers of incident path edges
(triangles); or forcing the regions formed by the path to be partially
monochromatic (squares), have exactly two special cells (stars), or be singly
covered by given shapes (polyominoes) and/or negatively counting shapes
(antipolyominoes). We show that any one of these clue types (except
the first) is enough to make path finding NP-complete (“witnesses exist
but are hard to find”), even for rectangular boards. Furthermore, we
show that a final clue type (antibody), which necessarily
“cancels” the effect of another clue in the same region, makes
path finding Σ2-complete (“witnesses do not
exist”), even with a single antibody (combined with many
anti/polyominoes), and the problem gets no harder with many antibodies.
- The full version of this paper is available as arXiv:1804.10193.
- The paper is available in PDF (745k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 13, 2020 by