# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1225: Rows are columns

From New Scientist #2381, 8th February 2003 [link]

First draw a chessboard. Now number the horizontal rows 1, 2, …, 8 from top to bottom and number the vertical columns 1, 2, …, 8 from left to right. You have to put a whole number in each of the sixty-four squares, subject to the following:

1. No two rows are exactly the same.
2. Each row is equal to one of the columns, but not to the column with the same number as the row.
3. If N is the largest number you write on the chessboard then you must also write 1, 2, …, N−1 on the chessboard.

The sum of the sixty-four numbers you write on the chessboard is called your total.

What is the largest total you can obtain?

[enigma1225]

### 4 responses to “Enigma 1225: Rows are columns”

1. Jim Randell 16 June 2015 at 8:12 am

A similar problem was published as Enigma 1248, so, having already solved that I was able to adapt my code to solve this problem.

This Python program runs in 664ms.

```from collections import Counter
from itertools import permutations
from enigma import irange, Accumulator, chunk, printf

# merge <s> with <t> in grid <g>
def merge(g, s, t):
for (i, x) in enumerate(g):
if x == s:
g[i] = t

# create an N x N grid with specified rows and columns equated
# rcs - list of (r, c) (0-indexed)
def grid(N, rcs):
# label the squares
n = 1
# make the grid
g = [0] * (N * N)
# equate the rows and columns
for (r, c) in rcs:
for i in irange(0, N - 1):
(ri, ci) = (r * N + i, c + N * i)
if g[ri] == 0:
if g[ci] == 0:
# allocate a new label
g[ri] = g[ci] = n
n += 1
else:
g[ri] = g[ci]
else:
if g[ci] == 0:
g[ci] = g[ri]
elif g[ci] != g[ri]:
# merge the two labels
merge(g, max(g[ri], g[ci]), min(g[ri], g[ci]))
return g

import sys
N = (8 if len(sys.argv) < 2 else int(sys.argv[1]))

r = Accumulator(fn=max)

# choose a permutation
rs = tuple(irange(0, N - 1))
for cs in permutations(rs):
if any(cs[i] == i for i in rs): continue
# generate the grid
g = grid(N, zip(rs, cs))
# no two rows are the same
if len(set(chunk(g, N))) != N: continue
# count the remaining occurrences
c = Counter(g)
# the maximum sum uses the the numbers 1 to N by occurrence order
m = sum(i * n for (i, n) in enumerate(sorted(c.values()), start=1))
r.accumulate_data(m, g)
if r.value == m:
printf("[m={m} {g}]")

printf("max = {r.value}")
```

Solution: The largest possible total for an 8×8 grid is 544.

Here’s an example layout:

In this instance the correspondence between rows and columns is (1, 2, 3, 4, 5, 6, 7, 8) → (2, 1, 4, 3, 6, 5, 8, 7), i.e. alternate pairs are swapped. Each number from 1 to 16 appears 4 times, hence the sum is 4×T(16) = 544.

This puzzle seems to have attracted the attention of academia, and is mentioned in several papers (including a 50 page chapter on a solution in Prolog). In particular:

[2005] “Enigma 1225: Prolog-Assisted Solution of a Puzzle Using Discrete Mathematics”, A. Csenki

[2009] “A Constraint-based Approach to Enigma 1225”, Hadrien Cambazard, Barry O’Sullivan, Barbara M. Smith

The first of these paper uses Prolog’s unification mechanism to process the problem (which is essentially the same process I use in the [[ `grid()` ]] function to equate the rows and columns). The second paper uses a constraint based programming language.

While these papers go on to develop more sophisticated algorithms to attack this particular problem (but they don’t apply to Enigma 1248), it is perhaps surprising how poorly their initial attempts perform. In [2009] it is stated that the run time of their initial algorithm for N=6 is greater than 1 hour, and in [2005] the run time of their initial algorithm for N=8 is 209.6s.

I dug out my 12″ Powerbook (from 2005, so contemporary with the earlier paper) and ran my Python program (using Python 2.7.2) and it runs the N=8 case in 13.5s. Although I don’t pretend my algorithm is sophisticated and will quickly get bogged down for larger values of N.

• Jim Randell 21 June 2015 at 10:42 am

Here’s an alternative program that uses the same technique as my original program to compute the value of the grid, but instead of considering all possible mappings between rows and columns only considers “representative” mappings (as described in the paper [2005]).

This runs much faster and allows us to consider larger grids. For example for N=8 my original program constructed 14833 grids. The program below only constructs 7 grids. So it runs in 46ms for the N=8 case and can be used to consider much larger values for N. (This program deals with values up to 42 in less than a minute).

