組合せ最適化問題としてのぷよぷよの連鎖数判定問題(計算量理論) NP-Completeness of Maximum Chain Problem on Puyopuyo

この論文をさがす

著者

    • 松金 輝久 MATSUKANE Teruhisa
    • 電気通信大学大学院情報工学専攻:現在, NTT データネッツ Department of Computer Science, Graduate School of Electro-Communications, The University of Electro-Communications
    • 武永 康彦 TAKENAGA Yasuhiko
    • 電気通信大学情報工学科 Department of Computer Science, Faculty of Electro-Communications, The University of Electro-Communications

抄録

ゲームやパズルの計算量や解法に関する研究は古くから行われている.特に最近ではテトリスのようなゲームが注目を集めている.本論文では,対戦型ゲームとして広く知られるぷよぷよを,人力として初期盤面と落下してくるピース列が与えられ,ピースを落下させることにより特定の目的を達成するパズルゲームとして定式化し,その連鎖数判定問題を考える.連鎖はぷよぷよにおける特徴的な性質であり,最大の連鎖を発生させる連鎖数判定問題がNP完全であることを証明する.

収録刊行物

  • 電子情報通信学会論文誌. D, 情報・システム

    電子情報通信学会論文誌. D, 情報・システム J89-D(3), 405-413, 2006-03-01

    一般社団法人電子情報通信学会

参考文献:  8件中 1-8件 を表示

被引用文献:  3件中 1-3件 を表示

キーワード

各種コード

  • NII論文ID(NAID)
    10017435004
  • NII書誌ID(NCID)
    AA12099634
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    18804535
  • NDL 記事登録ID
    7862040
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-779
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS 
ページトップへ