WEKO3
-
RootNode
アイテム
立体ピクロスはNP完全
https://ipsj.ixsq.nii.ac.jp/records/71326
https://ipsj.ixsq.nii.ac.jp/records/71326d477bbeb-277f-483f-95b0-60b45698f526
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-GPWS2010021 (688.4 kB)
|
Copyright (c) 2010 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Symposium(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2010-11-12 | |||||||
| タイトル | ||||||||
| タイトル | 立体ピクロスはNP完全 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Picross 3D is NP-complete | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||
| 資源タイプ | conference paper | |||||||
| 著者所属 | ||||||||
| 東北大学大学院情報科学研究科／日本学術振興会特別研究員DC | ||||||||
| 著者所属 | ||||||||
| 東北大学大学院情報科学研究科 | ||||||||
| 著者所属 | ||||||||
| 東北大学大学院情報科学研究科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences,Tohoku University/Research Fellow of the Japan Society for the Promotion of Science | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences,Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Information Sciences,Tohoku University | ||||||||
| 著者名 |
草野, 一彦
成澤, 和志
篠原, 歩
× 草野, 一彦 成澤, 和志 篠原, 歩
|
|||||||
| 著者名(英) |
KAZUHIKO, KUSANO
KAZUYUKI, NARISAWA
AYUMI, SHINOHARA
× KAZUHIKO, KUSANO KAZUYUKI, NARISAWA AYUMI, SHINOHARA
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 立体ピクロスとは任天堂が2009年に発売した同名のゲームに収録されているパズルである.問題として立方体のブロックが積み重なった直方体が与えられ,ブロックに描かれたヒントに従って不要なブロックを削り,隠されたカタチを取り出すのが目的である.本稿では,3SATからの帰着により,立体ピクロスの解の存在判定がNP完全であることを示す.また,立体ピクロスの高さを1に制限し,普通数字・丸数字・四角数字を区別しない場合には,解の存在判定が多項式時間で行えることを示す. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Picross 3D is a puzzle which is included in the video game with the same title, Nintendo released on 2009. Players are given a rectangular parallelepiped made of cubic blocks and try to take out the hidden object from it breaking unwanted blocks. In this paper, we show that it is NP-complete to decide whether a given Picross 3D has solutions by reducing 3SAT to Picross 3D. We also show that we can decide exsistence of solutions in polynomial time if height of Picross 3D is restricted to 1 and condition of hint numbers is ignored. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA12496601 | |||||||
| 書誌情報 |
ゲームプログラミングワークショップ2010論文集 巻 2010, 号 12, p. 108-113, 発行日 2010-11-12 |
|||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
