Algorithm to create hex flood puzzle

Question

I'm creating a puzzle game that, while playable by hand for easy levels, is meant to be solved by computer programs for harder ones. The puzzle is a flood fill on a hexagonal board. You can try a prototype here.

_{(source: hacker.org)}

Here is how the puzzle works: by choosing a color from the top, you perform a flood fill starting from the upper-left tile. This progressively converts the board to a solid color. The challenge is to do this in a certain number of moves.

I have created several puzzles similar to this, and the key is to use an algorithm that generates boards that are hard to solve without knowing how they were created. For example, here we might produce a board by reversing the flood fill: working backwards from a solid board until it has been unflooded. We know how many steps this took, and can set this as a lower bound on a solution.

The problem I'm facing is that when I try this approach, my upper-bound is way too high. It becomes trivial to solve the puzzle within this number of moves, even by moving randomly.

An approach that is not a solution is generating a random board and then solving it optimally and setting this as the target. The point is to create a puzzle where solving it optimally is NP time or at least a hard P.

So what I'm looking for is an algorithm that can generate extremely hard boards where solving them, as they get larger, becomes a serious challenge.

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.