Snake is a very old game for phones. Its a 'real time game', that means you have to make decisions fast. The rules are:
- You are a snake.
- You can move to the left, to the right or go straight ahead.
- Your length is $n$ at the beginning, but there are fruits which make you longer.
- The more fruits you eat, the more points you get. But with each fruit you eat, you get longer.
- If you crash into a wall / yourself, the game is over.
- The game field is a $n \times m$ grid, but there might be obstacles on the grid. You could also eventually go thorugh the borders of the game (so: from top to bottom, from left to right) or not (there are different 'maps')
You can play snake here if you don't know it.
I am now interested in what happens when your length is equal to the number of free cells on the board. Can you play it infinitely long?
My ideas
I think this is similar to the seven bridges of Königsberg except that you don't want to visit all bridiges exactly once, but all isles exactly once and get back to the isle you started with. However, I don't know if there is a similar (solved) problem. So the question how to decide if a map can be played infinitely long remains.
What is searched is a Hamiltonian path: Every free grid cell can be mapped to a vertex and every "neighboring" relationship can be mapped to an edge. Then every cell should be visited exactly once.
Finding a Hamiltonian path in an arbitrary Graph is NP-Complete. However, those graphs are not arbitrary. Every vertex has at most 4 edges. (I am not sure if this is of any use)