Algorithm to create hex flood puzzle

Answer 1

When doing RSA encryption, we do not find prime numbers, we select random numbers and then apply tests to them that give us increasingly high probability of the number being prime, withou ever proving it.

I suggest the same. Try to find conditions which that give a good likelyhood of the puzzle having the desired properties, and testing for those. Or you could use genetic algorithms/neural networks and train them to recognize the "good" puzzles, which amounts to the same thing.

Answer 2

I would try to prove that it is NP-complete or in P, to get a feel for the configurations which are difficult.

I'd also abstract away the hexagons and use a representation as a graph.

Answer 3

I've played the rectangular flood puzzle a lot (http://labpixies.com/gadget%5Fpage.php?id=10). Excited to see a Hex version! I think finding a hard game is as easy as: avoid large blocks of the same color to appear in the puzzle. At least in the rectangular cases I've seen, nearly all the puzzles that can be solved in a small number of steps have large color blocks.

P.S. I think your "lower bound" is not valid. When working forwards, if a good strategy is used, you could actually finish in fewer steps. The "lower bound" is really an upper bound for the optimum solution.