Sign in to follow this  
KlimBo_BG

Clickomania Algorithm

Recommended Posts

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!

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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 ;-))

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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!!!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this