2
\$\begingroup\$

So, as has been done many times before, I am designing an AI that can play Snake as effectively as possible. It didn't take me long to find this extremely useful thread here: How to find a safe path for an AI snake? where the top answer first and foremost recommends forming a Hamiltonian circuit for the grid and begin by just having the Snake follow this route.

However, after attempting this, I realised it didn't work with my initial grid size (23x23), at least I don't think it does. My understanding may be incorrect, but from what I gather, with m rows and n columns, if mn is odd, then there is no Hamiltonian circuit possible. If this is the case, then should I abandon this method? Or is there any way of implementing it in some case?

Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ That sounds like a theoretical computer science question. Game developers are more specialized in making Snake games for human players to play, not in making theoretically perfect AI to play Snake games. ;) \$\endgroup\$
    – DMGregory ♦
    Feb 2, 2019 at 15:37

1 Answer 1

Reset to default
2
\$\begingroup\$

Yes, you're correct, it's not possible. You can prove this using parity.

Color your grid like a chess-board. The start- and end-tiles of your Hamiltonian circuit must be adjacent, meaning they must have opposite colors. However, with an odd grid size, there are more of one color than the other, meaning to hit every square you must start and end on the same color. Thus no circuit is possible.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Apologies for the delay. Thank you, I tried exactly this, and it does indeed seem so. Regular old pathfinding it is. Thanks! \$\endgroup\$
    – Polyrogue
    Feb 5, 2019 at 20:21
  • \$\begingroup\$ I think its worth saying that if your original grid size is odd, you can take largest even subset by discarding a row/column, or just discard a corner tile, and still use Hamiltonian circuit algorithm. There will be a hole at the end, but if number of squares is odd its inevitable. \$\endgroup\$
    – unlut
    Nov 29, 2019 at 13:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .