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.