So I started making a new game early this morning (obviously with a little bit of inspiration), and here's what I came up with. Obviously it's far from complete, but I'm releasing this for one reason: I am wondering if anyone can help me figure out a way to make sure a puzzle is always solvable in x moves (you'll see what I mean when you play the game). I'm still pondering an algorithm for it, personally, but if anyone else has an idea, that'd be wonderful!

Since this is just the gameplay itself, I should list what I plan to do with it too, huh?
In the future, I'd like:
  • scorekeeping. I've thought of a way to do it, it's just a matter of, well, doing it.
  • sounds. Inspired a bit by Chime and Matrix.swf, I think I can do some pretty neat things with sound.
  • difficulty modes. It's already built in, but an option to choose them isn't really shown.
  • color selection. By this, I mean being able to choose how many colors are present.
  • game modes. I came up with two typical game modes: progressive and traditional. Progressive puzzles would start with 2 colors, and work their way up to the max, whatever it may be. Traditional games would choose how many colors are present.

Obligatory screenshot:

Overall, I'd say it's pretty ambitious. If I follow release early, release often, it's not nearly as bad than if I were to try to cram all of that into the first release. It'd never get done, like some other unnamed project I got bored of after working on it for a week.
Do you want a reasonable upper bound on the number of moves it takes to solve a puzzle, or to generate a puzzle solvable within X moves?
Reasonable upper bound, so I can adjust the bound based on the difficulty.
Have the computer simulate a round using the following heuristic:

1. Count, for each color, how many squares of its color would be on the map after one move of that color.
2. Find the color with maximum yield, and simulate playing that color.
3. Repeat until game is solved.

The number of moves it took to solve the game would probably be a reasonable upper bound.
I'm not sure if the heuristic I gave simulates perfect play, so if you're not concerned about speed you can also try something like A* pathfinding (with the same heuristic) for the exact number of moves.
I like it. Very addictive :D