Candy Crush

A variant of Bejeweled.

Description

Candy Crush Saga is a single-player videogame whose game mechanic is based on the idea of swapping adjacent items of a grid in order to form rows or columns of multiple items of the same kind. It can be considered a variant of Bejeweled.

Computational Complexity

See the CoG page on Bejeweled.

Notes

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

References

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

@misc{cog:candycrush,
    author = "{CoG contributors}",
    title  = "{Candy Crush --- Complexity of Games}",
    year   = "2021",
    url    = "https://www.isnphard.com/i/candycrush/",
    note   = "[Online; accessed 2021-05-03]"
}