There's computational complexity, then there's human complexity. I've thought a lot about this over the years (I've made a bunch of puzzle games, and puzzlescript, an engine/language for making grid-based puzzle games), and the only paper I've read that's made me think 'huh' was "Difficulty Rating of Sokoban Puzzle" by Jarušek and Pelánek ( https://www.fi.muni.cz/~xpelanek/publications/stairs2010-fin... ).

While I have a feeling that subject 'difficulty' is necessarily a slippery concept, they focus on 'context switching' as a key element of difficulty. In sokoban terms - how often you have to alternate between pushing one box and pushing another. This too can be gamed/trivialized, but, when I used it as a heuristic is was very good at generating the most horrifically difficult levels, much moreso than just going for 'solution length'.

On more general notions of complexity. In sokoban terms, the number of crates trumps everything else - for solvers I've written you quickly get exponential explosions with the number of crates. Nothing else really is significant.

I've also been working on solvers for more general classes of these games (puzzlescript games) and it's surprising how powerful generic solvers still are. PuzzleScript+MIS https://dekeyser.ch/puzzlescriptmis/ (not by me) is one powerful tool that uses PuzzleScript as a basis. I've worked on speeding up the solver a bunch (not currently integrated), figuring out good general heuristics for different kinds of games ( https://github.com/increpare/puzzlescript-labs has various experiments in this direction, including a modded version of PS+MIS). It's a nice optimizaiton problem for focusing on making numbers go down - there are lots of games to test on.

Wow, thank you for your input! The "alternation" proxy for difficulty is fascinating to me, doesn't feel like something I would have thought of right away. And, I guess I wasn't aware of how much thought goes into designing Sokobans :)

I think the crates trumping other complexity metrics isn't entirely obvious to me. For problem 15 in the OP's post, author says it was too expensive to compute at runtime in the browser. From a human perspective, it's not apparent why, as a large part of the solution is very repetitive. It feels as if there should be a more condensed representation for iterating over problems like that one.

If I may gauge your opinion on it, have you looked into MazeBench? It comes from LLM benchmarking circles, but seems to suggest a search space that's too difficult for LLMs, even with tools, to solve. Curious how much overlap the PS/MIS solvers would have with solving something like this.