added 244 characters in body
Source Link
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:

example

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

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.

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:

example

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

Source Link
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.