著者

高田 喜朗 五十嵐 達郎

雑誌

研究報告ゲーム情報学(GI) (ISSN:21888736)

巻号頁・発行日

vol.2016-GI-36, no.15, pp.1-8, 2016-07-29

---

立体ピクロスは,任天堂が販売するゲームソフトウェア中のパズルである.立方体を積み重ねた直方体が与えられ,ヒントを基に不要な立方体を消して隠された立体を見つけることがパズルの目的である.草野らは,このパズルの解の存在判定が NP 完全であること,また,高さが 1 に限定されかつセグメント情報がヒントとして与えられない場合には多項式時間可解であることを示した.しかし,高さが自由であることとセグメント情報が与えられることのどちらが NP 完全性に寄与しているかは不明であった.本研究ではこの問題について考察し,その結果,高さが 2 以上でセグメント情報が与えられない場合,及び,高さが 1 でセグメント情報が与えられる場合,どちらも NP 完全であることがわかった.