How to optimally solve the flood fill puzzle?
I like playing the puzzle game Flood-It, which can be played online at:
https://www.lemoda.net/javascript/flood-it/game.html
It's also available as an iGoogle gadget. The aim is to fill the whole board with the least number of successive flood-fills.
I'm trying to write a program which can solve this puzzle optimally. What's the best way to approach this problem? Ideally I want to use the A* algorithm, but I have no idea what should be the function estimating the number of steps left. I did write a program which conducted a depth-4 brute force search to maximize the filled area. It worked reasonably well and beat me in solving the puzzle, but I'm not completely satisfied with that algorithm.
Any suggestions? Thanks in advance.
Answer
As a heuristic, you could construct a graph where each node represents a set of contiguous, same-colour squares, and each node is connected to those it touches. (Each edge weighted as 1). You could then use a path-finding algorithm to calculate the "distance" from the top left to all other nodes. Then, by looking the results of flood-filling using each of the other 5 colours, determine which one minimizes the distance to the "furthest" node, since that will likely be your bottleneck.
Add the result of that calculation to the number of fills done so far, and use that as your A* heuristic.