Clickomania Algorithm

This topic is 4865 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 on other sites
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]

Share on other sites
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

Share on other sites
Thank you, spurious_interrupt!

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 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!

Share on other sites
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 on other sites
Where's the competition located? I tried to solve this problem myself once.

1. 1
2. 2
3. 3
4. 4
Rutin
13
5. 5

• 15
• 10
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633693
• Total Posts
3013358
×