Hardness Results on Generalized Puyo Puyo

Puyo Puyo is a Tetris-like falling-block video game, which has been played in Japan more than 30 years. In Tetris, tetrominoes fall on the board, whereas colored and colorless “puyo”s fall in Puyo Puyo. The clearing rule in Tetris is to fill a line (row) of the board, whereas that in Puyo Puyo is to make a cluster with a size of at least 4 puyos with a single color. A colorless puyo is cleared only when a colored puyo touching it is cleared. Due to this clearing rule, a clearing chain phenomenon arises, which is a unique nature of Puyo Puyo. In this paper, we investigate the computational complexity of a generalized Puyo Puyo, where the size of the board and the number of colors are arbitrary, but the falling sequence of puyos is given in an offline manner. We focus on two algorithmic problems in the generalized Puyo Puyo. One is the problem of finding a clearing chain with the longest length for a given board and a falling sequence of puyos, and the other is the problem of deciding whether a given board and a falling sequence of puyos can clear all the puyos, or not. Both problems are already known to be NP-complete. The former problem, the longest clearing chain problem, is shown to be NP-complete even if the number of colors is 4. The latter problem, the all-clear problem, is also shown to be NP-complete even if the number of colors is 2. In this paper, we strengthen these results: (1) The longest clearing chain problem is NP-complete even if the number of colors is 2. (2) The longest clearing chain cannot be approximated within a factor better than any polynomial of the falling sequence length in polynomial time unless P = NP.