# Block the snake from reaching points

Solution for Version 2 pending....

There is a $100\times 100$ grid. The upper left corner has coordinates $(1,1)$ and bottom right corner has $(100,100)$.

A 'snake' starts by occupying a single cell at $(1,1)$. On each move, it travels in any of 8 directions (vertically, horizontally or diagonally) to reach the next cell. Every cell once visited remains occupied by it; it grows by 1 unit with every move it makes. It cannot visit a cell twice, whether by retracing or by intersection. However, it may pass through a diagonal line it made earlier, by visiting only the unoccupied cells.

You need to set targets for it to reach. Each target is a single point, and the snake completes the goal by visiting the cell. Once a target is reached, you must immediately set the next one, anywhere else. You cannot set an already visited cell as a target.

Version 1 The snake must reach a target in minimum possible moves, irrespective of deeper strategy. What is the minimum number of targets you must set to create an impossible-to-reach target?

Version 2 The snake may take up to $100$ moves more than necessary to reach each target. Is it possible to block the snake (which is using perfect strategy)?

100 moves to waste means if reaching a certain target at the time it is set requires 29 moves, it can take up to 129 moves to do so.

The snake can not know any of your future goals, since you set one only after the previous one is complete. However, as it has 100 moves to waste for each target, it might deliberately waste moves to block your possible future targets.

• version1: is it 3 targets ? one in (100,100) then (x,100) then (x,1) ? Mar 14, 2015 at 19:52
• Maybe reword your question for Version 2 to "Does the snake or the player have a winning strategy"? if that is what you intend. Mar 14, 2015 at 23:11
• If diagonal crossing is forbidden, then it is possible to block the snake in version 2. Mar 24, 2015 at 12:17
• Do you know the answer to Version 2? (If you do, no hints!) Mar 28, 2015 at 22:18
• @Lopsy No, I don't know the answer for sure. I have a feeling the snake wins though. Mar 29, 2015 at 14:35

## Version 1:

Since for this version the snake can still have multiple choices for getting from point A to point B, namely two diagonals take the same number of moves as two moves in a not diagonal direction. Only moves which have to be completely diagonal or contain at most one non-diagonal move (assuming no obstructions yet from the "body" of the snake) can only be done in one way. When the snake does has multiple choices, it can then leave holes with diagonals. A set of targets which can prevent this would be $(100,100)$, $(2,1)$, $(3,1)$ and $(1,2)$. Each of the first three targets can only be reached in one way and the forth can not be reached at all, thus four targets are required.

• Good solution! I actually thought targets were required. I have up-voted, but sorry, I'll only accept the answer that answers the second version (since it's harder). Mar 16, 2015 at 10:13

## Version 1:

The snake is killed in 4 moves by the points (1,2), (100,2), (100,3) and (100,1). This works regardless if the snake is capable of pathfinding or not, as the cell is not reachable.

If the snake is capable of choosing an arbitrary shortest path specifically to thwart strategies (such as by intentionally alternating its path), then 6 steps are required (1,2), (2,2), (3,2), (3,1), (4,1), (2,1), since in this case the snake has only 1 choice, and is fully constrained by the options.

## Version 2:

Invalidated by edit clarification

• In your version 2, the snake can occupy the critical square (3,3) sometime earlier, and then appeal to the rule "You cannot set an already visited cell as a target." Mar 14, 2015 at 23:03
• @Lopsy Does the snake's "perfect strategy" include prescience of your intentions? If it does include that, then my answer is indeed invalid. Mar 14, 2015 at 23:05
• In my interpretation, you can chose your future targets depending on what the snake has done so far. In which case, it doesn't matter whether the snake is omniscient or not - this is a two-player game and either you or the snake has a winning strategy. Mar 14, 2015 at 23:08
• Your 4 moves solution can be prevented when the snake goes diagonal down right and later diagonal down left, since it takes the same number of moves to do this, but it does leave a gap for it to pass through. Mar 15, 2015 at 12:47
• @MarchHo I initially thought of that solution with six targets as well, but after some more thinking I did came up with another solution with four targets, see my answer. Mar 15, 2015 at 13:33

V1:

Go to $$(100,100), (2,1)$$, and lastly either anywhere in the lower-right empty area or $$(1,2)$$. This makes the entire area opposite to the snake's unreachable.

V2:

If there's a narrow "bottleneck" of width $$w$$ between two larger sections of a connected shape, the bottleneck can be blocked in $$w$$ moves if we start from the wide sections. Starting from the bottleneck makes barely a difference. If all the large sections have $$100w$$ or fewer squares, the snake can guarantee to win if it plays its cards right, which is the case in the beginning.