Maze Algorithm That generates the most difficult mazes?

Question

I was playing around with the recursive backtracking algorithm but it always produces very easy mazes. What algorithm produces the hardest mazes to solve (please include information about braids and biased directions if appropriate)?

Answer 1

Quantitatively defining the "difficulty" of a maze isn't easy. So let me be qualitative.

First off, Recursive Backtracker is a "perfect maze" algorithm; it generates mazes with one, and only one, solution. Most work on maze generation has to do with generating perfect mazes, so I will limit my answer to those.

There are many, many variations and off-shoots of maze algorithms. But in effect, there are only 12 basic maze algorithms. I have them listed here in the order that I personally (qualitatively and anecdotally) find to be most-to-least difficult:

1. Kruskal's
2. Prim's
3. Recursive Backtracker
4. Aldous-Broder
5. Growing Tree
6. Hunt-and-Kill
7. Wilson's
8. Eller's
9. Cellular Automaton (Easy)
10. Recursive Division (Very Easy)
11. Sidewinder (Predictable)
12. Binary Tree (Flawed)

There is not a lot of difference in the difficulty of the top four on my list. Sorry about that. Perhaps there is a flaw in your implementation. Most likely, you're just good at doing mazes. Try making them larger.

Answer 2

Whilst not a direct answer, this article on visualizing maze generation algorithms is a must-watch.