1

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?
DukeZhou
  • 6,237
  • 5
  • 25
  • 53
Ahmad Kandil
  • 19
  • 4
  • 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. – Recessive Dec 08 '19 at 07:51

1 Answers1

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.

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!).

Harsh Sinha
  • 121
  • 3