# Enigmatic Code

Programming Enigma Puzzles

## Enigma 876: Short circuit

From New Scientist #2031, 25th May 1996 [link]

We spent our holiday on the oddly-shaped island of Hexonia. One day, we drove around the coast road which was in the form of a hexagon with each angle 120°. I remember noticing that each straight was a different perfect square whole number of kilometres and that the complete circuit was less than 500 kilometres.

How far did we drive?

[enigma876]

### 3 responses to “Enigma 876: Short circuit”

1. Jim Randell 20 September 2021 at 8:45 am

This Python program travels the perimeter of the island, using isometric co-ordinates (where the axes are 60° apart).

In order to eliminate duplicate solutions we consider the longest side first, and then the second side should be longer than the last side (otherwise we could start at any vertex and travel in either direction, giving 12 times the number of distinct solutions).

It runs in 274ms.

Run: [ @replit ]

```from enigma import powers, inf, printf

# directions on an isometric grid, going round the hexagon
dirs = [ (1, 0), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1) ]

# new position after side k of length n
def pos(n, k, p=(0, 0)):
(x, y) = p
(dx, dy) = dirs[k]
return (x + n * dx, y + n * dy)

# find a hexagonal path
# sides = available sides
# ss = sides used so far
# t = remaining distance budget
# p = current position
def solve(sides, ss, t, p):
k = len(ss)
# are we done?
if k == 6:
# back where we started?
if p == (0, 0):
yield ss
else:
# choose the next side
for n in sides:
if n < t and n not in ss:
# and solve for the remaining sides
yield from solve(sides, ss + [n], t - n, pos(n, k, p))

# consider the largest square
T = 500
squares = list()
for n in powers(1, inf, 2):
if n > T: break
if len(squares) > 4:
# solve for largest square n, and 5 more squares
for ss in solve(squares, [n], T - n, pos(n, 0)):
if ss > ss[-1]:
printf("{ss} -> {t}", t=sum(ss))
squares.append(n)
```

Solution: The total distance is 420 km.

The sides of the island have the following lengths (in km): 169, 16, 49, 121, 64, 1.

Here is a diagram of the island: 2. Hugh Casement 21 September 2021 at 8:21 am

I’m not sure we need isometric coordinates. The net distances south and east must both be zero:
b + c – e – f = 0, 2(a – d) + b – c – e + f = 0.
If those are six different square numbers with sum less than 500 there is only one sequence, or its cyclic permutations clockwise or anticlockwise. To eliminate most of those duplicate solutions I started with the smallest.

3. GeoffR 22 September 2021 at 11:02 am

Using Hugh’s idea of horizontal and vertical distances, I calculated these distances in terms of the sides of the hexagon, using cos(60) for the horizontal distances and sin(60) for the vertical distances.

Fot the horizontal distances, I got:
S6/2 + S1 + S2/2 = S3/2 + S4 + S5/2

and, for the vertical distances:
S2 * sqrt(3)/2 + S3 * sqrt(3)/2 = S5 * sqrt(3)/2 + S6 * sqrt(3)/2

These equations translate to the two constraints in the code after the all sides square constraint.

```% A Solution in MiniZinc
include "globals.mzn";

predicate is_sq(var int: y) =
exists(z in 1..ceil(sqrt(int2float(ub(y))))) (
z*z = y );

% six sides of the hexagon
var 1..200: S1; var 1..200:S2; var 1..200:S3;
var 1..200: S4; var 1..200:S5; var 1..200:S6;

% make S1 the largest square
constraint S1 > S2 /\ S1 > S3 /\ S1 > S4 /\ S1 > S5 /\ S1  > S6;

constraint all_different ([S1, S2, S3, S4, S5, S6]);

% all sides of the hexagon are squares
constraint is_sq(S1) /\ is_sq(S2) /\ is_sq(S3)
/\  is_sq(S4) /\ is_sq(S5) /\ is_sq(S6);

% all horizontal and vertical distances must balance
constraint S6 + 2*S1 + S2 == S3 + 2*S4 + S5;
constraint S2 + S3 == S5 + S6;

constraint all_different([S1, S2, S3, S4, S5, S6]);

constraint S1 + S2 + S3 + S4 + S5 + S6 < 500;

solve satisfy;

output ["Squares (S1 - S6) in km: " ++ show(S1) ++ ",  "
++ show(S2) ++ ",  " ++ show(S3) ++ ",  " ++ show(S4)
++ ",  " ++ show(S5) ++ ",  " ++ show(S6) ++
"\nTotal length of sides(km) =  " ++ show(S1 + S2 + S3 + S4 + S5 + S6)];

% Squares (S1 - S6) in km: 169,  16,  49,  121,  64,  1
% Total length of sides(km) =  420
% ----------
% Squares (S1 - S6) in km: 169,  1,  64,  121,  49,  16
% Total length of sides(km) =  420
% ----------
% ==========

```

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