Algorithm for optimal moves to solve this puzzle

Question

There is a mobile puzzle game called Puzzle and Dragons that I'm interested in writing a board solver for, just for fun. It has a 5x6 board where each index holds a random color. It is similar to Bejeweled except you try to build a path in one movement that connects the most gems as possible. You have about 4 seconds to connect gems and you can end it early by letting go of the screen. After letting go, gems that are matched will disappear and gems above it will fall down while new random gems appear from the top.

Here is a demonstration of how the game works: http://www.maaak.net/pad/

I did a little bit of research and found out that I'm dealing with clustering problems here. I want to find the sets of the same color and then try to connect them with other sets of other colors.

Could you help me get started on this algorithm? Am I heading in the right direction? What are some specific clustering algorithms that I can try to incorporate?

Answer 1

This does not at all sound like clustering to me.

You may want to look at graph algorithms and constraint solvers instead.

(I'm not sure what, because I do not understand the "simulator" you linked to at all; it also is too large for my screen.)