Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 857
felix Avatar asked Sep 16 '09 04:09

felix


People also ask

How are flood fill algorithms implemented?

In fill algorithm, we start from a specified interior point (x, y) and reassign all pixel values are currently set to a given interior color with the desired color. Using either a 4-connected or 8-connected approaches, we then step through pixel positions until all interior points have been repainted.


1 Answers

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.

like image 169
Smashery Avatar answered Sep 21 '22 17:09

Smashery