著者

八登 崇之

出版者

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

雑誌

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

巻号頁・発行日

vol.2000, no.84, pp.25-31, 2000-09-21

被引用文献数

3

---

現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析されている.本稿では,パズルの一種であるスリザーリンクについて,解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する.また,スリザーリンクの別解問題(Another Solution Problem,1つ解が与えられた時に他に解があるかを判定する問題)について考察し,そのNP完全性の証明の指針を示す.For many of the widely played games and puzzles, their computational complexities have been analyzed. In this paper, we consider a sort of puzzle "Slither Link" and prove that the problem which determines whether or not a given instance of puzzle has any solutions is NP-complete, by using a polynomial time reduction from the Hamilton Path Problem with respect to restricted graphs. In addition we consider Another Solution Problem for the puzzle, the problem which determines, for a given instance and its solution, whether there is another solution for the instance. We provide a strategy to prove its NP-completeness.

著者

八登 崇之

雑誌

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

巻号頁・発行日

vol.2000, no.84(2000-AL-074), pp.25-31, 2000-09-21

---

現在多くの人に遊ばれているゲームやパズルの多くについて,その計算量が解析されている.本稿では,パズルの一種であるスリザーリンクについて,解があるかを判定する問題のNP完全性を制限されたハミルトン閉路問題からの多項式時間還元を用いて証明する.また,スリザーリンクの別解問題(Another Solution Problem,1つ解が与えられた時に他に解があるかを判定する問題)について考察し,そのNP完全性の証明の指針を示す.

著者

八登 崇之 瀬田 剛広

出版者

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

雑誌

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

巻号頁・発行日

vol.2002, no.103, pp.9-16, 2002-11-08

---

問題?に対する別解問題(ASP)というのは、?のインスタンスxとそれに対する1つの解sが与えられた時に、xのs以外の解を求める問題のことである。(新しい問題クラスとしてのASPの概念はUedaとNagaoによる。)本論文ではn個の解が与えられたときにもう1つの解を求める問題(n-ASP)について考察する。特に、対応する解への変換も多項式時間で行えるような多項式時間parsimonious還元に関する完全性であるASP完全性について考察する。応用として、本論文では3つの有名なパズル、スリザーリンクとカックロ(クロスサム)とナンバープレース(数独)についてそのASP換算製(NP完全性を含意する)を示す。The Another Solution Problem (ASP) of a problem II is the following problem: for a given instance x of II and a solution s to it, find a solution to x other than s. (The notion of ASP as a new class of problems was first introduced by Ueda and Nagao.) In this paper we consider n-ASP, the problem to find another solution when n solutions are given. In particular we consider ASP-completeness, the completeness with respect to the parsimonious reductions which allow polynomial-time transformation of solutions. As an application, we prove the ASP-completeness (which implies NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number Place.