This shows how far you can get when you take something apparently simple, and run with it! - even if you sometimes end up running in circles.

Particulary interesting are the various alternative definitions of complexity.

For this one:"take the average of these look-ahead lengths (L) and count the number of branch points (N). The maze score will be L^N." Why L^N? and not L*N, for instance. Even more plausibly, one could look at Max(L) (it doesn't matter how often one has to look for dead-ends - but their lengths seems crucial). Similarly, rather than the absolute number of loop(-traps), the longest one should matter most. There may be simple ways to integrate these two, and the simplest may just be Max(L, MaxLoopLength).

Psychologically, if the solver's working memory is the limiting criterion for finding a solution for a maze, we can expect that above lengths of 7, humans (not endowed with pencils or Mathematica or the like) start having problems. Then again, perhaps we should also take into account the number of nodes in the sub-tree that need to be evaluated before proceeding...