Enigmatic Code

Programming Enigma Puzzles

Enigma 373: Date the painting

From New Scientist #1522, 21st August 1986 [link]

Enigma 373

(R = Red, B = Blue, G = Green, Y = Yellow)

You will no doubt have recognised this as the latest masterpiece by the artist Pussicato, which has just gone on display at the National Gallery. I visited Pussicato in his studio at the end of March, just before he began work on the picture. He showed me the canvas divided into 36 squares which were numbered 1 to 36. He planned to paint the squares in order, one per day starting with square 1 on 1 April, using the four colours in strict rotation. He had numbered the squares so that from one day to the next he always moved to an adjacent square either horizontally or vertically; also, squares 1 and 36 were similarly adjacent. As I looked at the canvas, I pointed to two horizontally adjacent squares and remarked that the right-hand one contained a number which was 8 times the number in the left-hand square. Pussicato had no reply.

On what date did Pussicato paint the top left hand square of the picture?

[enigma373]

Advertisements

2 responses to “Enigma 373: Date the painting

  1. Jim Randell 2 December 2016 at 7:35 am

    This Python 3 program runs in 65ms.

    from enigma import printf
    
    # label the colours
    (R, B, G, Y) = (0, 1, 2, 3)
    
    # the grid
    grid = (
      (R, B, G, B, G, Y),
      (Y, G, Y, R, B, R),
      (R, B, R, Y, G, Y),
      (Y, G, B, G, B, R),
      (G, Y, R, B, R, B),
      (B, R, Y, G, Y, G),
    )
    
    # find paths on the grid
    # (r, c) - row and column
    # ps - positions on the path
    # cs - colours
    def solve(r, c, ps, cs):
      # are we done?
      if len(ps) == 36:
        # check we form a circuit
        (r1, c1) = ps[0]
        (r2, c2) = ps[-1]
        if (r1 == r2 and abs(c1 - c2) == 1) or (c1 == c2 and abs(r1 - r2) == 1):
          yield ps
      else:
        # move to an adjacent path of the right colour
        for (i, j) in ((+1, 0), (-1, 0), (0, +1), (0, -1)):
          (r2, c2) = (r + i, c + j)
          if r2 < 0 or c2 < 0 or r2 > 5 or c2 > 5: continue
          if cs[grid[r][c]] != grid[r2][c2]: continue
          if (r2, c2) in ps: continue
          yield from solve(r2, c2, ps + [(r2, c2)], cs)
    
    # try labelling the circuit
    def check(ps):
      # move along the path
      for (i, (r, c)) in enumerate(ps):
        # look at the square to the right
        if c > 4: continue
        j = ps.index((r, c + 1))
        # look for numbers that differ by a multiple of 7
        n = j - i
        (m, x) = divmod(n, 7)
        if x > 0: continue
        # m will be negative for a reverse traversal
        (m, m1, s) = ((m, m + n, 1) if m > 0 else (-m, -m - n, -1))
        printf("{m} is at position ({r}, {c}), {m1} is at position ({r}, {c1}) [s={s}]", c1=c + 1)
        # (0, 0) contains number...
        p = (0, 0)
        n = ((ps.index(p) - i) * s) % 36 + 1
        printf("{p} contains number {n}")
    
    for ps in solve(0, 0, [(0, 0)], { R: B, B: G, G: Y, Y: R }):
      check(ps)
    

    Solution: The top left hand square was painted on Day 31, i.e. 1st May.

    The path that follows the painting order visits the colours in a strict repeating order and finishes in a square adjacent to its start. As there are 36 squares in the grid and 4 colours we must cycle through the colour sequence 9 times, and so we can close the path into a circuit.

    By inspecting the corners (there is one of each colour) we can see that the order the colours are visited in is either …RBGY… or …RYGB…, one of these is the reverse of the other, so we only need to consider one of these possibilities as the visiting the colours in the other order would just amount to traversing the circuit in the opposite direction.

    It turns out there is only one circuit on the grid that traverses the colours in strict rotation, as seen below:

    enigma-373-circuit

    When we number the squares along the circuit there must be two squares horizontally adjacent to each other where the number of the right-hand one is 8 times the number on the left-hand one (i.e. 1 | 8, 2 | 16, 3 | 24, 4 | 32), so we are looking for adjacent squares that have numbers different by 7, 14, 21 or 28 (multiples of 7).

    Again there is only one way to number the squares to satisfy this:

    enigma-373-solution

    and this arrangement has 1 next to 8.

    The number in the top left-hand corner is 31, so this is coloured on the 31st day. If we start on 1st April that would be 1st May.

  2. Brian Gladman 3 December 2016 at 10:24 am
    # number the colours in the order we want to traverse the grid
    R, Y, G, B = 0, 1, 2, 3
    # form the grid of squares
    g = ((R, B, G, B, G, Y), 
         (Y, G, Y, R, B, R),
         (R, B, R, Y, G, Y), 
         (Y, G, B, G, B, R),
         (G, Y, R, B, R, B),
         (B, R, Y, G, Y, G))
    
    # find closed paths through the grid
    def find_path(p):
      # the number of squares visited so far
      ln = len(p)
      # have we visited all the squares
      if ln == 36:
        # if so, are the first and last squares on the path adjacent?
        (xs, ys), (xe, ye) = p[0], p[-1]
        if xs == xe and abs(ys - ye) == 1 or ys == ye and abs(xs - xe) == 1:
          yield p
      else:
        # the coordinates of the square at the end of the path so far
        x, y = p[-1]
        # consider the squares left, right, above and below it
        for xx, yy in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
          if 0 <= xx < 6 and 0 <= yy < 6:
            # if the square has not been visited and has the correct colour
            if (xx, yy) not in p and g[yy][xx] == ln % 4:
              yield from find_path(p + [(xx, yy)])
    
    fs = 'He painted the top left square on {}{} {}. [{} @ {}, {} @ {}, {} @ {}]'
    
    # consider possible closed paths through the grid
    for p in find_path([(0, 0)]):
      # consider each square on the path (except the first)
      for n, (x, y) in enumerate(p):
        # and the square to its right
        if n and x < 5:
          nn = p.index((x + 1, y))
          # if the top left square has the number n0 and we traverse the
          # path in colour order R, Y, G, B then 8.(n0 + n) = (n0 + nn);
          n0, r = divmod(nn - 8 * n, 7)
          if not r:
            # compute the positions with the revised numbering
            m, mm = n0 + n, n0 + nn
            # and ensure that n0 is in range (1..36)
            n0 = (n0 - 1) % 36 + 1
            # compute the day and month the top left square was painted
            day, mth = (n0 - 1) % 30 + 1, 'April' if n0 < 31 else 'May'
            sf = ['st', 'nd', 'rd', 'th'][min(day - 1, 3)]
            print(fs.format(day, sf, mth, n0, (0, 0), m, p[n], mm, p[nn]))
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: