@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00071326,
 author = {草野, 一彦 and 成澤, 和志 and 篠原, 歩 and KAZUHIKO, KUSANO and KAZUYUKI, NARISAWA and AYUMI, SHINOHARA},
 book = {ゲームプログラミングワークショップ2010論文集},
 issue = {12},
 month = {Nov},
 note = {立体ピクロスとは任天堂が2009年に発売した同名のゲームに収録されているパズルである.問題として立方体のブロックが積み重なった直方体が与えられ,ブロックに描かれたヒントに従って不要なブロックを削り,隠されたカタチを取り出すのが目的である.本稿では,3SATからの帰着により,立体ピクロスの解の存在判定がNP完全であることを示す.また,立体ピクロスの高さを1に制限し,普通数字・丸数字・四角数字を区別しない場合には,解の存在判定が多項式時間で行えることを示す., 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.},
 pages = {108--113},
 publisher = {情報処理学会},
 title = {立体ピクロスはNP完全},
 volume = {2010},
 year = {2010}
}