logobossstupid

I like playing the puzzle game Flood-It, which can be played online at:

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.

10 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.

After playing the game a few times, I noticed that a good strategy is to always go 'deep', to go for the colour which goes farthest into the unflooded territory.

A naive 'greedy' algorithm is to pick the next step that maximizes the overall perimeter of the main region.

(A couple of smart friends of mine were thinking about this the other day and decided the optimium may be NP-hard (e.g. you must brute force it) - I do not know if they're correct (wasn't around to hear the reasoning and haven't thought through it myself).)

Note that for computing steps, I presume the union-find algorithm is your friend, it makes computing 'one step' very fast (see e.g. this blog post).

A* is just a prioritized graph search. Each node is a game state, you rank nodes based on some heuristic, and always expand the lowest-expected-final-cost node. As long as your heuristic doesn't underestimate costs, the first solution you find is guaranteed to be optimal.

After playing the games a few times, I found that trying to drill to the opposite corner then all corners tended to result in a win. So a good starting cost estimate would be (cost so far) + a sufficient number of fills to reach the opposite corner [note: not minimum, just sufficient. Just greedily fill towards the corner to compute the heuristic].

I have been working on this, and after I got my solver working I took a look at the approaches others had taken.

Most of the solvers out there are heuristic and do not guarantee optimality. Heuristics look at the number of squares and distribution of colors left unchosen, or the distance to the 'farthest away' square. Combining a good heuristic with bounded DFS (or BFS with lookahead) results in solutions that are quite fast for the standard 14x14 grid.

I took a slightly different approach because I was interested in finding the provably optimal path, not just a 'good' one. I observed that the search space actually grows much slower than the branching factor of the search tree, because there are quite a lot of duplicate positions. (With a depth-first strategy it is therefore important to maintain a history to avoid a redundant work.) The effective branching factor seems closer to 3 than to 5.

The search strategy I took is to perform BFS up to a 'midpoint' depth where the number of states would become infeasible, somewhere between 11 and 13 moves works best. Then, I examine each state at the midpoint depth and perform a new BFS starting with that as the root. Both of these BFS searches can be pruned by eliminating states found in previous depths, and the latter search can be bounded by the depth of the best-known solution. (A heuristic applied to the order of the subtrees examined in the second step would probably help some, as well.)

The other pruning technique which proved to be key to a fast solver is simply checking whether there are more than N colors left, if you are N or fewer steps away from the current best solution.

Once we know which midpoint state is on the path to an optimal solution, the program can perform DFS using that midpoint state as a goal (and pruning any path that selects a square not in the midpoint.) Or, it might be feasible to just build up the paths in the BFS steps, at the cost of some additional memory.

My solver is not super-fast but it can find a guaranteed optimal solution in no more than a couple minutes. (See http://markgritter.livejournal.com/673948.html, or the code at http://pastebin.com/ZcrS286b.)

Smashery's answer can be slightly tweaked. For the total number of moves estimate, if there are 'k' colors at maximum distance, add 'k-1' to the number of moves estimate.

More generally, for each color, consider the maximum distance at which the color can be cleared. This gives us a dictionary mapping some maximum distances to a non-zero number of colors that can be cleared at that distance. Sum value-1 across the keys and add this to the maximum distance to get a number of moves estimate.

Also, there are certain free cases. If at any point we can clear a color in one move, we can take that move without considering the other moves.

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.

I think you could consider the number of squares that match or don't match the current color. So, your heuristic measure of 'distance' would be the number of squares on the board that are -not- the same color as your chosen color, rather than the number of steps.

A naive heuristic could be to use the number of colours left (minus 1) - this is admissible because it will take at least that many clicks to clear off the board.

I'm not certain, but I'm fairly sure that this could be solved greedily. You're trying to reduce the number of color fields to 1, so reducing more color fields earlier shouldn't be any less efficient than reducing fewer earlier.

1) Define a collection of existing like-colored groups.

2) For each collection, count the number of neighboring collections by color. The largest count of neighboring collections with a single color is the weight of this collection.

3) Take the collection with the highest count of neighbors with a single color, and fill it to that color. Merge the collections, and update the sort for all the collections affected by the merge (all the new neighbors of the merged collection).

Overall, I think this should actually compute in O(n log n) time, where n is the number of pixels and the log(n) only comes from maintaining the sorted list of weights.

I'm not sure if there needs to be a tie-breaker for when multiple fields have the same weight though. Maybe the tie-breaker goes to the color that's common to the most groups on the map.

Anyway, note that the goal of the game is to reduce the number of distinct color fields and not to maximize the perimeter, as different color schemes can occasionally make a larger field a sub-optimal choice. Consider the field:

3 3 3 3 3

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

1 2 2 2 2

The color 1 has the largest perimeter by any measure, but the color 2 is the optimal choice.

EDIT>

Scratch that. The example:

3 1 3 1 3

1 1 1 1 1

1 1 1 1 1

2 2 2 2 2

1 2 2 2 2

Invalidates my own greedy algorithm. But I'm not convinced that this is a simple graph traversal, since changing to a color shared by 2 neighbors visits 2 nodes, and not 1.

Color elimination should probably play some role in the heuristic.

1) It is never correct to fill with a color that is not already on the graph.

2) If there is one color field with a unique color, at least one fill will be required for it. It cannot be bundled with any other fills. I think this means that it's safe to fill it sooner rather than later.

3) The greedy algorithm for neighbor field count makes sense for a 2 color map.

Not the answer you're looking for? Browse other questions tagged algorithmsearchartificial-intelligencea-starflood-fill or ask your own question.