9
$\begingroup$

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.

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

3 Answers 3

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – ghosts_in_the_code
    Mar 16, 2015 at 10:13
0
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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." $\endgroup$
    – Lopsy
    Mar 14, 2015 at 23:03
  • $\begingroup$ @Lopsy Does the snake's "perfect strategy" include prescience of your intentions? If it does include that, then my answer is indeed invalid. $\endgroup$
    – March Ho
    Mar 14, 2015 at 23:05
  • $\begingroup$ 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. $\endgroup$
    – Lopsy
    Mar 14, 2015 at 23:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – fibonatic
    Mar 15, 2015 at 12:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – fibonatic
    Mar 15, 2015 at 13:33
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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