Return to Answer

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.

To complete the proof we have to show that minimum vertex cover corresponds to a valid solution in puzzle, and that no strictly better flooding sequence exists. 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 is optimal, because

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

I hope this helps $\ddot\smile$

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.

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$

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.

Minimum vertex cover gives us an optimal strategy: first flood the cover-colors, then border, and then again all the vertex colors. It works, because after flooding the last border color, we will still have to flood all the colors of other vertices, so it is suboptimal to flood any "unnecessary" vertices colors before. Also, it is not optimal to flood border color more than once, as it is sufficient to perform only the last border-color flood.

I hope this helps $\ddot\smile$

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.

To complete the proof we have to show that minimum vertex cover corresponds to a valid solution in puzzle, and that no strictly better flooding sequence exists. 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 is optimal, because

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

I hope this helps $\ddot\smile$

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". First, for each edge, put $|V|$ squares in a row in the colors of the vertices, and then surround it with a border. Then surround each half of the perimeter with the colors of incident vertices.

Minimum vertex cover gives us an optimal strategy: first flood the cover-colors, then border, and then again all the vertex colors. It works, because after flooding the last border color, we will still have to flood all the colors of other vertices, so it is suboptimal to flood any "unnecessary" vertices colors before. Also, it is not optimal to flood border color more than once, it is sufficient to perform only the last border-color flood.

I hope this helps $\ddot\smile$

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.

Minimum vertex cover gives us an optimal strategy: first flood the cover-colors, then border, and then again all the vertex colors. It works, because after flooding the last border color, we will still have to flood all the colors of other vertices, so it is suboptimal to flood any "unnecessary" vertices colors before. Also, it is not optimal to flood border color more than once, as it is sufficient to perform only the last border-color flood.

I hope this helps $\ddot\smile$