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.