ThinkFun, the US publishers of Rush Hour, wrote a blog post about this when they made the mobile app with a bunch of autogenerated levels maybe around 2010. Unfortunately that article is basically impossible to find now, since they redid their website and deleted the old posts. (I say "impossible", since I spent a couple of hours looking for it again while reading papers on procedural puzzle generation last year. Maybe somebody here has better luck).

The basic metric their level generator used for quantifying interesting difficulty was the earliest point of non-trivial divergence in solutions. I.e. if there's a puzzle with a 50 and 51 move solution, having those solutions diverge on move 3 is interesting. Having them diverge on move 45 isn't.

I wonder if this is the article you're thinking of:

https://web.archive.org/web/20100221131225/http://www.thinkf...

(The text of the article is only visible at the very bottom of the page for some reason)

That's it, thanks! (And to romellem for the link with a working layout and images.)

Awesome find, thanks! Wonder if I can find this Mark Engelberg fellow...

He also made an original game with ThinkFun: Code Master, which does some fun stuff with state machines:

https://www.thinkfun.com/products/code-master/

Through hcs's reply below, I was able to come across a better link to the original blog post:

Thinkfun & Mark Engelberg, "The Inside Story of How We Created 2500 Great Rush Hour Challenges"

https://web.archive.org/web/20130703141244/http://www.thinkf...

Check out the paper "Difficulty Rating of Sokoban Puzzle": https://pdfs.semanticscholar.org/880f/32f843e8e1fe9c712b0fc4... -- in particular the "problem decomposition" model introduced at the end. Being able to break a solution into subproblems makes it easier, even if there are a lot of steps (see Figures 5 and 6 in the paper).

One way this could be calculated is to assign transition probabilities to the edges, and calculate the expected number of steps a random walk takes to reach the end. (wikipedia has the math required: https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expecte...)

I'm not sure how best to assign probabilities, or how sensitive it would be to that. Perhaps uniformly, or perhaps biased toward moving closer to the end state.

http://cs.ulb.ac.be/~fservais/rushhour/ has a listing of puzzles that take the most moves, but also mentions how many different configurations are possible.

The guy who made the website literally wrote his master's about it: http://code.ulb.ac.be/dbfiles/Ser2005mastersthesis.pdf

I linked to this in the Prior Art section. This is the one I wasn't very impressed with. For one, his "moves" are unit-steps.

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.

Haha. Well, if you have ideas I'm all ears!

Not just a broad tree, but a labyrinthine broad tree where you are basically traversing a maze of choke points

A bit tangential but Peter Norvig talks about hard puzzles some in norving.com/sudoku.html

I like Peter Norvig. You inspired me to email him about this.