@ wrote... (14 years ago)

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



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.


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.


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.


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


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