Bejeweled

Description

Bejeweled is a single-player videogame whose game mechanic is based on the idea of swapping adjacent items of a grid in order to for rows or columns 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:

• Bejeweled is played on a board consisting of a $n \times m$ grid where each cell initially contains exactly one out of a set of 6 types of gems.
• Each gem in position $(i,j)$ (row $i$ and column $j$), is considered to be adjacent to its horizontally and vertically adjacent cells, that are $\left( i-1, j \right), \left( i+1, j \right), \left( i, j-1 \right)$ and $\left( i,j+1 \right)$ (with obvious exceptions at the border of the grid).
• A player’s move consists in swapping the positions of two adjacent gems provided that this move cause the vertical or horizontal alignment of three or more adjacent gems of the same kind.
• When three or more adjacent gems of the same kind end up being vertically or horizontally aligned, they pop at the same time, awarding some points to the player and disappearing from the board; the cells left empty are immediately filled with the above gems that fall towards the bottom of the grid; moreover, as gems fall, the empty cells at the top of the column are filled with newly generated gems. The whole process is repeated until there are no more gems that pop.

Computational complexity

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

• Is there a sequence of moves that allows the player to pop a specific gem?
• Can the player get a score of at least $x$?
• Can the player get a score of at least $x$ in less than $k$ moves?
• Can the player cause at least $x$ gems to pop?
• Can the player play for at least $x$ turns?

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.

@misc{cog:bejeweled,
    author = "{CoG contributors}",
    title  = "{Bejeweled --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/bejeweled/",
    note   = "[Online; accessed 2024-04-13]"
}