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.

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