[icefox]

Exactly what you said, this solution doesn't make super-hard puzzles, it makes not-fun puzzles. The obvious next step that I would challenge you to do would be to optimizes for puzzle cuts so that they do not follow the main color lines of the image as much as possible. This would result in pieces that are just as interesting, but produce puzzles that are radically more fun to actually put together.

A good puzzle will not bore the player. Boring is that there are many blue pieces that all look exactly alike. Trying each one over and over is not fun. But with a tweak to your technique you could make sure that every blue piece that can contain another color would, thus increasing the variance of unique pieces which is not boring for players. Finding a blue piece with this little bit of brown and a spec of purple means the player can get to remember that and hunt for where it could go which is the fun part of puzzles. Do that and you can approach puzzle companies to license them a tool to make more fun puzzles and they will buy it.

Now of course your tool can't solve everything you can still end up with rubbish like: http://www.amazon.com/USAopoly-M-Ms-Puzzlemania-Puzzle/dp/B0...

And in contrast a really good puzzle that at first glance looks like it is all one color, but filled with so much detail it is a blast to put together. http://www.amazon.com/Ravensburger-78000-Fire-Dragon/dp/B000...

[ibuildthings]

Pushing away from color lines is very easy. For negative values of lambda in Eq.1 of the paper, (i.e. reverse the cost for color lines ), the optimization tries to push the puzzle shapes away from the color lines. We had tried a few in this configuration, but personally my co-authors and I liked the puzzles generated by the scheme of adhering to the color lines.

Hardness/fun factor in puzzles is a matter of personal taste. Hence the ability to personalize is very interesting. Not everyone like to solve 10000+ piece puzzles , nor color line adherence, but people invest time and effort in solving them.