2020/04/23 by Hadyn Tang, Tang, Hadyn
Computer Science · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Management and Algorithms #F.1.3 #FOS: Computer and information sciences #FOS: Mathematics #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2004.12849
openalex publication_date 2020/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
"Eye-Witless", "Haisu" and "Oriental House" are genres of logic puzzles invented by William Hu, and "Detour" is a genre of logic puzzle invented by online user Guowen Zhang. Each of these puzzles revolves around constructing a path or loop through the cells of a grid according to certain constraints given by clues in the grid. We prove that deciding whether a particular puzzle in each of these genres is solvable is NP-complete.