This snake game solver is represented by an undirected graph and the Hamiltonian Cycle algorithm that generates path visiting each vertex exactly once. This approach ensures that the snake will never collide and maximum score will be achieved.
The application is based on the fundamental algorithm in the field of a graph theory to determine the cycle in the graph. Finding the cycle allows the solver to traverse all the vertices in the graph exactly once, hence it always gets maximum score in the game. The graph in algorithm.py script is represented by a hash table composed of vertices keywords. Each vertex corresponds to a cell in the game grid and is connected to its adjacents according to a schema presented in the picture below.
The algorithm calculates only one of several available paths. It is caused by a NP-complete problem and a polynomial time complexity to find all existing paths. In this program a recursive backtracking approach was also proposed.
Copy the repository by forking and then downloading it using:
git clone https://github.com/<YOUR-USERNAME>/Snake-SolverTo install requirements use:
cd Snake-Solver
pip install -r requirements.txtRun App:
cd Snake-Solver
python3 main.py-
Randomly place snake on the board by pressing Space
-
To run solver press Enter
