Very interesting write-up. I have ran into a similar problem with generating mazes that are interesting to solve for humans. Depending on the desired difficulty you want the path to have a certain length and a certain number of forks as well as a certain length for dead-ends.

I wonder whether omitting the grid was a conscious decision, I feel the images would be more clear with a grid of some sort.