著者

水野 秀一 田中 哲朗

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.28, pp.53-59, 2008-03-12

参考文献数

5

被引用文献数

1

---

I.Q はよく知られたパズルゲームであるが,その計算量の議論はこれまで行われてこなかった.本論文では,I.Q のクリアにおいて重要な概念であるターン数に着目し,決められたターンにすべてのキューブを捕獲することができるかどうかというターン数判定問題が NP 完全であることを証明した.Up to now, the computational complexity of I.Q has not been discussed though it is a puzzle game known well. In this paper, wo proofed NP-completeness of the turn number decision problem which is whether to catch all cube in given turns.