One simple idea I had was NumMoves * log(ClusterSize) as a difficulty metric. But I'm not sure. I had my wife play several different puzzles to try to gauge difficulty based on that but it didn't seem so clear cut.
What we the people are demanding are insanely hard puzzles. Not an enumeration of hard games on the 6x6 board, but a heuristic generator for the 7x7 or the 8x8 or even the 10x10 if need may be, of games that seem utterly intractable for the first few hours.
