# Enigmatic Code

Programming Enigma Puzzles

## Enigma 325: Clear thin circuit

From New Scientist #1473, 12th September 1985 [link]

An n-circuit is drawn on a triangular grid made up of equilateral triangles. It is a closed path of n different points and n different legs. Every leg runs along a grid-line and every point is a junction of grid-lines. Legs do not overlap, but they may cross.

A clear circuit is one that you cannot make a circuit with just some of the points. Thus the 5-circuit A is not clear. Points 1, 2 and 5 would make a 3-circuit: so would points 3, 4 and 5. But B is clear.

The fatness of a circuit is the area it encloses. Thus A has fatness 5 (measured by the number of little triangles enclosed), and B has fatness 7.

Can you find a clear 9-circuit with a fatness of 9 (or less)?

Happy Christmas from Enigmatic Code!

[enigma325]

### One response to “Enigma 325: Clear thin circuit”

1. Jim Randell 25 December 2015 at 8:12 am

I thought this was an interesting puzzle to solve programatically.

Firstly we have to deal with the triangular grid (rather than the more normal rectilinear one). I used a similar approach to that in Enigma 175, where I consider grid axes that are 60° apart.

Then we have to write code that will generate “clear” circuits with the required number of legs. I generate circuits with increasing maximum leg lengths.

And finally we have to compute enclosed area of a (possibly) self-crossing circuit. My approach was to construct a box on the grid that encloses the shape, and then label all the triangles inside that box. We start by labelling a triangle on the outside of the shape with 0, then we label all adjacent triangles with 0 or 1 according to whether the shared edge of the adjacent triangles is part of the perimeter of the shape. If the shared edge is not included in the shape, then the value remains unchanged. But if the shared edge is included in the shape then value changes (from 0 to 1, or 1 to 0).

Here is my Python program. It finds the first solution to the puzzle in 7.5s, but you can leave it running to find more solutions.

```# points are represented by a triangular grid with 60 degrees between the axes
#
# so points that correspond to legs in the circuit differ by multiples of one
# of the following three "directions": (0, 1), (1, 0), (1, -1)
#
# an edge between two adjacent points is represented by a pair consisting of
# those two points
#
# a grid triangle in represented by the three points that make up its vertices

from itertools import count
from enigma import irange, tuples, printf

# can points p0 and p1 be connected along grid lines
# return (<point>, <direction>, <number of edges>)
def connected(p0, p1):
((x0, y0), (x1, y1)) = (p0, p1)
if x0 == x1:
if y0 < y1:
return (p0, (0, +1), y1 - y0)
else:
return (p1, (0, +1), y0 - y1)
elif y0 == y1:
if x0 < x1:
return (p0, (+1, 0), x1 - x0)
else:
return (p1, (+1, 0), x0 - x1)
elif x0 + y0 == x1 + y1:
if p0 < p1:
return (p0, (+1, -1), x1 - x0)
else:
return (p1, (+1, -1), x0 - x1)
else:
return None

# the edges between two connected points
def edges(p0, p1):
r = connected(p0, p1)
if r is None: return None
((x0, y0), (dx, dy), n) = r
s = list()
for i in irange(1, n):
(x1, y1) = (x0 + dx, y0 + dy)
s.append(((x0, y0), (x1, y1)))
(x0, y0) = (x1, y1)
return s

# generate "clear" n-circuits
# n - number of points remaining to add to the circuit
# m - max leg length
# ps - points in the circuit
# es - edges in the circuit
# d - direction of the previous leg
def generate(n, m, ps, es, d):
# current position
(x, y) = p = ps[-1]
# choose a direction
for (dx, dy) in ((+1, 0), (0, +1), (+1, -1)):
# different from the last direction
if (dx, dy) == d: continue
# choose a length
for i in irange(1, m):
for i in (i, -i):
# the new point
q = (x + i * dx, y + i * dy)

# check it is clear
if any(connected(q, q1) for q1 in ps[1:-1]): continue

# and new edges don't overlap
es1 = edges(q, p)
if es.intersection(es1): continue
es1 = es.union(es1)

# the last point should close the circuit
if n == 1:
es2 = edges(q, ps[0])
if not(es2 is None or len(es2) > m or es1.intersection(es2)):
yield (ps + [q], es1.union(es2))

else:
if connected(q, ps[0]): continue
for s in generate(n - 1, m, ps + [q], es1, (dx, dy)):
yield s

# generate clear n-circuits
def clear_circuits(n):
# consider increasing maximum leg length
for m in count(1):
# shape with an initial leg of length m and a max edge of m
(p0, p) = ((0, 0), (m, 0))
for s in generate(n - 2, m, [p0, p], set(edges(p0, p)), (1, 0)):
yield s

# yield the three grid triangles adjacent to triangle <t>
# returns (<adjacent triangle>, <shared edge>)
((x, y), (x1, y1), _) = t
if x == x1:
yield (((x - 1, y + 1), (x, y), (x, y + 1)), ((x, y), (x, y + 1)))
yield (((x, y), (x + 1, y - 1), (x + 1, y)), ((x, y), (x + 1, y)))
yield (((x, y + 1), (x + 1, y), (x + 1, y + 1)), ((x, y + 1), (x + 1, y)))
else:
yield (((x, y - 1), (x, y), (x + 1, y - 1)), ((x, y), (x + 1, y - 1)))
yield (((x, y), (x, y + 1), (x + 1, y)), ((x, y), (x + 1, y)))
yield (((x + 1, y - 1), (x + 1, y), (x + 2, y - 1)), ((x + 1, y - 1), (x + 1, y)))

# return area enclosed by circuit <ps>
def enclosed(ps, es):

# compute the bounding box
minx = min(x for (x, y) in ps) - 1
maxx = max(x for (x, y) in ps)
miny = min(y for (x, y) in ps) - 1
maxy = max(y for (x, y) in ps)

# generate the triangles in the bounding box
tri = dict()
for y in irange(miny, maxy):
for x in irange(minx, maxx):
tri[((x, y), (x, y + 1), (x + 1, y))] = None
tri[((x, y + 1), (x + 1, y), (x + 1, y + 1))] = None

# label the first triangle
t0 = ((minx, miny), (minx, miny + 1), (minx + 1, miny))
tri[t0] = 0
ts = [t0]

# consider triangles in ts
while ts:
t1s = list()
for t in ts:
v = tri[t]
# and adjacent triangles / edges
if tri.get(t1, -1) is not None: continue
tri[t1] = (v ^ 1 if e in es else v)
t1s.append(t1)
ts = t1s

# count the squares (tri.valueus().count() doesn't work in Python 3)
return sum(1 for x in tri.values() if x == 1)

# generate clear 9-circuits
for (ps, es) in clear_circuits(9):
# calculate the enclosed area
a = enclosed(ps, es)
if a > 9: continue
printf("{ps} enclosed = {a}")
break
```

Solution: Yes – it is possible to find a clear 9-circuit with a fatness of 9 (or less).

The neatest looking solution, with a fatness of 7, is shown below:

The maximum leg length is 4.

This figure was the published solution.

Although there are other solutions, with a maximum leg length of 4, that have a fatness of 9:

It could be argued that, although these shapes are less pleasing to the eye, they are a better fit to the question posed in the puzzle.

There are also solutions with a maximum leg length of 5 that also have a fatness of 9:

(Of course the shapes given can be reflected and/or rotated to give similar solutions).

For other Enigmas that have fun on triangular grids see: Enigma 82, Enigma 144, Enigma 175, Enigma 1774.

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