2024-03-29T11:14:31Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000316932023-04-27T10:00:04Z01164:02592:02600:02605
六角格子,三角格子上でのスリザーリンクのASP完全性についてASP-Completeness of the Slither Link Puzzle on Several Gridsjpnhttp://id.nii.ac.jp/1001/00031693/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31693&item_no=1&attribute_id=1&file_no=1Copyright (c) 2007 by the Information Processing Society of Japan大阪電気通信大学 総合情報学部 情報工学科大阪電気通信大学 情報通信工学部 情報工学科温井, 康介上嶋, 章宏パズルやゲームの面白さの源は,それらの持つ根源的な難しさにあり,これまで数多くのパズルやゲームの計算複雑さが解析されている.本稿では,ペンシルパズルの一種であるスリザーリンクの盤面を正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.AN1009593X情報処理学会研究報告アルゴリズム(AL)200723(2007-AL-111)1291362007-03-092009-06-30