一般化ぷよぷよのより強い計算困難性

本研究では一般化ぷよぷよの計算複雑度について考える．対象とするのは盤面サイズ，色数に関して一般化した，オフライン型パズルとしてのぷよぷよである．本研究ではこの一般化ぷよぷよにおける 2つの問題を取り上げる．1 つは全消し判定であり，もう一つは連鎖数最大化である．前者に関してはぷよ 2色（おじゃまぷよあり）の設定であっても NP 完全であることが，後者に関してはぷよ 4 色（おじゃまぷよあり）の設定でも NP 困難であることが示されている．特に後者に関しては，詳細な証明は公開されていないがぷよ 3 色（おじゃまぷよあり）の設定で，あるいはぷよ 5 色（おじゃまぷよなし）でも NP 困難であることが指摘されている．本研究ではこれらの結果をいくつかの側面から強化する．我々の結果は以下のとおりである： (1) 連鎖数最大化はぷよ 3 色（おじゃまぷよなし）でも NP 困難，(2) P≠NP の仮定の下で， ぷよ 4 色（おじゃまぷよあり）の連鎖数最大化に対しては近似比の精度保証が入力の多項式以下となるような多項式時間近似アルゴリズムは存在しない， (3) 全消し判定はぷよ 4 色（おじゃまぷよなし）でも NP 完全である．

In this paper, we investigate the computational complexity of a generalized variant of Puyopuyo. The variant generalizes the size of the board and the number of colors but falling pairs of puyos are given in the offline manner. We focus on two problems of the generalized Puyopuyo; board clearing and maximizing chains. Both problems are already known to be NP-hard. More precisely, the former is NP-complete even for puyos of 2 colors with N-puyo setting, and the latter is NP-hard even for puyos of 4 colors with N-puyo setting. The latter result is mentioned to be improved to the setting of puyos of 3 colors with N-puyo and the setting of puyos of 5 colors without N-puyo, though the detail is not published. In this paper, we strengthen these results from several aspects. Our results are as follows: (1) The chain maximization is NP-hard even for the setting of puyos of 4 colors without N-puyo. (2) The chain maximization for puyos of 3 colors with N-puyo cannot be approximated within any polynomial factor in polynomial time, unless P=NP. (3) The board clearing is NP-complete even for the setting of puyos of 4 colors without N-puyo.