2026-07-26T03:28:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8794 2024-03-06T10:42:40Z ddc:004 open_access

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible Abel, Zachary Bosboom, Jeffrey Demaine, Erik D. Hamilton, Linus Hesterberg, Adam Kopinsky, Justin Lynch, Jayson Rudoy, Mikhail video games puzzles hardness 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 Sigma_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zachary Abel and Jeffrey Bosboom and Erik D. Demaine and Linus Hamilton and Adam Hesterberg and Justin Kopinsky and Jayson Lynch and Mikhail Rudoy 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.3 urn:nbn:de:0030-drops-87944 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.3 eng https://creativecommons.org/licenses/by/3.0/legalcode