Rand al'Thor
• 112.6k
• 22
• 307
• 605

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.

Is this algorithm always optimal? If so For example, is therein a nice proof of its optimality? If not, what is the optimal algorithm for making the whole grid monochromatic as fastposition such as possible?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.

Rand al'Thor
• 112.6k
• 22
• 307
• 605

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

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.