ぷよぷよはNP完全  [in Japanese] PUYOPUYO is NP-Complete  [in Japanese]

Search this Article

Author(s)

    • 牟田 秀俊 MUTA Hidetoshi
    • 東京大学大学院情報理工学系研究科 Dept. of Computer Science, Graduate School of Information Science and Technology, the Univ, of Tokyo

Abstract

計算量理論の応用法の一つにパズルの計算量を測って難しさを推定するのがある.本研究では, ぷよぷよという同じ色のぷよをくっつけて消すというパズルゲームのオフライン版を3-PARITIONからの還元でNP完全問題であることを示す.

In this research, we analyze the complexity of the offline version of Puyopuyo. Puyopuyo is the game in which the player make same colored puyos connected and cleared.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 105(72), 39-44, 2005-05-13

    The Institute of Electronics, Information and Communication Engineers

References:  7

Cited by:  3

Codes

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