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.