*Shariki*is a puzzle game developed by the russian programmer

**Eugene Alemzhin**in 1994. The rules are simple:

(...) matching three or more balls of the same color in line (vertical or horizontal). These balls then explode and a new ones appear in their place.The first

*Shariki*'s clone is

*Tetris Attack*, a fusion between

*Shariki*and the most famous

*Tetris*, also this developed in Soviet Union by

**Alexey Pajitnov**. But the most famous clone is

*Bejeweled*(2001) by PopCap Games, from which is derived the

*Candy Crush Saga*. During this March,

**Toby Walsh**and the italian team composed by

**Luciano Gualà**,

**Stefano Leucci**,

**Emanuele Natale**proved that

*Candy Crush*and other similar games are NP-hard:

The twentieth century has seen the rise of a new type of video games targeted at a mass audience of "casual" gamers. Many of these games require the player to swap items in order to form matches of three and are collectively known asThe italian team realized also a web-based implementation of their technique.tile-matching match-three games. Among these, the most influential one is arguablyBejeweledin which the matched items (gems) pop and the above gems fall in their place.Bejeweledhas been ported to many different platforms and influenced an incredible number of similar games. Very recently one of them, namedCandy Crush Sagaenjoyed a huge popularity and quickly went viral on social networks. We generalize this kind of games by only parameterizing the size of the board, while all the other elements (such as the rules or the number of gems) remain unchanged. Then, we prove that answering many natural questions regarding such games is actuallyNP-Hard. These questions include determining if the player can reach a certain score, play for a certain number of turns, and others.

Toby Walsh (2014). Candy Crush is NP-hard, arXiv: 1403.1911v1

Luciano Gualà, Stefano Leucci & Emanuele Natale (2014). Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard, arXiv: 1403.5830v1