@ wrote... (12 years, 12 months ago)

Here's a follow up to my previous post, maze solver. I've finally gotten around to solving this properly with a breadth-first search. Shortest path is 16031, 11% better than my previous best.

I did two things to properly solve this puzzle, based on this section on Wikipedia, I filled in all dead ends. This takes a surprising amount of time (ugly code, 2.5 seconds, nice code that uses functions, 12 seconds) but dramatically sped up a depth first search. My depth first search still didn't find the best path, only a path.

So then I completely rewrote my solver to use a breadth first search and it finds the shortest path in only 8.6 seconds. 5 seconds if I fill in the dead ends but since that takes 12 seconds it's not a win.


For interest sake, here is the dead end filled version.



Category: tech, Tags: mazes, python
Comments: 1
Maze Solver Update 2 « Burgundywall.com @ February 6, 2011 wrote... (12 years, 7 months ago)

[…] from maze solver update, I came across another very large maze at Purpy Pupple wikipedia page. And when I say large, I mean […]

Click here to add a comment