Check out the paper "Difficulty Rating of Sokoban Puzzle": https://pdfs.semanticscholar.org/880f/32f843e8e1fe9c712b0fc41152da3d4ec3bd.pdf https://pdfs.semantics

Check out the paper "Difficulty Rating of Sokoban Puzzle": https://pdfs.semanticscholar.org/880f/32f843e8e1fe9c712b0fc41152da3d4ec3bd.pdf 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).