Computer Science Department
The Complexity of Clickomania
Alexander Iliev
In this project I will explore different approaches to solve the puzzle known variously as Clickomania and Same Game. The rules of the game are simple. You are given a grid of size NxM. Initially, each cell/tile in the grid is colored in one of K different colors. Neighboring cells of the same color form groups. At each move, the player can click on a group of at least 2 cells, which results in the disappearance of the group. Cells that are positioned above this region slide down to fill in the hole. In case an entire column has been removed, all cells to the right of the column are shifted one position to the left . When a region of C cells has been removed, the player receives (C-1) credits. In case the player manages to remove all tiles from the grid, his score is doubled. The goal is to maximize the score in the game. Even though the rules are simple and the game is very intuitive, finding the sequence of moves that maximizes your score is an NP-complete problem. In this project I will develop two competing algorithms that give approximate solutions, one using a heuristic function, and the second one using the concepts of machine learning.