一般化ぷよぷよの連鎖数判定問題  [in Japanese] NP-completeness of Maximum Chain Problem on Generalized Puyopuyo  [in Japanese]

Search this Article

Author(s)

Abstract

計算量に関する研究において、最近ではテトリスのようないわゆる「落ちもの」ゲームの計算量にも興味が集まっている。本研究ではぷよぷよというゲームを取り上げる。一般化ぷよぷよの連鎖数判定問題のNP完全性を3-PARTITIONからの帰着によって示す。

Recently, complexity of the puzzles like Tetris draw our attention. In this paper, we deal with Puyopuyo; it is a computer game well-known in Japan. We prove NP-completeness of maximum chain problem on generalized Puyopuyo by reduction from 3-PARTITION.

Journal

  • IEICE Tech. Rep.

    IEICE Tech. Rep. 104(743), 95-103, 2005-03-11

    The Institute of Electronics, Information and Communication Engineers

References:  7

Cited by:  1

Codes

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