31
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ After playing the game for a few minutes I can think of an instance where it wouldn't be optimal: when the most popular-colored block(s) is/are completely encapsulated by the "flood" block. So this colored block would have the most contact with the flood block, but not necessarily expand the flood block's reach if changed to that color. I think more optimal algorithm would be to select the color that reaches the most blocks, so looking two steps ahead rather than one. But your algorithm works because the highest block count will generally connect to the most blocks. $\endgroup$ – econoMichael Dec 13 '16 at 0:07
  • 15
    $\begingroup$ Solving this game is NP-Hard, so there probably aren't any clever algorithms which find the optimal solution quickly. arxiv.org/abs/1001.4420 $\endgroup$ – Mike Earnest Dec 13 '16 at 0:13
  • $\begingroup$ @MikeEarnest Thanks, very interesting! $\endgroup$ – Rand al'Thor Dec 13 '16 at 1:13
  • $\begingroup$ @MikeEarnest you should make that an answer. $\endgroup$ – Taemyr Dec 13 '16 at 9:04
  • $\begingroup$ The answer to the title question is obviously "yes". ;) $\endgroup$ – Ian MacDonald Dec 14 '16 at 18:17
7
$\begingroup$

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.

$\endgroup$
40
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Why does the greedy algorithm force you to begin with yellow? It looks to me as if it would equally well choose orange, in which case everything goes nicely. (But if we just duplicate your example's first row, we get an example where the greedy algorithm does force you to begin with yellow.) $\endgroup$ – Gareth McCaughan Dec 14 '16 at 15:04
  • 2
    $\begingroup$ @GarethMcCaughan You gain two squares of area with yellow, one square with orange. Additionally, if an algorithm has decisions where they can 'equally well choose' different options, which might not actually lead to an optimal solution, it can hardly be called optimal anyways. $\endgroup$ – TheGreatEscaper Dec 14 '16 at 15:47
  • $\begingroup$ oh, sorry, I'm a twit. I was thinking the greedy algorithm was picking whatever colour has most cells immediately adjacent to the top-left region, which is of course complete nonense. My apologies. $\endgroup$ – Gareth McCaughan Dec 14 '16 at 15:53
38
$\begingroup$

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.

example diagram

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$

$\endgroup$
  • 2
    $\begingroup$ It seems that e1 and e2 have traded places in your puzzle. In the graph, e2 is the one with no yellow. $\endgroup$ – Wumpus Q. Wumbley Dec 13 '16 at 19:31
  • 1
    $\begingroup$ This is a great answer, although it took me a long time to work out the proof's conclusion based on the last paragraph. Perhaps it's just me but I think the current wording uses vertex covering as a solution for Tatham's Flood, implying the reduction backwards, whereas it'd make more sense to establish how the constructed Tatham's Flood could be used to solve vertex cover (i.e. you must select only the required colours to touch every border => select only the vertices required to touch every edge of the graph, and not the opposite). $\endgroup$ – meiamsome Dec 14 '16 at 6:52
  • $\begingroup$ @WumpusQ.Wumbley Fixed now, thanks for noticing. $\endgroup$ – dtldarek Dec 14 '16 at 9:39
  • $\begingroup$ @meiamsome One has to show that an optimal puzzle solution produces an optimal vertex cover and effective way to do this is to show that any vertex cover (in particular minimum vertex cover) can be transformed into valid flooding strategy of corresponding length (here $|C| + |V| + 1$). Although I agree, I could have written it more clearly, maybe the newer version will suit you better. $\endgroup$ – dtldarek Dec 14 '16 at 9:45
  • 1
    $\begingroup$ Awesome reduction and awesome visual explanation! But I notice that your reduction requires $k = |V|+1$ colors to encode a graph of size $V$. If Tatham's Flood permits $n$ (the size of the grid) to increase unboundedly, but caps $k$ (the number of colors) at let's say $k=7$, can we still come up with a reduction from vertex cover, or is it possible that Tatham's Flood becomes easier than vertex cover at that point? $\endgroup$ – Quuxplusone Dec 21 '18 at 5:14
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ^vote with a note: Very nice improvement, though I was distracted at first by the word "area" in "surface area," as we are already talking about filled in "areas." It is more distinctly a "boundary/border/interface/frontier length/size" (measured by the number of blocks, not edges), if I understand correctly. $\endgroup$ – humn Dec 15 '16 at 22:01
  • $\begingroup$ Yep, "border length" would be more specific in this case. I am used to the more non-dimensionalized "surface area" I've been taught to describe the outer boundary for any R^n $\endgroup$ – Max Hoffman Dec 16 '16 at 4:40
2
$\begingroup$

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/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.