Flood-it is a game created by LabPixies, which was recently aquired by Google.
The game consists of a board with random colors cells. Let’s call the top-left cell a seed cell and the region connected to the seed cell and with the same color as it, the flooded region. At each round, the player chooses a color for the flooded region which may flood adjacent regions, expanding the flooded region. The final objective is to flood all the board.
In the original game, there are three different sizes of boards: 14, 21 or 28. The number of colors is always 6.
A paper from Clifford, Jalsenius, Montanaro and Sach , presents theoretical results regarding the general version of this problem, where the size of the board and the number of colors can be unbounded.
In this post we’ll highlight the main results of their paper and present an integer linear programming approach to solve it exactly.
For , the game is shown to be NP-hard even if one is allowed to start flooding from an arbitrary cell. The proof given in  is based on a reduction from the shortest common supersequence problem (SCS for short).
There are two greedy approaches one might try:
1. Pick the color that maximizes the number of cells covered.
2. The most frequent color in the perimeter of the current region.
In Figure 2, we have an instance where this strategies can be arbitrarily bad . They use colors while the optimal solution is 3.
Surprisingly, the following naïve strategy:
Cycle through all colors until the board is colored.
gives a solution with a value within a factor of the optimal value.
More specifically, if is the optimal number of movements and the number of available colors, then this algorithm solves the problem with no more than movements. To see why, let be the color sequence of the optimal solution. In the worst case, each cycle covers at least one color in the sequence. Thus, this algorithm is approximated.
This can be refined to observing that the cycle does not need to have the current color of the flooded region.
The authors improve this bound with a randomized algorithm that achieves a expected factor.
They also give a lower bound, proving that if the number of colors is arbitrary, no polynomial time approximated algorithm with a constant factor can exist unless P=NP.
An upper bound for the number of movements required for solving any is given by the following theorem:
Theorem 1: There exists a polynomial time algorithm for Flood-It which can flood any n x n board with C colors in at most moves.
Conversely, we can set an lower bound for a board:
Theorem 2: For , there exists an board with (up to) colors which requires at least moves to flood.
That is, we can’t expect an algorithm to perform much better than the one from Theorem 1 for arbitrary boards.
Integer Linear Programming
Let be the number of colors and an upper bound for the optimal solution. A component is a connected region of pixels with same color, considering 4-adjacency. Two components and are adjacenct if there exists at least a pixel in adjacent to a pixel in .
We denote by the set of components adjacent to component . Let be the set of components and . Furthermore, let be the color of component .
We define the binary variable that is 1 if color is chosen at iteration or 0 otherwise. We also define the binary variable that is 1 if component is filled in some iteration or 0 otherwise.
For simplicity, we’ll assume that the component of the seed cell has index .
(1) Objective function:
(2) For each component ,
(3) For each iteration ,
(4) For each component and iteration ,
(5) For each component and iteration
(6) For each component ,
(7) For the component of seed cell,
(8) For all component and iteration ,
(9) For all color and iteration ,
Constraint (2) states that we fill a component exactly in one iteration. Constraint (3) says that at each iteration we pick at most one color. Constraint (4) allow us to fill a component only if any of its adjacent components has been already filled (which means it currently has the same color as the seed pixel) and if its color is the same as the chosen color (5) .
Finally, constraints (6)-(9) state the variables are binary and each component starts unfilled except the component of the seed cell.
We’ve implemented this model in C++ using the COIN-OR Cbc library. The code is available, as always, on github.
The first task was obtaining “real” instances. I don’t know whether the colors of Flood it! boards are uniformly chosen. Thus, I preferred to take some print screens from the original game and do some image processing to convert it matrices with integer representing colors.
Unfortunately the model is too big if we use as the number of components, . The number of constraints (4) is then and for the instance in Figure 3, .
In order to reduce its size, we tried two tricks.
First, we changed our model a little bit to decrease the number of contraints (4). Now, may also be 1 if component was covered some iteration before . Thus, we can rewrite (4) as,
(4′) For each component ,
But now we need to allow a component to be “covered” if it was covered in a previous iteration, even if the current color does not match. Thus, (5) becomes:
(5′) For each component and iteration
We also need to change (2) equality to inequalities. Now, note that there are constraints (4′).
The second trick is based on the assumption that in general, the optimal number of movements is much less than the number of components. Thus, solve the model for increasing values of starting with the number of colors until we find a feasible solution.
Even with these changes, we were not able to solve the instance in Figure 3. The 5×5 instance obtained from the first rows and cols of the matrix is solved in 2 minutes using 9 colors.
0 0 1 2 2
3 4 0 0 1
0 0 0 2 4
1 3 3 3 4
3 0 4 0 2
1 2 0 1 3 0 3 4 2
For the 6×6 instance obtained the same way, the solver does not find the optimal solution in an hour.
In this post we gave a brief summary of Clifford et al. paper and then presented a integer linear programming approach to solve instances exactly.
As our experimental results showed, even for the smallest boards (14 x 14) we’re not able to obtain optimal solutions in feasible time.
As future work, we may try devising alternative models or find additional inequalities. Another possibility is to solve this same model using a commercial solver like CPLEX.