Problem Link:
Difficulty:
Challenge problem
Pre-requisites:
None
Problem:
You have to play The game “Snake” minimizing the number of steps taken to finish the game.
Explanation:
The most basic thing to take care of when the snake moves is to make sure that it should always have enough “room” to move around without obstructing itself.
A very simple thing to do could be as follows:
Find a hamiltoniam cycle. Move the head of your snake in Hamiltonian cycle as until it eats up all apples. It is guarenteed that the snake will never end up eating itself because the length of snake’s always remains less than length of cycle(= m * n). The maximum number of steps taken by this method is size of cycle * number of apples =(n * m) * (n * m - 1), which is about 8.1 * 105.
It is easy to construct hamiltonian cycles for grids whose one dimension is even. The most popular cycles used was the following pattern:
However, when you actually play snake, you dont really do this. Initially, when the length of snakes is small, after eating an apple you just move the head to next apple along shortest. The body of snake has little chance of obstructing the head in the initial stages. As the length of snake increases, the body interferes with the motion of head more and more, and you should play with more care.
Many of the top solutions used similar ideas to move the head along shortest path initially. After some stage, choose paths from one apple to another such that the path is short and the snake does not end up obstructing itself.
It is difficult to understand the best solutions because they are rather long and un-commented, but you can hack them to show you the moves made by the snake as game evolves and its fun to watch them.
Setter’s Solution:
Can be found here