六角格子,三角格子上でのスリザーリンクのASP完全性について
スポンサーリンク
概要
- 論文の詳細を見る
パズルやゲームの面白さの源は,それらの持つ根源的な難しさにあり,これまで数多くのパズルやゲームの計算複雑さが解析されている.本稿では,ペンシルパズルの一種であるスリザーリンクの盤面を正k-角格子状に一般化したk-トスリザーリンクを提案し,k-スリザーリンクの解の存在判定を問う問題のNP完全性を,制限付きハミルトン閉路問題からの多項式時間還元を用いて証明する.また,別解問題(ASP,Another Solution Problem, 問題例とその1つの解が与えられたとき,他の解の有無を判定する問題)についても考察し,k-スリザーリンクの別解問題について,そのNP完全性を示す.
- 一般社団法人情報処理学会の論文
- 2007-03-09
著者
関連論文
- 盤面および使用セルを考慮した回転型セル迷路のPSPACE完全性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- n/k-彩色での階層構造間に存在する平面グラフの構成手法
- 3
- Anti-Webによる$H$-彩色に関する新たな階層構造の導出 (理論計算機科学の深化と応用)
- H-彩色可能なグラフのクラスの階層構造のCirculant graphsによる細分化
- circulant制約を持った隣接色制約付き彩色問題の応用と解析 (計算理論とアルゴリズムの新展開)
- 六角格子,三角格子上でのスリザーリンクのASP完全性について
- 平面グラフの^^^~-彩色問題
- 5M-9 ZKIPを実現するために組合せ問題を基本機能に分解する枠組み(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 平面グラフのn/k-彩色問題の計算複雑さ
- 2
- 8面,20面ダイスを用いたRolling Dice PuzzleのNP完全性(アルゴリズムとデータ構造・計算複雑度)
- 回転型セル迷路のPSPACE完全性(アルゴリズムとデータ構造・計算複雑度)
- 2-K-6 色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性(ワークショップ「娯楽のOR-エンターテイメントの数理」)