Puzzle Creation Algorithm

Question

I am creating a puzzle game, which, being played manually for easy levels, is designed to solve computer programs for more complex ones. A puzzle is a fill on a hexagonal board. You can try the prototype here .

alt text http://www.hacker.org/flood/screen.png

Here's how the puzzle works: choosing a color from above, you fill the fill, starting from the top left tile. This will gradually transform the board into a solid color. The challenge is to do this in a certain number of moves.

I have created several puzzles like this, and the key is to use an algorithm that generates boards that are difficult to solve without knowing how they were created. For example, here we can create a board by reversing the fill of the bay: work back from a solid board until it is flooded. We know how many steps it took, and we can set it as the lower bound for the solution.

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

An approach that is not a solution generates a random board, and then optimally solves it and sets it as a goal. The point is to create a puzzle where the optimal solution is NP time, or at least hard P.

So, I'm looking for an algorithm that can generate extremely hard boards, where solving them as they grow becomes a serious problem.

Answer 1

When performing RSA encryption, we do not find primes, we select random numbers, and then apply tests to them that give us an increasingly high probability that a number is ever proving it.

I suggest the same thing. Try to find conditions that give a good chance that the puzzle has the desired properties and will test it. Or you can use genetic algorithms / neural networks and teach them how to recognize “good” puzzles, which is the same thing.

Answer 2

I would try to prove that he is NP-complete or in P, in order to feel complex difficulties.

I would also abstract the hexagons and use the graph view.

Answer 3

I have played a rectangular drop puzzle many times ( http://labpixies.com/gadget_page.php?id=10 ). Excited to see the Hex version! I think finding a difficult game is as easy as: avoiding large blocks of the same color to appear in the puzzle. At least in the rectangular cases that I saw, almost all puzzles that can be solved with a few steps have large color blocks.

PS I think your "lower bound" is invalid. When working forward, if you are using a good strategy, you could complete fewer steps. The "lower bound" is indeed the upper bound for the optimal solution.