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

この論文をさがす

著者

抄録

計算量に関する研究において、最近ではテトリスのようないわゆる「落ちもの」ゲームの計算量にも興味が集まっている。本研究ではぷよぷよというゲームを取り上げる。一般化ぷよぷよの連鎖数判定問題の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.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 104(743), 95-103, 2005-03-11

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

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

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

  • ぷよぷよはNP完全

    牟田 秀俊

    電子情報通信学会技術研究報告. COMP, コンピュテーション 105(72), 39-44, 2005-05-13

    参考文献7件 被引用文献3件

キーワード

各種コード

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