[kuboble]

Length of the solution correlates with difficulty just not perfectly. It's easy to come up with artificial boards with high move count that are easy (e.g. Hanoi towers or long winded corridors)

With three pieces difficulty gets much harder past 16 moves optimal.

It was a long process but in the end I wrote program to generate all different board shapes, for each of those shapes I generated some basic starting position (all pieces next to each other) and then generated all positions reachable from starting position.

Then I tried different heuristics as to which level is the most interesting and ended up with just taking the one with the longest solution.

It generated approximately 100k levels and I started playing them randomly and marking those I liked to final game.