Howdy, Stranger!

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

Categories

Solving SameGame aka Clickomania

stefek99stefek99 Member Posts: 2
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

  • BitByBit_ThorBitByBit_Thor Member Posts: 2,444
    : 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
  • stefek99stefek99 Member Posts: 2
    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.