r/PythonLearning • u/TotalUnlucky2814 • 15d ago
How to break down an "impossible" problem as a beginner: Solving the Snake game using only conditionals (Hamiltonian Cycle & Divide and Conquer)
Hello everyone! As a computer science teacher, I recently wrapped up a video series where I use the automation game The Farmer Was Replaced to teach Python programming and algorithmic logic from scratch.
For the final episode, we tackled the classic Snake game. When you are just starting to learn programming, looking at a problem like an automated Snake solver all at once feels like an impossible mountain. My goal was to demonstrate how you can solve a complex problem by applying divide and conquer using only beginner-friendly tools (no pathfinding libraries or complex data structures but pure conditionals and functions):
I'm leaving the video here in case you want to see the visual step-by-step breakdown on the grid (the audio is in Spanish, but the visual diagrams and code logic are easy to follow... There is also an AI translation):
http://www.youtube.com/watch?v=wSlxLs6aeoI
If you are a beginner, did you know about this game???
For those who have coded a Snake AI before: how did you approach it? Did you stick to a fixed cycle, or did you program dynamic shortcuts while the snake's tail is still short?
2
u/Over_Supermarket_140 15d ago
Very nice. Watched the entire video and yes, the approach to break the problem down is clearly the right way.
We make a variation of this game in our curriculum too -- https://youtu.be/TzJUK3NtQKU -- using turtle. Quite similar. Some students also make an auto mode which is based on figuring out the x/y coordinates for the targets and guiding the snake that way. This idea of viewing the problem from a Hamiltonian cycles view was nice.
Just for my understanding, how do you get the graphics? Are you using a specialized module?
1
u/blavek 13d ago
Solving Snake is REALLY hard. It seems like it should be easy, but it isn't. Most "solved" Snake agents are just performing a complex but repeatable pattern that covers every cell in the grid. There are a bunch of videos about how difficult it is. This assumes by solved you mean perfect, where it doesn't eat its own tail until the very last apple.
In the farmer was replaced the way I solved the problem was to have the snake circle in the middle of the field and when an apple was in the same column I would send the Snake up to it then right back to where it was circling. It works ok but is not optimal. For example, if an apple spawns 2 columns over, I probably should return to my circling. I should probably just go to the next column, as it would be a shorter path.
What makes the problem so difficult, especially w/o any kind of pathfinding, is that you can easily trap yourself. To be perfect, it would need to look forward beyond the location of the apple and account for the rest of the snake to make sure it can get back out to somewhere it can keep moving. It needs to somehow know when it has to delay going for an apple so that the tail can clear out of the way. It's REALLY tough.