3
$\begingroup$

You are playing a snake game. The snake starts in the top-left corner of a grid. Each cell of the grid is either empty or a wall. Each turn you can press a key to move the snake in one of four directions: either horizontally or vertically. Once a key is pressed, the snake moves in the assigned direction until it either reaches a wall or the boundary of the grid. Can you construct a $9 \times 9$ grid with $4$ walls such that the snake is able to visit every empty cell of the grid?

Here is a simpler version of this puzzle: Snake game on a 6×6 grid

$\endgroup$
3
$\begingroup$

Yes, it's possible:

    0   .   .   .   .   .   .   .   1

    3   .   .   .   .   .   .   .   2

    4   .   .   .   .   .   .   5   X

    X   20  .   .   .   .   .   .   19

    13  .   .   .   .   .   .   .   14
    &17                             &18
    16  .   .   .   .   .   .   .   15

    .   21  .   .   .   .   .   22  X

    .   X   9   .   .   .   .   .   8
                                    &10
    12  .   .   .   .   .   .   6   7
                                    &11

    0,1,2,3,...: move number
    X: wall
 

$\endgroup$
1
  • $\begingroup$ Yes that's the solution I had in mind. Well done! Are there any other solutions? $\endgroup$ – Dmitry Kamenetsky Apr 16 at 8:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.