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

松金 輝久  武永 康彦  

誌名
電子情報通信学会論文誌 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完全であることを証明する.