论文标题
在满足某些路径和循环难题的NP完整性上
On the NP-Completeness of Satisfying Certain Path and Loop Puzzles
论文作者
论文摘要
“无眼”，“ Haisu”和“ Oriental House”是William Hu发明的逻辑难题的流派，“ Detour”是由在线用户Guowen Zhang发明的逻辑难题的流派。这些难题中的每一个都围绕着根据网格中的线索给出的某些约束来构建路径或循环。我们证明，确定这些类型中每种类型中的特定难题是否都是NP完整的。
"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.
