Warning: Undefined array key "category" in /var/www/02search_html/bin/summary.php on line 35

Warning: Undefined variable $STR_top_url in /var/www/02search_html/bin/__base_html.php on line 883
IEICE Trans - 組合せ最適化問題としてのぷよぷよの連鎖数判定問題

組合せ最適化問題としてのぷよぷよの連鎖数判定問題

松金　輝久
武永　康彦

誌名
電子情報通信学会論文誌 D   Vol.J89-D    No.3    pp.405-413
発行日: 2006/03/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 計算量理論
キーワード: 
NP完全性,  計算量,  パズル,  

本文: PDF(554.7KB)>>
論文を購入


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