Will a greedy algorithm solve Tatham's Flood?

Question

I was just investigating some of the puzzles on Simon Tatham's website, and came across Flood, in which we start with an $n\times n$ grid of cells each of which is filled with one of $k$ predetermined colours, and (quoting the game instructions):

Try to get the whole grid to be the same colour within the given number of moves, by repeatedly flood-filling the top left corner in different colours.

Click in a square to flood-fill the top left corner with that square's colour.

My strategy for doing this is to use a simple 'greedy algorithm'. At each stage:

• consider the single-colour block which starts from the top left corner
• count the number of cells of each colour which are adjacent to this block (i.e. which will become part of the block if we flood-fill with that colour)
• pick the colour such that this number is maximal, and flood-fill with that colour.

For example, in a position such as this:

... flood-filling blue would gain us 4 cells, purple would gain us 5, red 3, yellow 2, and orange 2, so we choose purple.

---

Is this algorithm always optimal? If so, is there a nice proof of its optimality? If not, what is the optimal algorithm for making the whole grid monochromatic as fast as possible?

_{Disclaimer: I don't know the answer to this question. Also, I'm not completely confident that I've explained the algorithm well enough - please leave a comment if it's not clear, and I'll try to improve it.}

Answer 1

A normal greedy algorithm, as TheGreatEscaper has demonstrated, can be quite inefficient for some arrangements.

But there may be value in a greedy algorithm which values percentage of a colour removed, rather than merely number of cells removed. For example, in TheGreatEscaper's example, you have three choices - red, yellow, or orange. Choosing red will clear ~17% of the red on the board. Choosing yellow will clear ~50% of the yellow on the board. But choosing orange will clear 100% of the orange on the board. Therefore, there is no value in delaying the choice of orange.

I doubt even this approach would end up being guaranteed to be optimal. But I would expect it to perform better than the naive cell-count approach.

Even better would be if a multi-step greedy algorithm were applied - a greedy algorithm that looks more than one step at a time.

For instance, with a two-step algorithm, you'd look at the next two colours. So for example, using TheGreatEscaper's example, if you look only one step (using a cell-count approach), you get one cleared for each of red and orange, and two for yellow. With a two-step approach, the sequence orange-yellow, red-yellow, and yellow-Lgreen all clear 5 cells, whereas other choice pairs give fewer cells.

Using this, along with percentages, would stabilise the sequence, avoiding many of the pitfalls that the naive approach gives, although it probably won't be completely optimal.

Imagine TheGreatEscaper's example, but with orange replacing the dark blue at the far edges.

In this case, the sequence using the naive approach will go yellow (2), Lgreen (3), Dgreen (4), blue (5), orange (7), red (6), blue (5), Dgreen (4), Lgreen (3), yellow (2) - 10 steps.

If using a simple percentage approach (with a tie broken by count), it will go yellow (50%), Lgreen (50%), Dgreen (50%, 4), red (~67%), blue (100%, 10), orange (100%, 13), Lgreen (100%, 3), yellow (100%, 2), red (100%, 2) - 9 steps.

If using a percentage approach with two-step greediness, it will go red (~117%), yellow (200%), Lgreen (200%), Dgreen (200%), blue(200%), orange(200%), red - 7 steps.

Answer 2

It's definitely not optimal! Here's a counterexample:

Start from the white area. Greedy algorithm would make you do all the colours on the top right (5 moves: yellow, green, dark green, blue, dark blue), then the red (1) and then all the other colours (6 moves), making a total of 12 moves.

There is an obviously more efficient method: orange, yellow, green, dark green, blue, dark blue, red, needing only 7 moves.

I don't think there's a simple algorithm to solve flood apart from a breadth first search which will bash out every possible case, since too much optimization relies on evaluating the entire grid.

---

EDIT: I think I should clarify what a breadth first search is, as it appears it's a programmer-centric term.

Breadth first search works through the following ways: - Only try colours that will increase your area - Store every possible state after n moves - Throw away states that are strictly inefficient - If you're a clever programmer, you can throw away some more states :).

The states stored for n = 2 are (Y,g), (Y,O), (Y,R), (O,Y), (O,R), (R,O), (R,Y).
The area (Y,O) covers is a strict subset of (O,Y) so it can be removed. (O,R) Identical to (R,O).
So we're left with (Y,g), (Y,R), (O,Y), (O,R), (R,Y).
An optional clever shortcut is to throw out (Y,R) by comparing it to (R,Y) topologically, and how any solution with Y,R can be beaten by R,Y, but that requires a lot more programming work. It'll naturally die out later down the search.
So a good breadth first search will only store (Y,g), (O,Y), (O,R), and (R,Y), for 2 move possibilities.

Basically, the first time a set of n moves turns the board into one colour, the breadth first search is done.
With a little bit of programming knowledge, it's the easiest way to 'solve' a game like flood.

Answer 3

That problem is NP-hard, so an efficient strategy to calculate the optimal moves would be a major breakthrough in computer science. Of course, there might be a greedy strategy, but not an efficient one, e.g. that works in exponential time.

To prove that it really is NP-hard, we will reduce vertex cover to your problem.

Let $G$ be the input graph. We will use $|V|+1$ colors, one for each vertex, and one "border color" (diagram below uses gray). First, for each edge, put $|V|$ squares in a row using the colors of the vertices, and then surround it with a border. Then surround it again, each half of the perimeter with the colors of incident vertices.

To explain the intuition behind the construction, let us make three observations:

• for any valid flooding sequence it is sufficient to perform only one border-color flood, namely the one that removes the last tile of border-color;
• after the border-color flood, we will still have to flood all the colors of other vertices, so it is suboptimal to flood any "unnecessary" vertices colors before all the border-color tiles has been removed;
• by the construction of puzzle instance, exactly the colors of vertices corresponding to a vertex cover are necessary, that is, for any edge at least one of incident vertices is in the cover.

To complete the proof we have to show that an optimal puzzle solution corresponds to an optimal solution of minimum vertex cover. In other words, we show that any flooding sequence can be transformed into valid vertex cover in $G$, and that for any vertex cover in $G$ there is an appropriate puzzle flooding sequence.

Given a flooding sequence we take vertex $v$ into the cover if its color has been flooded before the last tile of border color has been removed. The size of the cover is at most $|C| \leq k-|V|-1$ where $k$ is the length of the sequence. Observe that to remove border color tiles of each "edge" we had to flood at least one of its outer colors, in other words, each edge will have at least one incident vertex in the cover, as required.

Given a valid vertex cover, the corresponding flooding strategy is to first flood the cover-colors, then border, and then again all the vertex colors. It's size is $k = |C|+|V|+1$ where $C$ is the vertex cover used. Note that this number matches the bound from the previous paragraph, that is, strictly shorter flooding sequence implies strictly smaller vertex cover.

I hope this helps $\ddot\smile$

Answer 4

If you redefine the metric of greediness, you might find a more efficient algorithm.

I've been playing around with the following greedy algorithm and had consistent success with random harder puzzles. I've only tried it for a handful of puzzles but it usually results in fewer moves than the autosolver provided by the site. It's not optimal, but it can probably be proven to be better or equivalent to picking the option that clears the most cells.

Maximizing the number of cells unlocked by your move is the greedy strategy. It's still not optimal, because it fails to provide the optimal solution in the case provided by TheGreatEscaper.

At each step make the choice that maximizes the reach of the flood. So choosing the option that exposes the most new cells to flood. Options should be weighted to those exposing clusters (which would likely expose the reach even further on a following move). I found this could be achieved by adding each cell in a cluster that would have an exposed side after choosing your colour.

Put into other words, maximize the total number of cells that could be cleared by all choices for the following move.

Tie breaker should reevaluate the state after each tied option

It's not optimal but it would up solving TheGreatEscaper's scenario in one move more than the optimal solution.

In the given example, you would choose purple, not because it clears 5 squares, but because it opens up 10. Orange would open up 6, blue opens 5, yellow opens 3, and red only opens 1.

Answer 5

It seems like a possible optimal strategy would be:

• If an entire color scheme can be eliminated with the next flood choice, choose that color

• Else: select the color that increases the surface area/border length between the current $\left( f_n \right )$ and next step $\left( f_{n+1} \right)$

In this case, surface area would be defined in a more practical sense than just the unit length of the total edges of the flood. It would be a count of the total number of blocks touching the flood, which prevents double counting and ignores the edges of the playing board.

This is different from the greedy algorithm in that counting the touching blocks maximizes only the increase in the flood's size this turn, whereas the surface area I defined would increase the flood's ability to grow in subsequent turns, optimizing growth throughout the game.

This method will not always be optimum, also. There are cases where sacrificing turns for a more strategic and rewarding flood in the future would be optimum. If we ran thousands of simulations to compare the a) average time of computation and b) number of turns until success for i) this simple algorithm and ii) a machine learning model or backtracking model, we could compare the tradeoff between the two. I think that if the board's starting points are generated randomly, this quick algorithm would still work pretty well.

Answer 6

Using a greedy algorithm usually gets you to a nearly optimal solution, or even optimal, but it's no ensured. If you want to find the solution that gets you to solve the puzzle in minimum moves (that is, the optimal solution), I would recommend you, if you're willing to learn it, of course, getting started with a bactracking algorithm. It will compare all possible solutions and return you the best. Once you have it, it's easy to modify it to obtain a branch and bound algorithm, wich will solve the problem more efficiently, ensuring you always have the optimal solution.

In case you only want a solution, yeah, a greedy algorithm usually does your work.

Here is a good starting point about backtracking: http://algorithms.tutorialhorizon.com/introduction-to-backtracking-programming/