11
$\begingroup$

An ant is a methodical creature, and the ants in this puzzle are particularly so. When they start walking they always walk in a straight line, and when they reach a boundary they always turn exactly $90^\circ$ anticlockwise. If they still cannot move, they turn through $180^\circ$ and try to move. After this they have tried all directions and so stop. (Put otherwise, the ant tries turning left; if that fails, it tries turning right from its original heading.)

When an ant is set on the lower left corner on a $5\times 5$ board, as shown below as cell $A1$, and it treats any cell it has already visited, as well as the edges of the board, as boundaries, it traverses the entire board (as shown in blue). enter image description here

However, if the ant starts in a different cell, say $B3$ then it omits some cells on its journey, as shown: enter image description here (in this case cells $B4, C4$ and $D4$).

Given the $11\times 11$ grid below, there are two starting cells for such an ant that omit exactly one cell when the ant cannot move any more. The ant always starts moving the $A \rightarrow K$ direction, unless it starts in column $K$ in which case, applying the $90^\circ$ rule, it moves up. Which two cells are they?

EDIT: As pointed out by Stiv there is actually only one starting cell for which the ant will omit a single cell, not two.

enter image description here

|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ @hexomino Good point, I should have been explicit! Yes, the ant will head in the A->K direction unless it starts in column K, in which case the $90^\circ$ rule applies and it move up $\endgroup$ – postmortes Dec 3 '19 at 17:13
  • 2
    $\begingroup$ What about K11? $\endgroup$ – JMP Dec 3 '19 at 17:50
  • 1
    $\begingroup$ @JMP then it goes left — the 90 degree rule always works :) $\endgroup$ – postmortes Dec 3 '19 at 18:10
7
$\begingroup$

Initial notes:

  • If the ant ever starts at one corner of a blank region which is a perfect rectangle, then it will fill that whole rectangle and stop.

  • Starting in row 1 will not solve the problem.

Detailed deduction

Say the starting point is row number $n>1$, column letter $l$, and exactly one cell is omitted. The ant's journey can be described as follows:

  1. First, it will fill in the rest of row $n$ to the right. (If it starts in column K, skip this step.) All of row $n$, columns $\geq l$, filled.

  2. Then it will go up in column K to the top. (Assume $n$ is not 11 at this stage.) All of column K, rows $\geq n$, filled.

  3. Then along row 11 to the cell A11. All of row 11 filled.

  4. Then down. If the starting column $l$ was A, then either the rest of the grid now gets filled in one big spiral (if it was A1) or there's at least one whole row of omitted squares. So we know $l$ is not A, and we end up at A1 now. All of column A filled.

  5. Then across to K1. All of row 1 filled.

  6. Then up column K to the row $n-1$. All of column K filled. If $n$ is 2, contradiction. Then across row $n-1$ to column B. All of row $n-1$ filled. If $n-1$ is not 2, we then turn left and stay in the lower chunk of the board, omitting at least two squares unless the starting point was C10. If $n$ was 3, we either fill the rest of the board above or we just get stuck in whatever's left of row 3 omitting the above part.

Final answer

The only possible starting point is

C10:

C10 grid solved

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Very nice, and nicely explained as well :) Thank-you! $\endgroup$ – postmortes Dec 3 '19 at 18:12
  • 4
    $\begingroup$ I'm struggling to follow one part here in the D3 scenario - won't it try to turn left at C4, then hit the dead end at C3, missing out most of the board? $\endgroup$ – Stiv Dec 3 '19 at 18:44
  • $\begingroup$ @postmortes Welp, Stiv seems to be correct (see above comment). Are these the two solutions you were thinking of, and you also made a mistake with D3? Or is there a third (second) one that I've missed? $\endgroup$ – Rand al'Thor Dec 3 '19 at 19:50
  • $\begingroup$ No, those were the two I thought I'd found as well. I apologise to you (actually all of puzzling.stackexchange) -- I don't seem to take enough care when asking puzzles. $\endgroup$ – postmortes Dec 3 '19 at 20:39
  • $\begingroup$ However, you still found the (now unique) solution, and detailed how it's done, so there's no reason to remove your check-mark :) $\endgroup$ – postmortes Dec 3 '19 at 20:40
2
$\begingroup$

The two starting cells were C10 and D3 if the ant has a memory, and tests it's previous turn orientation before trying the other way, otherwise just C10.

|improve this answer|||||
$\endgroup$

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.