# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1204: Small fitogether

From New Scientist #2360, 14th September 2002 [link]

I secretly write the 3×3 square:

I then tell you that the horizontal rows of my square were 231, 312 and 123 and the vertical columns 213, 321 and 132, in some order. If you can work out what my square was then it is called a “fitogether”. (If you check you will see this square is not a fitogether).

Similarly, I can start with any n×n square of numbers where each row and each column contains 1, 2, 3, … n. I tell you the rows and columns in some order and you try to work out my square; if you can, it is called a fitogether. We only consider n if it is at least 2.

The value of a square of numbers is the number obtained by writing the the rows one after the other in order with the top row at the left. For example, the square above has value 312231123.

Find the bottom row of the fitogether with the smallest value.

[enigma1204]

### One response to “Enigma 1204: Small fitogether”

1. Jim Randell 8 September 2015 at 7:48 am

This Python 3 program generates Latin Squares of increasing dimensions, until it finds a size with “fitogethers”, and then finds the smallest one. It runs in 7.5s.

```from collections import defaultdict
from itertools import count
from enigma import irange, Accumulator, printf

# generate permutations of sequence <s>
# exceptions in <xs>
# permutation so far in <p>
def permute(s, xs, p=()):
# are we done?
if not s:
yield p
else:
# choose an element
for (i, e) in enumerate(s):
if e not in xs[0]:
yield from permute(s[:i] + s[i + 1:], xs[1:], p + (e,))

# generate latin squares of size <n> from sequence <s>
# rows so far are in <rs>
def squares(n, s, rs):
# are we done?
if len(rs) == n:
yield rs
else:
# possible next rows
xs = (tuple(zip(*rs)) if rs else [()] * n)
for r in permute(s, xs):
yield from squares(n, s, rs + [r])

# consider increasing n
for n in count(2):
printf("[trying n={n} ...]")

# d maps rows + columns to square
d = defaultdict(list)

r = tuple(irange(1, n))
for rs in squares(n, r, []):
k = tuple(sorted(rs)) + tuple(sorted(zip(*rs)))
d[k].append(rs)
printf("[n={n}: found {t} squares]", t=sum(len(v) for v in d.values()))

# find minimum unique squares
m = Accumulator(fn=min)
for (k, vs) in d.items():
if len(vs) == 1:
m.accumulate(vs[0])

# have we found a solution?
if m.value is not None:
printf("n={n} v={m.value}")
break
```

Solution: The bottom row of the fitogether with the smallest value is 5, 3, 1, 2, 4.

The 5×5 “fitogether” in question is shown below:

Fortunately we don’t have to search very far to find a fitogether, as this program becomes unwieldy above n=5.

The number of Latin Squares LS(n) gets quite big quite quickly as n increases (OEIS A002860):

LS(2) = 2
LS(3) = 12
LS(4) = 576
LS(5) = 161,280
LS(6) = 812,851,200
LS(7) = 61,479,419,904,000
LS(8) = 108,776,032,459,082,956,800