Answers.Body: <p>A Hamiltonian path in a graph is a path that visits all the nodes/vertices exactly once, a hamiltonian cycle is a cyclic path, i.e. all nodes visited once and the start and the endpoint are the same.
  If we want to solve the snake game using this, we could divide the playable space in a grid and then try to just keep traversing on a hamiltonian cycle, this means you would eventually get all the rewards and never hit yourself unless you are longer than can fit on the screen.
  You can look at the code given in this <a href="https://github.com/gsurma/slitherin" rel="nofollow noreferrer">Github repo</a>.</p>
  
  <p>Note that this method, as you can tell, is not going to be optimal by time, there could be better solutions than this.
  You will have to use a graph to store all the nodes and the complexity is supposed to be O(n!).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-08T19:52:16.027Z
Answers.LastActivityDate: 2019-12-08T19:52:16.027Z
Answers.UserDisplayName: Harsh Sinha
Body: <p>I wonder if there is a way to solve snake game using Hamiltonian algorithm?
  if there is a way</p>
  
  <ol>
  <li>how to apply it?</li>
  <li>what data structure will be used with algorithm?</li>
  <li>time complexity and space complexity?</li>
  <li>is this algorithm an optimal solution or there is a better way?</li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-08T07:51:34.210Z
Comments.Text: https://youtu.be/tjQIO1rqTBE?t=947 is a good video that uses a Hamiltonian cycle to achieve this. No, this is not optimal in terms of time (it takes a longer to reach some lengths then other methods do) but it is perfect, and will eventually get to the maximum length.
Comments.UserDisplayName: Recessive
Tags: <game-ai><graph-theory><path-finding>
Title: How to solve Snake Game with a Hamiltonian graph algorithm?
UserDisplayName: Ahmad Kandil
ThreadText: # How to solve Snake Game with a Hamiltonian graph algorithm?
  
  (Asked by: username_0 on 2019-12-08)
  
  I wonder if there is a way to solve snake game using Hamiltonian algorithm?
  if there is a way
  
  1. how to apply it?
  2. what data structure will be used with algorithm?
  3. time complexity and space complexity?
  4. is this algorithm an optimal solution or there is a better way?
  
  **Tags:** game-ai, graph-theory, path-finding
  
  > **Comments:**
  > **username_1**: https://youtu.be/tjQIO1rqTBE?t=947 is a good video that uses a Hamiltonian cycle to achieve this. No, this is not optimal in terms of time (it takes a longer to reach some lengths then other methods do) but it is perfect, and will eventually get to the maximum length.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-12-08. Score: 2
  
  A Hamiltonian path in a graph is a path that visits all the nodes/vertices exactly once, a hamiltonian cycle is a cyclic path, i.e. all nodes visited once and the start and the endpoint are the same.
  If we want to solve the snake game using this, we could divide the playable space in a grid and then try to just keep traversing on a hamiltonian cycle, this means you would eventually get all the rewards and never hit yourself unless you are longer than can fit on the screen.
  You can look at the code given in this [Github repo](https://github.com/gsurma/slitherin).
  
  Note that this method, as you can tell, is not going to be optimal by time, there could be better solutions than this.
  You will have to use a graph to store all the nodes and the complexity is supposed to be O(n!).
  
  
  ---
  
  