```from collections import Counter
from enigma import irange, Accumulator, chunk, printf

# merge <s> with <t> in grid <g>
def merge(g, s, t):
for (i, x) in enumerate(g):
if x == s:
g[i] = t

# create an N x N grid with specified rows and columns equated
# rcs - list of (r, c) (0-indexed)
def grid(N, rcs):
# label the squares
n = 1
# make the grid
g = [0] * (N * N)
# equate the rows and columns
for (r, c) in rcs:
for i in irange(0, N - 1):
(ri, ci) = (r * N + i, c + N * i)
if g[ri] == 0:
if g[ci] == 0:
# allocate a new label
g[ri] = g[ci] = n
n += 1
else:
g[ri] = g[ci]
else:
if g[ci] == 0:
g[ci] = g[ri]
elif g[ci] != g[ri]:
# merge the two labels
merge(g, max(g[ri], g[ci]), min(g[ri], g[ci]))
return g

import sys
N = (8 if len(sys.argv) < 2 else int(sys.argv[1]))

# label the rows
rows = tuple(irange(0, N - 1))

# generate non-decreasing sequences that sum to <t> (minimum element <m>)
def decompose(t, m=1):
for i in irange(m, t // 2):
for s in decompose(t - i, i):
yield [i] + s
yield [t]

# generate representative row/column mappings for an n x n grid
def columns(n):
# decompose n
for p in decompose(n, 2):
# partition the rows into cycles
i = 0
ss = []
for j in p:
ss.append(rows[i:i + j])
i += j
# and generate columns assignments
cs = [None] * n
for s in ss:
for (i, j) in zip(s, s[1:] + s[:1]):
cs[i] = j
yield cs

r = Accumulator(fn=max)

# consider representitive columns
for cols in columns(N):
# generate the grid
g = grid(N, zip(rows, cols))
# no two rows are the same
if len(set(chunk(g, N))) != N: continue
# count the remaining occurrences
c = Counter(g)
# the maximum sum uses the the numbers 1 to N by occurrence order
m = sum(i * n for (i, n) in enumerate(sorted(c.values()), start=1))
r.accumulate_data(m, g)
if r.value == m:
printf("[m={m} {g}]")

printf("max = {r.value}")
```

As noted in paper [2009] the maximal solution observed is always the smallest viable decomposition of N. Which would mean (as the decompositions are generated in lexicographical order) that as soon as a solution is found the program could exit. If we do this we can find solutions up to N=450 in under a minute.

2. Brian Gladman 20 June 2015 at 9:31 pm
```from sys import argv
from itertools import permutations

# output a filled grid
def out_grid(g, n):
for r in range(n):
for c in range(n):
print('{:02d}'.format(g[c + n * r]), end=' ')
print()
print()

# fill row (r) in the N by N grid (g) starting with the next
# value (v) such that column cols[r] is equal to row r
def fill_grid(g, r, v, cols, N):
# have we finished?
if r == N:
yield g
else:
# the column in row r
for c in range(N):
# the grid positions (r, c), (c, cols[r]) and (cols[c], r)
# must all be equal
i, j, k = c + N * r, cols[r] + N * c, r + N * cols[c]
# if all three are equal
if g[i] == g[j] == g[k]:
# and all three are not set, set them to the next value
if g[i] == 0:
g[i] = g[j] = g[k] = v = v + 1
else:
continue
# if two are not set, set them to the other (set) value
elif g[i] == g[j] == 0 or g[j] == g[k] == 0 or g[k] == g[i] == 0:
g[i] = g[j] = g[k] = g[i] + g[j] + g[k]
# if only one is not set, the other two must be equal
elif g[i] == 0 or g[j] == 0 or g[k] == 0:
# if they are equal set the unset value to their value
if g[j] == g[k] or g[k] == g[i] or g[i] == g[j]:
g[i] = g[j] = g[k] = (g[i] + g[j] + g[k]) // 2
else:
return
# there is no solution if three set values are not equal
elif len(set((g[i], g[j], g[k]))) > 1:
return
yield from fill_grid(g, r + 1, v, cols, N)

N = 8 if len(argv) < 2 else int(argv[1])

# for the solution count and maximum grid sum
cnt, max_sum = 0, 0
# for each permutation mapping rows to columns
for r2c in permutations(range(N)):
# no row number maps to the same column number
if all(r != c for r, c in enumerate(r2c)):
# find filled grids
for g in fill_grid([0] * N ** 2, 0, 0, r2c, N):
# save the maximum grid sum and the solution count
sm = sum(g)
if sm >= max_sum:
max_sum = sm
cnt += 1
print(sm, r2c)
out_grid(g, N)
print('{} solutions with a maximum grid sum of {}.'.format(cnt, max_sum))
```
• Brian Gladman 20 June 2015 at 10:44 pm

I forget to mention that, for reasons I haven’t worked out yet, my solution above doesn’t work for odd N.

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