strategy - Will a greedy algorithm solve Tatham's Flood?

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

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.