六角格子，三角格子上でのスリザーリンクのASP完全性について

• Item type: SIG Technical Reports(1)
• 公開日: 2007-03-09
• タイトル: 六角格子，三角格子上でのスリザーリンクのASP完全性について
• タイトル / 言語: en
• タイトル: ASP-Completeness of the Slither Link Puzzle on Several Grids
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪電気通信大学 総合情報学部 情報工学科
• 著者所属: 大阪電気通信大学 情報通信工学部 情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Engineering Informatics, Osaka Electro-Communication University
• 著者所属(英): en
• 著者所属(英): Department of Engineering Informatics, OsakaElectro-Communication University
• 著者名: 温井, 康介; 上嶋, 章宏
• 著者名(英): Kosuke, NUKUI; Akihiro, UEJIMA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: パズルやゲームの面白さの源は，それらの持つ根源的な難しさにあり，これまで数多くのパズルやゲームの計算複雑さが解析されている．本稿では，ペンシルパズルの一種であるスリザーリンクの盤面を正k角格子状に一般化した，k‐スリザーリンクを提案し，k‐スリザーリンクの解の存在判定を問う問題のNP完全性を，制限付きハミルトン閉路問題からの多項式時間還元を用いて証明する．また，別解問題（ASP，Another Solution Problem，問題例とその1つの解が与えられたとき，他の解の有無を判定する問題）についても考察し，k‐スリザーリンクの別解問題について，そのNP完全性を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 23(2007-AL-111), p. 129-136, 発行日 2007-03-09
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会