# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1163: Clean up the square

From New Scientist #2319, 1st December 2001 [link]

Delete two of the three occurrences of each letter in the square (above), so that you leave one letter in each row and in each column.

Look at the square you obtain. What is the letter in the top row, the letter in the second row, …, the letter in the bottom row, in that order?

[enigma1163]

### 3 responses to “Enigma 1163: Clean up the square”

1. Jim Randell 13 June 2016 at 8:29 am

This Python 3 program runs in 41ms.

```from enigma import irange, chunk, join

# dimensions of the grid
N = 9

# related squares
related = []
for i in irange(0, N * N - 1):
rs = set()
# related squares are in the same row and same column
(r, c) = divmod(i, N)
rs.update(j + r * N for j in irange(0, N - 1))
rs.update(j * N + c for j in irange(0, N - 1))
# but not the square itself
related.append(rs)

# remove elements from the grid
def remove(grid, rs):
g = list(grid)
for i in rs:
g[i] = '_'
return g

def solve(grid, s):
# are we done?
if not s:
yield grid
else:
# find occurrences of the next letter
ps = list(p for (p, x) in enumerate(grid) if x == s[0])
# choose one of the occurrences to keep
for (i, p) in enumerate(ps):
# remove the other occurrences
# and any letters in related squares
rs = related[p].union(ps[:i], ps[i + 1:])
# provided we are not removing any earlier letters
if any(grid[j] < grid[p] for j in rs): continue
yield from solve(remove(grid, rs), s[1:])

# we choose _ to represent empty squares, so that it compares as
# greater than any of the letters
grid = list(
'_C___G__B' +
'___B__EG_' +
'D_I___A__' +
'___F_I__E' +
'_A__FH___' +
'__C___F_D' +
'H_B____C_' +
'_I_HE____' +
'G___A__D_'
)

# find solutions for the given grid
for g in solve(grid, 'ABCDEFGHI'):
for r in chunk(g, N):
print(join(r))
print()
```

Solution: The remaining letters in each row, from top to bottom, are: G, B, A, E, F, C, H, I, D.

There is only one solution for the grid, shown below:

2. arthurvause 13 June 2016 at 10:37 am

For 9 letters each occuring 3 times, it is feasible to do a brute force search of the 3**9 = 19683 possible options of distinct letters, but this solution wouldn’t be scalable.

```from itertools import product
from collections import defaultdict

square =  [list( x ) for x in
['.C...G..B' ,
'...B..EG.' ,
'D.I...A..' ,
'...F.I..E' ,
'.A..FH...' ,
'..C...F.D' ,
'H.B....C.' ,
'.I.HE....' ,
'G...A..D.']]

positions = defaultdict(list)
for i in xrange(9):
for j in xrange(9):
if square[i][j] != '.':
positions[square[i][j]].append((i,j))

for p in  product(*[positions[x] for x in positions]) :
if len(set( x for (x,y) in p))==9:
if len(set( y for (x,y) in p))==9:
print ''.join([ square[x][y] for (x,y) in sorted(p)])
```
3. Brian Gladman 13 June 2016 at 5:35 pm
```# the size of the grid
M = 9

def solve(s, lev):
if lev == 9:
# all letters have been processed
yield s
else:
# select the next letter and find its positions
ch = 'ABCDEFGHI'[lev]
ixs = (i for i, c in enumerate(s) if c == ch)
# try each letter position as that remaining
for ix in ixs:
# compile a new grid with other copies of this letter removed
ss = [c if c != ch or i == ix else '-' for i, c in enumerate(s)]

# since there is only one letter in each row and column, we
# can now remove other letters from them for this position
rr, cc = divmod(ss.index(ch), M)
for i in range(M):
if ss[M * rr + i] not in (ch, '-'):
ss[M * rr + i] = '-'
if ss[M * i + cc] not in (ch, '-'):
ss[M * i + cc] = '-'

# check that all rows and columns have at least one letter
if (all(s[i : i + M].count('-') != M for i in range(0, M * M, M)) and
all(s[i : M * M : M].count('-') != M for i in range(M))):
yield from solve(ss, lev + 1)

# the initial grid
sq = list( '-C---G--B'  '---B--EG-'  'D-I---A--'
'---F-I--E'  '-A--FH---'  '--C---F-D'
'H-B----C-'  '-I-HE----'  'G---A--D-' )

# find solutions with one letter in each row and column
for s in solve(sq, 0):
ss = ''.join(s)
for r in range(0, M * M, M):
print(ss[r : r + 9])
print()
```

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