情報処理学会 第87回全国大会

5K-04
色数1の一般化ぷよぷよの連鎖数判定問題
○水越開理,武永康彦(電通大)
ぷよぷよは、代表的な落ち物パズルゲームの一つである。色ぷよとおじゃまぷよという性質の異なる2種類のぷよが存在し、プレイヤーは、これらのぷよを消すようにゲームを進める。一人用のぷよぷよにおいて、色ぷよの色数や、おじゃまぷよの有無といった条件は、ゲームの難易度に影響する。これらの条件を変更し、それぞれの場合について初期状態からk連鎖以上の連鎖を構成できるか判定する連鎖数判定問題の計算複雑さについて研究が行われてきた。本研究では、色ぷよの色数が1、おじゃまぷよ有りの制約下において、連鎖数判定問題の計算複雑さを明らかにする。