# 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:

- 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.