Flood It: One More Tweak

I found a way to improve the lower bound on the number of moves needed to solve a Flood-It board position.  Basically, we can obtain a lower bound on the earliest time when a color can be cleared.  First, we have to be able to reach all cells containing the color, which is a simple distance measurement.  But next we need to be able to make consistent progress to every furthest cell of the color.

For each of the furthest cells of a color, we can create a distance map for that cell and find the critical paths to reach that furthest cell.  We can then record the different colors at each distance on that critical path.  On each turn, we have to move to one of those colors.  So we have a list of color sets, and we need to take one color from each set on each turn.

For each furthest cell of a color, we can build the list of color sets, and then AND together corresponding sets across the different cells.  If the AND of corresponding sets is empty -- if there is a turn on which no color choice will make progress to every furthest cell -- then we have proven a lower bound for that color that is one more than the furthest distance.

Unfortunately, I didn't implement quite the algorithm described here.  I didn't think up some of the generalities until after I wrote the code.  I'll have to see if the more general code can slightly improve the lower bound in more cases.

For the 14x14 board position, I'm now at 6,136 nodes evaluated and 1,894 of those expanded, in about 30 seconds (using python).

For the 21x21 board position, I'm now at 114,975 nodes evaluated and 39,493 of those expanded, in about 24 minutes.

So about 2.5 times faster.