# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1260: Latin fives

From New Scientist #2416, 11th October 2003 [link]

Your task today is to put one letter C, L, X, V or I into each of the 25 squares in the grid so that each row and each column (read downwards) forms a different valid Roman numeral. The sum of the numbers in the rows is to equal the sum of the numbers in the columns. Use the smallest number of Cs you can. As a hint, one of your diagonals will be a valid Roman numeral and the other will contain only one letter.

What are:

(a) the sum of the numbers in the rows (or columns); and
(b) the Arabic value of the valid diagonal?

[enigma1260]

### 2 responses to “Enigma 1260: Latin fives”

1. Jim Randell 27 January 2015 at 8:14 am

This Python program runs in 53ms.

```from collections import defaultdict
from enigma import irange, int2roman, roman2int, Accumulator, printf

# collect 5-letter roman numerals by prefix
romans = defaultdict(list)
for i in irange(1, 399):
r = int2roman(i)
if len(r) == 5:
for i in irange(0, 5):
romans[r[:i]].append(r)

# count the C's
m = Accumulator(fn=min)

# rs = rows
# cs = columns
# nr = number of rows
# nc = number of columns
# cr = count of C's in rows
# cc = count of C's in columns
def solve(rs, cs, nr, nc, cr, cc):
if nr == 5:
# sum the rows and columns
rsi = tuple(roman2int(x) for x in rs)
csi = tuple(roman2int(x) for x in cs)
sr = sum(rsi)
sc = sum(csi)
if sr == sc:
# count the C's
m.accumulate_data(cr, rs)
if cr == m.value:
printf("{cr}: {rs} => {rsi} => {sr}, {cs} => {csi} => {sc}", rs=' '.join(rs), cs=' '.join(cs))
else:
# prefix for the next row
pr = ''.join(x[nr] for x in cs)
if pr not in romans: return
# prefixes for remaining columns
pcs = tuple(''.join(rs[j][i] for j in irange(0, nr - 1)) for i in irange(nc, 4))
if any(x not in romans for x in pcs): return
# choose the next row
for r in romans[pr]:
# make sure it's not already used
if r in rs or r in cs: continue
# if it exceeds the current best C count then give up
n = r.count('C')
if m.value is not None and cr + n > m.value: continue
# and it's possible to complete remaining columns
if any(p + x not in romans for (p, x) in zip(pcs, r[nc:])): continue
# move on to the next column
solve(cs, rs + [r], nc, nr + 1, cc, cr + n)

solve([], [], 0, 0, 0, 0)
print(m)
```

Solution: (a) The sum of the numbers in the rows (or the columns) is 536. (b) The Arabic value of the valid diagonal is 162.

There are 5,816 ways of filling out the grid with Roman Numerals (although any solution will also appear with the rows and columns interchanged, so the are essentially 2,908 different ways to fill out the grid).

Four of these ways use only 3 C’s. These are the grids shown below (along with their reflections along the leading diagonal):

2. Brian Gladman 29 January 2015 at 8:52 am

I really enjoyed this one and I tried quite a few different approaches, most using the same ‘prefix’ based approach that you adopted. I tried a pure row based approach and also on based on starting with the centre row and column. But nothing matched the speed of the alternating row/column approach that you used so I ended up with a solution that closely follows your own.

```from collections import defaultdict

# for storing roman numerals in range 1..399 by prefix
rnb = defaultdict(list)
# for the integer value of a roman numeral
val = dict()
# The range here is 1..399 because all roman numerals
# outside this range have more than five characters
for n in range(1, 400):
h, x = divmod(n, 100)
s = 'C' * h
q, r = divmod(x, 10)
for i, t in enumerate((q, r)):
u, v = 'XI'[i], 'LV'[i]
if t == 9:
s += u + 'CX'[i]
elif t >= 5:
s += v
t -= 5
if 1 <= t < 9:
s += u + v if t == 4 else u * t
if len(s) == 5:
# for converting roman numerals to integers
val[s] = n
# store roman numerals in a map from their
# prefixes
for i in range(6):
rnb[s[:i]] += [s]

# for the current minimum nomber of 'C's used
min_c = None

# fill in the grid recursively, alternating between
# rows and columns
#   rows - the rows completed so far (number = nr)
#   cols - the columns completed so far (number = nc)
#
def fill_in(rows, cols, nr, nc):
global min_c
# do we have a complete grid?
if nr == 5:
# exit if we have more 'C's than our current minimum
c_cnt = ''.join(rows).count('C')
if min_c and c_cnt > min_c:
return
# check if the row and column sums are the same
sum_rows = sum(val[x] for x in rows)
if sum_rows == sum(val[x] for x in cols):
# form the two diagonals
fd = ''.join(rows[i][i] for i in range(5))
rd = ''.join(rows[i][4 - i] for i in range(5))
# check that one has five equal characters and
# that the other is a valid roman numeral
if len(set(fd)) == 1 and rd in val:
diag = val[rd]
elif len(set(rd)) == 1 and fd in val:
diag = val[fd]
else:
return
# return a solution if we have found one with a
# new minimum number of 'C's
# return the solution
if not min_c or c_cnt <= min_c:
min_c = c_cnt
yield sum_rows, diag, rows
else:
# from the columns so far, find the first 'nr' characters
# in row 'nr' and use this to find all roman numerals that
# can be placed in this row
for r in rnb[''.join(x[nr] for x in cols)]:
rr = rows + [r]
# exit if we have more 'C's than the current minimum
c_cnt = ''.join(rr).count('C')
if min_c and c_cnt > min_c:
return
# skip if we have a duplicate roman numeral or any of the
# partially completed columns from row 'nr' upwards cannot
# form a valid five character roman numeral
if (r in rows or r in cols or
any(''.join(x) not in rnb for x in tuple(zip(*rr))[nr:])):
continue
# now switch rows and columns and move to next row/column
yield from fill_in(cols, rr, nc, nr + 1)

for sum_rows, diag, rows in fill_in([], [], 0, 0):
print(sum_rows, diag, rows)
```

But there are (again!) some practical differences as I am not convinced that the checks you make on lines 36 and 39 are needed because we have not yet added another row (column) and we have already checked that the columns (rows) can be completed from this position when we added the previous row (column). I certainly find the same 5816 solutions without these checks (for a modified solver that doesn’t check the diagonals or the numbers of ‘C’s) although that is no guarantee that my logic here is correct.