Most difficult maze?

[Neal-Specter]

Which maze generation type do yall think makes the most difficult maze to solve? Which ones would be resistant to the starting from the end solving strategy?

[armin-reichert]

Hi. I cannot give you a "scientific" answer, but let me try to give some thoughts.

The mazes generated by all these algorithms are "perfect mazes". A "perfect maze" is just a spanning tree of the undirected graph induced by the grid: vertices of the graph are the grid positions and edges are the horizontal and vertical connections between neighbor positions (in the "8-neighbor topology, also the diagonal neighbors are considered as connected).

So you have a spanning tree of a grid graph and you run a graph traversal / pathfinder algorithm on this tree. As there exists a unique path between any two vertices in the tree, a path/solution always exists.

Each graph algorithm has its characteristic time and space complexity. This can be found in any textbook on graph algorithms. To "solve" a maze most efficiently, the pathfinder should expand as little nodes as possible and also find the shortest path. As described above, in these trees there exists a unique path between any two vertices so this is also the shortest path. So the "difficulty" is probably just determined by the kind of maze that has the longest paths in average. I did not measure that but it is rather obvious that the longest paths occur in the mazes created with the "backtracking" algoritzhm (random depth-first search over the grid graph). The pathfinder that expands the least nodes is probably "best-first search". You can see that clearly in the demo application.

I do not understand your last sentence, sorry.

Hope this helps.

Armin Reichert