How to optimally solve the flood fill puzzle?

user_3623956 0
Viewed 19959

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.

flood-fill a-star artificial-intelligence search algorithm
10 Answers

Here's an idea for implementing the graph to support Smashery's heuristic.

Represent each group of contiguous, same-colour squares in a disjoint set, and a list of adjacent groups of squares. A flood fill merges a set to all its adjacent sets, and merges the adjacency lists. This implicit graph structure will let you find the distance from the upper left corner to the farthest node.

user_207540
Related