セグメント情報のない立体ピクロス及び高さ1の立体ピクロスのNP完全性

• Item type: SIG Technical Reports(1)
• 公開日: 2016-07-29
• タイトル: セグメント情報のない立体ピクロス及び高さ1の立体ピクロスのNP完全性
• タイトル / 言語: en
• タイトル: NP-completeness of Picross 3D without Segment Information and That with the Height of One
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: パズルゲームの理論
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 高知工科大学情報学群
• 著者所属: 高知工科大学情報学群／現在，ユニバーサル・インフォメーション・サービス株式会社
• 著者所属(英): en
• 著者所属(英): Kochi University of Technology
• 著者所属(英): en
• 著者所属(英): Kochi University of Technology /
• 著者名: 高田, 喜朗; 五十嵐, 達郎
• 著者名(英): Yoshiaki, Takata; Tatsuro, Ikarashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 立体ピクロスは，任天堂が販売するゲームソフトウェア中のパズルである．立方体を積み重ねた直方体が与えられ，ヒントを基に不要な立方体を消して隠された立体を見つけることがパズルの目的である．草野らは，このパズルの解の存在判定が NP 完全であること，また，高さが 1 に限定されかつセグメント情報がヒントとして与えられない場合には多項式時間可解であることを示した．しかし，高さが自由であることとセグメント情報が与えられることのどちらが NP 完全性に寄与しているかは不明であった．本研究ではこの問題について考察し，その結果，高さが 2 以上でセグメント情報が与えられない場合，及び，高さが 1 でセグメント情報が与えられる場合，どちらも NP 完全であることがわかった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Picross 3D is a puzzle provided in a game software published by Nintendo. Kusano et al. have shown that it is NP-complete to decide whether a given Picross 3D instance has a solution. They have also shown that it is polynomial-time solvable if we restrict the height of the instance to one and erase segment information from the hints. However, it has not been known that which is the source of the NP-completeness, the height of the instance or the segment information. In this paper, we show that both of them are the source of the NP-completeness; i.e., it is NP-complete either if the segment information is not given and the height is more than one or if the segment information is given and the height is restricted to one.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12049625
• 書誌情報: 研究報告エンタテインメントコンピューティング（EC）; 巻 2016-EC-41, 号 15, p. 1-8, 発行日 2016-07-29
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8914
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会