@ wrote... (9 years, 8 months ago)

I saw a recent post of the most incredible maze I've ever seen. Well I just had to solve it.

Original

map

Version 1. Just keep turning right, following the right hand wall. Turns out this takes 109,000 steps to find the exit. Solves in approx 3 seconds.

109k

Version 2. Keep turning right but if you find yourself in a dead end, backtrace to the last place you could make a choice, go left instead. 66,850 steps.

66850

Version 3. Keep turning right, but if you dead end or step on a square that you've previously visited, throwout your path since the first time you visited that square then turn left. 17,838 steps, solves in approx 12 seconds.

17838

I should mention that this is NOT the optimal path. In fact you can easily see in the top left in the double wide section there is a lot of backtracking and again to the bottom right of there a large section of switchbacks that could easily be bypassed.

I'm not entirely sure how to do a depth first search on a problem set this huge since you can't use simple recursion. Four hours was all I was willing to dedicate to this little project, I may come back to it one day.

Update: I did

mazesolver.py

Category: tech, Tags: mazes, python
Comments: 0
Click here to add a comment