The solution of following problem is very important for me!!! I need of a competitive algorithm, which play the game "Clickomania" (or "Same Game"). Finding the best solution for appeared to be a NP-complete problem, as I read in a scientific paper, analyzing Clickomania complexity. This is a little abstract from a paper called "The Complexity of Clickomania" in "More Games of No Chance" (http://theory.lcs.mit.edu/~edemaine/papers/ClickomaniaGameTheory2000/paper.ps): We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes a chosen connected monochromatic group of at least two square blocks, and any blocks above it fall down. We show that one-column puzzles can be solved, i.e., the maximum possible number of blocks can be removed, in linear time for two colors, and in polynomial time for an arbitrary number of colors. On the other hand, deciding whether a puzzle is solvable (all blocks can be removed) is NP-complete for two columns and five colors, or five columns and three colors. The following lines are about the specification of my problem: I have a square table with size N x M (0<N<51, 0<M<51) and it's divided into N X M squares. Each of this squares have value(color from 1 to 7). If you can help me with an algorithm, which finding a competitive solution, I'll be much thankful. Thank you!

My program has the current hi-score for JT's Blocks on Yahoo. ( 14 x 9 grid, 5 colors ).

What do you want to know about the algoryhthm?

[Edited by - spurious_interrupt on July 10, 2005 11:22:22 AM]

I want to know how algorithm works - step by step. If you want, you can send me source code with comments or some help(theory) about this topic ;-))

edit

Thank you, spurious_interrupt!

Hi.

What do you mean by a competitive solution?
Do you want an algorithm that allways clears the intire board?
Do you want an algorithm that allways gives you the max amount of points(specify rules)?
Do you want an algorithm that gives you good results with little cpu usage?

I want an algorithm that allways gives me the max amount of points. The rules are:
When you clear a region which consists of N squares you get (N-1)^2 points. If you clear all squares of the board, your current (POINTS) will be (2*POINTS). Exuse me for my bad English, please!

In the meantime, if somebody can help me with other opinion about this problem, I'll be pleased to "hear" him ;-))

Come on, Klimbo, this is a programming contest problem and you are supposed to work the problem out on your own. Reading all the present literature on the net is fine, but asking people around the programming and ai forums here and there (http://www.ai-forum.org/topic.asp?forum_id=1&topic_id=16442) to help you out is a miserable cheating attempt. Have some self-respect!!!