Jump to content
  • Advertisement
Sign in to follow this  
KlimBo_BG

Clickomania Algorithm

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

If you intended to correct an error in the post then please contact us.

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
Advertisement
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 this post


Link to post
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 ;-))

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!