[ibuildthings]

One of the authors here. Since it is a optimization, the difficulty can be controlled as a parameter ( the lambda parameter in Eq.1 in the paper ).

But you are right, some of the puzzles can be super-hard ( for example, the Seurat puzzle ) that we used to joke between ourself to name our paper "taking the fun out of puzzles".

Personally, what was fascinating for me is the shape of the puzzle curve it produced. Most of the common puzzles are grid based (i.e. four neighbours - up , down, left, down ). But in this scheme, there can be strange neighborhood pieces, with even stranger shapes.

[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.

[stankot]

This is really nice, from the scientific side, and it creates awesome puzzles as well. Any chance that we can see this software as a service, or maybe even for download?