Enigmatic Code

Programming Enigma Puzzles

Enigma 664: The way of the dove

From New Scientist #1819, 2nd May 1992 [link]

In Churchester there are nine churches of the Angel, of the Bell, of Charity, of Destiny, of Endurance, of Friendship, of God, of Help and of Inspiration. The map of Chuchester shows the nine square parishes and each has its church at its centre. I can only remember where the church of the Angel and the church of Charity are:

There are nine doves in Churchester and each one visits three churches, flying around in a triangle in a clockwise direction. For example, one dove flies from Help to Bell, to Charity, and then back to Help again. The routes of the doves are HBC (the one just mentioned), DAF, BGI, GEA, HID, CEF, CAI, BED and FHG.

Complete the map of Churchester.

[enigma664]

4 responses to “Enigma 664: The way of the dove

  1. Jim Randell 10 June 2022 at 9:56 am

    I assigned cartesian coordinates to the churches, we can then calculate the area of the triangles from the coordinates of the vertices. If the area is negative, then the the vertices of the triangle are visited (on the map) in a clockwise order. (See: [@wolfram.com]).

    This Python program runs in 65ms. (Internal run time is 3.4ms).

    Run: [ @replit ]

    from enigma import (tuples, subsets, product, update, reverse, join, printf)
    
    # calculate the area of a polygon with vertices <vs>
    def area(vs, m=0.5):
      return m * sum(x1 * y2 - x2 * y1 for ((x1, y1), (x2, y2)) in tuples(vs, 2, circular=1))
    
    # solve the puzzle for triangles <ts>, vertex map <m>, vertices <vs>
    # vertices from <vs> should be assigned to make <ts> clockwise triangles
    # return the complete vertex map
    def solve(ts, m, vs):
      # are we done?
      if not ts:
        yield m
      else:
        # choose a triangle to complete next
        t = min(ts, key=lambda t: sum(v not in m for v in t))
        # fill out unallocated vertices
        us = list(v for v in t if v not in m)
        for xs in subsets(vs, size=len(us), select="P"):
          m_ = update(m, us, xs)
          # look for clockwise (= negative area) triangles
          if area((m_[v] for v in t), m=1) < 0:
            yield from solve(ts.difference([t]), m_, vs.difference(xs))
    
    # initial map
    m0 = dict(C=(-1, 1), A=(0, -1))
    
    # remaining vertices
    vs = set(product((-1, 0, 1), repeat=2)).difference(m0.values())
    
    # clockwise (= negative area) triangles
    ts = {"HBC", "DAF", "BGI", "GEA", "HID", "CEF", "CAI", "BED", "FHG"}
    
    # solve the puzzle
    for m in solve(ts, m0, vs):
      # output solutions
      d = reverse(m)
      for y in (1, 0, -1):
        r = list(d.get((x, y), '?') for x in (-1, 0, 1))
        printf("{r}", r=join(r, sep=" ", enc="[]"))
      printf()
    

    Solution: The positions of the churches are as shown:

  2. Frits 10 June 2022 at 8:19 pm

    This program prints 5 solutions which must be manually checked.

       
    from itertools import permutations
    
    ts = {"HBC", "DAF", "BGI", "GEA", "HID", "CEF", "CAI", "BED", "FHG"}
    s_ts = {"".join(sorted(x)) for x in ts}
    
    # circular pairs   example HBC: [HB, BC, CH]
    pairs = [x[i] + x[(i + 1) % 3] for x in ts for i in range(3)]
    
    # check that 3 fields are not on one line 
    def check(vs):
      rows = set("".join(sorted(vs[i][j] for j in range(3))) for i in range(3))
      cols = set("".join(sorted(vs[i][j] for i in range(3))) for j in range(3))
      diags = {"".join(sorted(vs[i][i] for i in range(3))), 
               "".join(sorted(vs[2-i][i] for i in range(3)))}
      return not s_ts.intersection(rows | cols | diags)
    
    # 3x3 matrix
    m = [[""] * 3 for _ in range(3)]
    m[0][0] = "C"
    m[2][1] = "A"
    
    rest = "BDEFGHI"
    
    d = dict()
    
    sols = []
    for p in permutations(rest):
      m[0][1] = p[0]
      m[0][2] = p[1]
      m[1][0] = p[2]
      m[1][1] = p[3]
      m[1][2] = p[4]
      m[2][0] = p[5]
      m[2][2] = p[6]
      
      # check not all 3 fields are on one line  
      if not check(m): 
        continue
        
      # I (CAI) must occur in first column
      if not any("I" == m[i][0] for i in range(3)): continue
        
      # 2 positions at top left may not be CI, etc
      if m[0][1] + m[0][0] in pairs: continue
      
      # 2 positions at top right may not be BE, etc
      if m[0][2] + m[0][1] in pairs: continue
      
      # 2 positions at upper right may not be BE, etc
      if m[1][2] + m[0][2] in pairs: continue
      
      # 2 positions at lower right may not be BE, etc
      if m[2][2] + m[1][2] in pairs: continue
      
      # 2 positions at right bottom may not be BE, etc
      if m[2][1] + m[2][2] in pairs: continue
      
      # 2 positions at lower left may not be IG, etc
      if m[1][0] + m[2][0] in pairs: continue
      
      # 2 top corners may not be BC, etc
      if m[0][2] + m[0][0] in pairs: continue
      
      # 2 bottom corners may not be BI, etc
      if m[2][0] + m[2][2] in pairs: continue
      
      # 2 right corners may not be HB, etc
      if m[2][2] + m[0][2] in pairs: continue
      
      # 2 left corners may not be CH, etc
      if m[0][0] + m[2][0] in pairs: continue
      
      # 2 fields adjacent to C may not be HI, etc
      if m[0][1] + m[1][0] in {x for x in pairs if "C" not in x}: continue
     
      sols.append([m])
     
    for s in sols:
        for x in s[0]:
          print(x)
        print("")  
    
    print("please verify each solution on clockwise order") 
    
    • Jim Randell 10 June 2022 at 10:46 pm

      @Frits: When I run this it prints the same thing 5 times. And it is not the answer to the puzzle.

      Probably because you are overwriting the same list each time. So you just end up with multiple copies of the final state.

      • Frits 10 June 2022 at 11:15 pm

        @Jim, I removed my deep copy statement at last minute. I didn’t notice it messed up the output.

        Using sols.append([[list(row) for row in m]]) at line 76 the correct data is displayed.

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 )

Connecting to %s

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

%d bloggers like this: