著者

温井 康介 上嶋 章宏

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.23, pp.129-136, 2007-03-09

参考文献数

15

被引用文献数

1

---

パズルやゲームの面白さの源は,それらの持つ根源的な難しさにあり,これまで数多くのパズルやゲームの計算複雑さが解析されている.本稿では,ペンシルパズルの一種であるスリザーリンクの盤面を正k角格子状に一般化した,k‐スリザーリンクを提案し,k‐スリザーリンクの解の存在判定を問う問題のNP完全性を,制限付きハミルトン閉路問題からの多項式時間還元を用いて証明する.また,別解問題(ASP,Another Solution Problem,問題例とその1つの解が与えられたとき,他の解の有無を判定する問題)についても考察し,k‐スリザーリンクの別解問題について,そのNP完全性を示す.A fundamental difficulty to solve games and puzzles seems to become the basis for interest factors of them, and the computational complexity of puzzle games have been investigated. This paper proposes k-Slither Link Puzzle, which is a generalization of the traditional Slither Link Puzzle concerning the grids. The puzzle is one of many popular pencil-and-paper puzzles on rectangular grids k = 4, we deal with the puzzles on all the rest of regular tessellations of the plane, i.e. triangular k = 3 and hexagonal grids k = 6. This paper presents the NP-completeness of k-Slither Link Puzzle for k = 3, 6.Moreover, the NP-completeness of ANOTHER SOLUTION PROBLEMS (ASP), which are problems to decide if there is some solution other than a given solution, of the puzzles is proved in this paper.