Solving SameGame aka Clickomania

Does anyone know any algorithm which solves this game? (http://en.wikipedia.org/wiki/SameGame)

I know that this is a NP-Complete problem but maybe exists some approximate methods.

This is task on my studies and basic (obligatory) version states, that the gamefield is 10x10 and there is always a full solution (none blocks left).

I really appreciate your help.



Comments

  • : Does anyone know any algorithm which solves this game?
    : (http://en.wikipedia.org/wiki/SameGame)
    :

    Hmm, brute force?

    : I know that this is a NP-Complete problem but maybe exists some
    : approximate methods.
    :
    : This is task on my studies and basic (obligatory) version states,
    : that the gamefield is 10x10 and there is always a full solution
    : (none blocks left).
    :
    : I really appreciate your help.
    :

    For a totally filled 10x10 gamefield, there are max 50 possibilities for the first move. So, atleast there are no more 50! ways of solving (I know, I know... I'm not really helping here).

    A smarter solution would be to only select moves that cause more color-convergence (i.e., after the move, the amount of blocks n
  • Thank you for a piece of advice.

    I forgot about one serious issue which distinguish my problem from regular game... That is - columns don't swap left after when one is cleared.

    This simplifies the problem but I still don't know how what improvements can be applied to the brute force method.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories