著者
草野 一彦 成澤 和志 篠原 歩
雑誌
ゲームプログラミングワークショップ2010論文集
巻号頁・発行日
vol.2010, no.12, pp.108-113, 2010-11-12

立体ピクロスとは任天堂が2009年に発売した同名のゲームに収録されているパズルである.問題として立方体のブロックが積み重なった直方体が与えられ,ブロックに描かれたヒントに従って不要なブロックを削り,隠されたカタチを取り出すのが目的である.本稿では,3SATからの帰着により,立体ピクロスの解の存在判定がNP完全であることを示す.また,立体ピクロスの高さを1に制限し,普通数字・丸数字・四角数字を区別しない場合には,解の存在判定が多項式時間で行えることを示す.

言及状況

はてなブックマーク (5 users, 5 posts)

私の知ってるパズルで適当にググってみたらNP完全らしかった

Twitter (4 users, 4 posts, 1 favorites)

私の知ってるパズルで適当にググってみたらNP完全らしかった / “立体ピクロスは NP 完全” https://t.co/3kJbDFQ3sd
立体ぴくろすはNP完全.3SATになるらしい. https://t.co/tScqhANV3Z
所以益智游戏都得是NPC么?“任天堂ピクロス3D 的NPC证明” https://t.co/A5lsRz8a

Wikipedia (1 pages, 1 posts, 1 contributors)

編集者: 114.175.88.131
2011-09-16 19:47:07 の編集で削除されたか、リンク先が変更された可能性があります。

収集済み URL リスト