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.

  • $\begingroup$ version1: is it 3 targets ? one in (100,100) then (x,100) then (x,1) ? $\endgroup$
    – Abr001am
    Mar 14 '15 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 '15 at 23:11
  • $\begingroup$ If diagonal crossing is forbidden, then it is possible to block the snake in version 2. $\endgroup$
    – Alexis
    Mar 24 '15 at 12:17
  • $\begingroup$ Do you know the answer to Version 2? (If you do, no hints!) $\endgroup$
    – Lopsy
    Mar 28 '15 at 22:18
  • $\begingroup$ @Lopsy No, I don't know the answer for sure. I have a feeling the snake wins though. $\endgroup$ Mar 29 '15 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.

  • $\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$ Mar 16 '15 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

  • $\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 '15 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 '15 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 '15 at 23:08
  • $\begingroup$ @Lopsy Perhaps OP should clarify the question on this issue, as it stands it is rather vague. $\endgroup$
    – March Ho
    Mar 14 '15 at 23:11
  • 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 '15 at 13:33

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.