著者

Jonas Kölker

出版者

一般社団法人 情報処理学会

雑誌

Journal of Information Processing (ISSN:18826652)

巻号頁・発行日

vol.20, no.3, pp.694-706, 2012 (Released:2012-07-15)

参考文献数

8

被引用文献数

2 15

---

In a Kurodoko puzzle, one must colour some squares in a grid black in a way that satisfies non-overlapping, non-adjacency, reachability and numeric constraints specified by the numeric clues in the grid. We show that deciding the solvability of Kurodoko puzzles is NP-complete.