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

Search this Article

Author(s)

    • 松金 輝久 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

Abstract

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

Journal

  • The IEICE transactions on information and systems (Japanese edetion)

    The IEICE transactions on information and systems (Japanese edetion) J89-D(3), 405-413, 2006-03-01

    The Institute of Electronics, Information and Communication Engineers

References:  8

Cited by:  3

Codes

  • NII Article ID (NAID)
    10017435004
  • NII NACSIS-CAT ID (NCID)
    AA12099634
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    18804535
  • NDL Article ID
    7862040
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-779
  • Data Source
    CJP  CJPref  NDL  NII-ELS 
Page Top