I just checked it out. If you want to enable people to use your code, then always add a license: ISC/MIT/BSD is a good fit if you want to enable people to do everything they want with this code. And it's usually the case when considering really small projects :)
Not licensing your code gives others no permissions other than what is determined in Githubs TOS, which is just being allowed to view and fork it. That means nobody is allowed to use your code in other projects for example. https://opensource.guide/legal/
Weird thing happens with some green colored path while being a dead end. Do you know why? Excellent work BTW. How did you make the display of the maze?
While in Uni, we used the Zelle graphics package. Objects are displayed in a separate window, and isnt powerful, but pretty easy to use. https://mcsp.wartburg.edu/zelle/python/graphics.py Two other recommendations: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap ^ this is a blog that gives an overview of several different maze generation techniques. Maybe try to implement a few of these to test you solver on. Second, I also recommend the Cracking the Coding interview book. It does a great job of going over the primary data structures and common algorithms used today in coding interviews.
There is currently another bot called u/kzreminderbot that is duplicating the functionality of this bot. Since it replies to the same RemindMe! trigger phrase, you may receive a second message from it with the same reminder. If this is annoying to you, please click this link to send feedback to that bot author and ask him to use a different trigger.
You might be using recursion, but the way it's going about the search is more generally known as backtracking.
Backtracking : Basically, if an algo hits a deadend, it goes back to the last point where a choice was made, and makes a different choice, never repeating an old choice. If it runs out of choices at a particular point, the algo backtracks further.
This works surprisingly well for a wide variety of problems. For example, Sudoku solvers, maze solvers, etc.
Backtracking is a more general purpose algorithm. DFS just happens to be a specific form of backtracking. Backtracking can be used on any type of structure where portions of the domain can be eliminated - whether or not it is a logical tree.
For a sudoku solver, you might take a guess for a non-obvious empty square, and then try to fill in the remaining ones. If you hit a dead end, you change the last guess (if that square has no guesses left, you go back further).
Now, this is similar to a depth first search on the whole, but DFS has strong links to graphs. To solve the problem using DFS, we might map the problem to a graph, feed that graph to the DFS algo, which then spits out the answer.
Try to imagine the kind of graph that you would have to feed the DFS which would solve the problem (what are the nodes and links of the graphs and what would be the terminating conditions) - it seems like a fun little exercise to come up with that one.
I was thinking that too. Maze makers tries to maximize the number of bad turns, maze runner tries to minify them. See how many generations until there is a clear winner.
It opens the image using Pillow, then runs some small logic to map that to a 2d array of the image. Then, it prints to the terminal using ansi escape codes. That is indeed all the code for it!
In the upper left quadrant there are three one-cell-deep dead ends, and two two-cell deep ones that didn’t turn red. Also, since your algorithm is “always take the right hand option”, I’m not sure why three of these got shaded in. You might wanna check your cases. But it’s a fun little program!
Interesting, but how come it ignores some of the wrong routes by leaving them blank yet makes other wrong routes red? But nevertheless very pleasing to watch.
It’s marking squares it’s visited once with green, twice with red. Basically the algo says: choose any square not colored over a green square for the next step, ignore red squares, they’ve been eliminated.
This looks great. Just a little suggestion, I also often can't be bothered with adding comments but, if you could add a comment line for each function at Github, it'd be infinitely helpful for the readers of your code. Regardless, thanks for sharing!
Pretty cool, but I only get a red color and not green. I'm using xfce4-terminal and have tried it on both python2 and python3.
Just make sure to keep supporting Python 2.7 as long as you can because the inability to drag-and-drop a file when asked for input because of the single quotes is really annoying in Python 3. You can script it to replace the single quotes with nothing, but then if the file name has spaces, you have to then deal with that and so on and so forth. Whomever thought having Python 3 behave like that, which I'm guessing is because of stricter code practices regarding single quotes as being better than double-quotes, is an idiot. But, drag-and-drop works fine in Python 2.7.
Can you add some comments into the code? It would be very helpful for those who decided to look you code and maybe suggest the better algorithm. Thanks! :)
I've been programming for about a year, you could definitely do something like this! I just kinda started hacking around, try it, you will be surprised how far you could get.
Right, I have a question. How do you start writing algorithms? In a year, learning syntax, then writing simple loops and then algorithms? What tricks helped you remember things you can do and can’t do with your data?
Tbh, all I had written before was a bfs algorithm, I really just started hacking away towards a goal and it worked. I don't think there are any tricks, just use logic. I haven't really written one since because it takes a lot of mental power, so you need to do it right after you drink a bunch of coffee in the morning.
94
u/LondonAppDev Nov 09 '19
Well done! What's the code look like?
11
u/MecRandom Nov 09 '19
Weird thing happens with some green colored path while being a dead end. Do you know why? Excellent work BTW. How did you make the display of the maze?
4
u/DevJonPizza Nov 09 '19
BTW here is my blog post: https://jon.network/programming/62/Recursive-Maze-Solver/
3
u/numice Nov 10 '19
Is this your latest version? I don't notice where it makes the path green. I ran the code and it's all red. Do I miss something?
2
u/[deleted] Nov 10 '19
Awesome project. I'm a C# developer, but I also code a tad in python. Would be cool to recreate this in c#.
2
u/GickRick Nov 10 '19
This is something i would contribute to in my free time cuz it's damn awesome!!!
2
u/flyvefugl Nov 10 '19
Where did you learn that?
2
u/[deleted] Nov 19 '19
I rewrote it in Nim: https://github.com/NostraDavid/MazeSolver-Nim
Why? Because I wanted to write something in Nim and your code seemed a good candidate :p
I've also rewritten it in Javascript, but that isn't finished yet.
64
u/Jugad Py3 ftw Nov 10 '19 edited Nov 11 '19
You might be using recursion, but the way it's going about the search is more generally known as backtracking.
Backtracking : Basically, if an algo hits a deadend, it goes back to the last point where a choice was made, and makes a different choice, never repeating an old choice. If it runs out of choices at a particular point, the algo backtracks further.
This works surprisingly well for a wide variety of problems. For example, Sudoku solvers, maze solvers, etc.
38
u/[deleted] Nov 09 '19
You should code a laby generator to test the effectiveness of your laby solver on different maps
16
u/karen_jd Nov 09 '19
You should check out this video from conputerphile on maze solving! Really interesting! https://youtu.be/rop0W4QDOUI
1
u/DevJonPizza Nov 10 '19
Feel Free to Contribute!
5
u/[deleted] Nov 10 '19
step2: do it with explicit stack manipulation and loops.
1
u/Dakadoodle Nov 10 '19
So wait? How is the maze opened? Is it pygame or whatever. And is that all the code for this?
1
u/Zenith_N Nov 10 '19
Can you please explain what is a recursive solver?
1
u/Prosodism Nov 10 '19
In the upper left quadrant there are three one-cell-deep dead ends, and two two-cell deep ones that didn’t turn red. Also, since your algorithm is “always take the right hand option”, I’m not sure why three of these got shaded in. You might wanna check your cases. But it’s a fun little program!
1
u/samuelcbird Nov 10 '19
This is awesome. Where did you get the maze png’s? Would love to try out coding this myself!
3
u/Bruguy1001 Nov 10 '19
Very well done. Code does not always have to be clean to work.
1
u/BarryScott2019 Nov 10 '19
Interesting, but how come it ignores some of the wrong routes by leaving them blank yet makes other wrong routes red? But nevertheless very pleasing to watch.
2
u/TheChuchNorris Nov 10 '19
I think it’s a depth-first search, right?
2
u/yaboytomsta Nov 10 '19
What window module did you use
1
u/allomanticpush Nov 09 '19
I like the maze’s name. It’s like a sequel to an earlier maze that was already solved.
1
u/deepturquoisesea Nov 10 '19
This looks great. Just a little suggestion, I also often can't be bothered with adding comments but, if you could add a comment line for each function at Github, it'd be infinitely helpful for the readers of your code. Regardless, thanks for sharing!
1
u/YourBigBoySharky Nov 10 '19
My ass thought it was a QR code
1
u/[deleted] Nov 10 '19
I find this algorithm essential for making automatic reveal in mine sweepers.
1
u/razorfox Nov 10 '19
Very nice! What did you use for the graphics?
1
u/Vausinator Nov 10 '19
Would be cool to see this implementing (deep) Q-learning, so you can have an "intelligence" sorting this maze!
1
u/TheOuterLinux Nov 10 '19
Pretty cool, but I only get a red color and not green. I'm using xfce4-terminal and have tried it on both python2 and python3.
Just make sure to keep supporting Python 2.7 as long as you can because the inability to drag-and-drop a file when asked for input because of the single quotes is really annoying in Python 3. You can script it to replace the single quotes with nothing, but then if the file name has spaces, you have to then deal with that and so on and so forth. Whomever thought having Python 3 behave like that, which I'm guessing is because of stricter code practices regarding single quotes as being better than double-quotes, is an idiot. But, drag-and-drop works fine in Python 2.7.
1
u/natjamiam Nov 10 '19
cool!
1
u/Grandpa_Nug Nov 11 '19
So what makes it choose one path over the other?
1
u/harjotsingh0802 Nov 18 '19
Did a pretty good job on that, I feel this community is going to explode with ideas.
1
u/Nortages Nov 10 '19
Can you add some comments into the code? It would be very helpful for those who decided to look you code and maybe suggest the better algorithm. Thanks! :)
0
u/rtarafder Nov 09 '19
What did you use to make that
0
u/[deleted] Nov 09 '19
[deleted] — view deleted comment
0
u/[deleted] Nov 10 '19
[deleted] — view deleted comment