Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at least one common edge with another same-coloured cell. A group of s$\geq$k cells can be "popped" i.e. removed from the field and a player is assigned a score for it. When a group is removed, the remaining cells are displaced s.t. no cell has an empty cell underneath it (basically, remaining cells "fall down"). If a column vanishes as a result of popping, every non-empty column to the left of it is displaced one cell to the right. The game ends when there are no groups left on the field. The score is a function of s, and in the end a cumulative score is calculated. The aim of the game is to get maximum cumulative score.
The question is if there is an algorithm that allows to calculate maximum possible end score for a given starting arrangement of cells? I suspect it has something to do with graph searching, but I have little experience with such things. Can anyone please suggest how can one approach such kind of a problem? I have also thought about doing something with cellular automata, but I really doubt this approach (however fun it might be).
This often goes by the name 'Clickomania' or, apparently, 'Same Game'; I'm not sure how much people have studied the optimization version you list, but it's known that determining whether a grid can be completely solved or not is NP-complete as soon as you get to sufficient amounts of colors and columns. See Eric Demaine's page at http://erikdemaine.org/clickomania/ for more details of the result, including a link to the original paper proving the NP-Completeness result and a few basic results on optimization in the $n\times 1$ grid case; alternately, you can find the paper on the arXiv.