I'm trying to write a solver in C# .NET for a game known as Flowerz. For your reference, you can play it on MSN, here: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz

In short, its rules are like this:

• There's a queue filled with coloured flowers. Its length is arbitrary
  • The queue cannot be influenced
• The queue is generated at the start of the level
• The goal of the game is to create matches of three (or more) of the same colour
  • You win the round when the queue is empty and there's at least one empty space left over
• Flowers have either one or two colours.
  • If there are two colours, then there's an outer colour, and an inner colour. In the case of two colours, the outer colour is used for matching.
  • If there is a match, then the outer colour disappears and the flower is now a single colour flower with the same colour as the inner flower
• Cascading matches are possible. A cascade is when three (or more) outer flowers disappear, and when their inner colours form another chain of 3 (or more flowers).
• The playing field is always 7x7
• Some spaces on the field are covered by rocks
  • You can't place flowers on rocks
• The queue can also contain a spade which you can use to move any placed flower to an unoccupied space
  • You have to use the spade, but you don't actually have to move the flower: it's perfectly legal to place it right back from where it came
• The queue can also contain a coloured butterfly. When you use this butterfly on a flower, then the flower gets the colour of the butterfly
  • Applying a butterfly to a flower with two colours, results in the flower getting only a single colour, namely that of the butterfly
  • You can waste the butterfly on an empty space or a flower which already has this colour
• Clearing the field does not win the game

The goal of the solver is simple: find a way to empty the queue, with as many leftover spaces as possible. Basically, the AI places the game for me. The output of the solver is a list with moves it found. I'm not interested in score, but in surviving as long as possible.

Needless to say, the search space grows quickly the larger the queue gets, so a brute force is out of the question. The queue starts at 15, and grows with 5 every two or three levels, if I remember right. And, of course, placing the first flower on (0,0) and the second on (0,1) is different from placing the first one on (1,0) and the second flower on (0,0), especially when the field is already populated with flowers from an earlier round. Such a simple decision could make the difference in making it or not.

The questions I have are the following:

• What kind of problem is this? (think travelling salesman, knapsack, or some other combinatorial problem). Knowing this could make my Google-fu a tad better.
• What kind of algorithm could give me good results, fast?

Regarding the latter: At first, I tried to write my own heuristic algorithm (basically: how would I solve it, if I knew queue?), but that results in a lot of edge cases and scoring matching that I might miss.

I was thinking of using a genetic algorithm (because I at least know how to use that...), but I'm having some problems deciding on a binary representation of the board. Then there's the crossover issue, but that can be solved with an ordered crossover operator or some sorts.

My guess is that the solver must always know the board configuration and the queue it's trying to empty.

I know of a few other heuristic algorithms such as neural networks and fuzzy logic systems, but I lack the experience to know which one is best applicable, or if there are others better suited.