1
$\begingroup$

There is a display of NxN (N<=90) pixels with some blocked pixels and a snake of width = 1 pixel and variable length and two players A and B play a game.

The game proceeds as follows -

  1. Both players take alternate turns.
  2. In each turn, the player has to extend the length of the snake by moving it's head in either of the three directions (left/right/forward) by one pixel thereby increasing the length of the snake by 1 pixel. Therefore, the snake doesn't move from it's initial position but only the length of the snake increases and it's head moves in some direction.
  3. The head of the snake cannot cross it's body or any of the blocked pixels.
  4. The Player who cannot extend the length of the snake anymore loses the game.

The list of blocked pixels is given to you.

Initially the length of the snake is 1 pixel i.e. it occupies only one pixel from the NxN pixels.

I need to know for each unblocked pixel, who will win the game if Player A starts the game by putting the snake on this particular pixel initially.

I tried reducing the problem to apply the Sprague-Grundy theorem but made no progress as the size of the display is too large (90x90) So, calculating the Grundy numbers for each state isn't computationally feasible.

Also, I suspect that there exists a max flow solution to the problem but I failed to construct the flow network for the given problem.

Can someone suggest a solution which works for the given dimensions of the display?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.