Bejeweled

A player swaps adjacent items in a $n \times m$ grid in order to form as many matches of three as possible.

Description

Bejeweled is a signle-player videogame whose game mechanic is based on the idea of swapping adjacent items of a grid in order to for rows or colums of multiple items of the same kind. Candy Crush Saga and other match-three games [1] may be considered generalization of it.

The rules of the game are the following:

Computational complexity

Answering any of the following questions has been proven to be an NP-Complete problem [2]:

Notes

A playable version of the NP-hardness reduction of [2] is available here.

References

[1] J. Juul, “A casual revolution: Reinventing video games and their players”, 2012.

[2] L. Gualà, S. Leucci, E. Natale, “Bejeweled, Candy Crush and other match-three games are (NP-)hard”, in CIG 2014.