title: Algorithm to create hex flood puzzle
body: <p>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 <a href="http://www.hacker.org/flood/" rel="nofollow noreferrer">here</a>.</p>
  
  <p><a href="https://i.stack.imgur.com/E6Ju6.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/E6Ju6.png" alt="alt text"></a><br>
  <sub>(source: <a href="http://www.hacker.org/flood/screen.png" rel="nofollow noreferrer">hacker.org</a>)</sub>  </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <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.</p>