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.
