Enigmatic Code

Programming Enigma Puzzles

Enigma 975: Ant goes for a walk

From New Scientist #2130, 18th April 1998 [link]

Imagine an 8 × 8 chess board and imagine that in each square of the board there is written one of the following four instructions:

Turn right;
Turn left;
Go straight ahead;
Go back.

An ant is placed at the centre of the bottom left corner square. She walks, parallel to the bottom edge of the board, until she reaches the centre of the next square. She reads the instruction in the square she is in and sets off walking in the direction specified by that instruction. She walks in a straight line until she reaches the centre of a square or until she walks off the board; in the latter case, her walk stops. She continues her walk in this way, from square to square, obeying the instruction each time. She walks until she reaches the top right corner square, or she walks off the board; when either happens, her walk stops. In the former case it is called a successful walk.

Answer each of the following questions, “Yes” or “No”.

1. Is it possible to find a successful walk in which the ant repeats some part of her walk?

2. Is it possible to find a walk in which the ant does not repeat the first part of her walk but does repeat some part of her walk?

3. Is it possible to find a successful walk in which the ant visits the top left-hand corner square of the board more than once?

4. Suppose now that the board is 4 × 4. Is is possible to write an instruction in each square, using each of the four different instructions four times, so that the ant’s walk visits every square of the board at least once?

[enigma975]

One response to “Enigma 975: Ant goes for a walk

  1. Jim Randell 31 January 2020 at 11:04 am

    The instructions are fixed, and the ant’s process is deterministic. So if the ant enters a square it has been in before from the same direction as before it is forced to repeat the instructions in exactly the same way until it finds itself entering the square again from the same direction. So it will be doomed to repeat the loop forever.

    This answers the first two parts of the question:

    Solution: 1. No; 2. No.

    We call the instructions R (“turn right”), L (“turn left”), A (“straight ahead”) and B (“back”)

    In order for the ant to visit the top left square more than once it must enter it from two different directions. There are only two possible directions the square can be entered from – from below (heading north) or from the right (heading west).

    When entered from below it can only instruct R or B. When entered from the right it can only instruct L or B. So in order to be entered more than once it would have to contain the instruction B.

    So we can think about what the instruction in the square below would be. It can’t be B, as that would create an inescapable loop. It can’t be L, as we would have to enter the square from the left, which is impossible. And it can’t be R, as if we entered from the right, turned right, advanced to the corner, turned back, we would then have to turn R and end up off the board. So the only option is A, but this just pushes the issue down to the next square, which must also be A, and so on until we see the entire rest of the left-hand edge of the grid would need to be filled with A’s entered from below, but the last one cannot be entered from below, so the scenario is not possible.

    Solution: 3. No.

    For the final part we can write a program to look for suitable grids.

    This Python 3 program runs in 675ms.

    Run: [ @repl.it ]

    from enigma import multiset, irange, join, printf
    
    # advance: map <direction> -> (<delta x>, <delta y>)
    adv=dict(N=(0, 1), E=(1, 0), S=(0, -1), W=(-1, 0))
    
    # turn: map <instruction> -> <direction> -> <new direction>
    turn = dict(
      R=dict(N='E', E='S', S='W', W='N'),
      L=dict(N='W', E='N', S='E', W='S'),
      A=dict(N='N', E='E', S='S', W='W'),
      B=dict(N='S', E='W', S='N', W='E'),
    )
    
    # update a map with <k> -> <v>
    def update(m, k, v):
      m = m.copy()
      m[k] = v
      return m
    
    # solve a grid, filling instructions
    # x, y = current position
    # d = current direction
    # s = available instructions
    # m = map
    # vs = visited squares
    # n = count the steps
    def solve(x, y, d, s, m=dict(), vs=set(), n=0):
      # have we reached the end?
      if x == 3 and y == 3:
        # have we visited every square?
        vs.add((x, y, d))
        if len(set((x, y) for (x, y, d) in vs)) == 16:
          yield (m, n)
      else:
        # are we caught in a loop?
        if (x, y, d) in vs: return
        vs = vs.union([(x, y, d)])
        # advance
        (dx, dy) = adv[d]
        x += dx
        y += dy
        # are we out of bounds?
        if x < 0 or y < 0 or x > 3 or y > 3:
          pass
        else:
          # turn according to the instruction from the map
          i = m.get((x, y), None)
          if i is not None:
            yield from solve(x, y, turn[i][d], s, m, vs, n + 1)
          else:
            # fill out the instruction
            for i in s.keys():
              yield from solve(x, y, turn[i][d], s.copy().remove(i), update(m, (x, y), i), vs, n + 1)
    
    # each of the 4 instructions 4 times
    s = multiset.from_dict(dict(R=4, L=4, A=4, B=4))
    
    # solve the grid, starting at (0, 0), heading E
    for (m, n) in solve(0, 0, 'E', s):
      # output solution grids
      vs = join((join((m.get((x, y), '?') for x in irange(0, 3)), sep=" ") for y in irange(0, 3)), sep=" / ")
      printf("{n} -> {vs}")
    

    Solution: 4. Yes.

    There are five possible grids. The ant can manage a walk of 20, 22 or 24 steps.

    Here are diagrams of the grids and the walks:

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: