Continuing from maze solver update, I came across another very large maze at Purpy Pupple wikipedia page. And when I say large, I mean 4000x4000 large. Purpy calls it 2000x2000 but since it is very clearly 4000 pixels by 4000 pixels I'm calling it as 4k.

Anyhow, I had to modify his original image slightly, I cropped of the first column and the last row. This allows my entrance & exit finder to work properly. My solution appears to match his but I didn't do a pixel comparison.

Clicking on the images will take a long time as they're 1.8MiB and 3.2MiB and my upload connection is very slow.

$ time ./mazesolver.py MAZE_2000x2000_DFS.png
loading MAZE_2000x2000_DFS.png
loading image maze
load_image took 16.492s
maze size: (4001, 4001) entrance at: [0, 1] exit at: [4000, 3999]
Found exit: [4000, 3999]
backtrack took 29.140s
find_exit took 441.896s
exit at [4000, 3999], path length 783734
saved solved.png

real    9m1.530s
user    8m57.246s
sys     0m2.293s

Update: 2013-01-23: my new 3.4 GHz i5 solves this in 5:22. And after doing some micro-optimizations I've gotten it down to 4:45 but short of a dramatic algorithm change I doubt python can get much better than this.