# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1466: Crossed words

From New Scientist #2627, 27th October 2007

I have just made up a small crossword for our local newspaper. It is a square grid of traditional style with fewer than a quarter of the small squares shaded and the rest to be filled by “across” and “down” answers. The pattern of shaded squares has “180° symmetry”, i.e. if you rotate it through 180° about its central point, the layout looks the same.

The lengths of the answers, in the usual crossword order, are:

Across: 3 5 3 3 3 3 3 5 3
Down: 6 3 7 7 6 3

and two of the answers are CROSSED and WORDS.

(a) What is the size of the grid (e.g. 11 by 11)?
(b) What are the clue numbers for ‘CROSSED’ and ‘WORDS’ (e.g. 6 Down and 12 Across)?

[enigma1466]

### 2 responses to “Enigma 1466: Crossed words”

1. Jim Randell 4 February 2013 at 7:58 am

The following Python program runs in 1.5s (under PyPy) and produces partially filled out grid.

```from itertools import combinations, product
from enigma import irange, printf

ACROSS = [3, 5, 3, 3, 3, 3, 3, 5, 3]
DOWN = [6, 3, 7, 7, 6, 3]

# find spaces for crossword solutions
# return a list of: (<clue-number>, <A or D>, <solution-length>, <grid-position>)
def spaces(g, n, n2):
(p, r, i) = (0, [], 1)
# find a blank
while p < n2:
if g[p] == '_':
(a, d) = (0, 0)
# could it start an across solution?
if p % n == 0 or g[p - 1] != '_':
# find the end of it
(q, qm) = (p + 1, n * (1 + p // n))
while q < qm and g[q] == '_': q += 1
a = q - p
if a > 1: r.append((i, 'A', a, p))
# could it start a down solution?
if p < n or g[p - n] != '_':
# find the end of it
q = p + n
while q < n2 and g[q] == '_': q += n
d = (q - p) // n
if d > 1: r.append((i, 'D', d, p))
if a > 1 or d > 1: i += 1
p += 1
return r

# attempt to fit the solutions into the grid
def fit(g, n, *s):
# copy the grid
f = list(g)
# attempt to fit the solutions in
for (w, x) in s:
if len(w) != x[2]: return None
i = x[3]
for c in w:
if not(f[i] == c or f[i] == '_'): return None
f[i] = c
i += (1 if x[1] == 'A' else n)
return f

# there are 7 letter down clues, so we need at least a 7 x 7 grid
# also there are an odd number of across clues, so the grid must have odd dimensions

# there are 9 across clues with 31 letters, and they all must
# intersect with at least one (down) clue, and there are 6 down clues
# with 32 letters, so, the maximum number of letter squares on any
# grid is: 31 + 32 - max(9, 6) = 54

# on a 9x9 grid that means at least 27 squares need to be shaded, but the maximum
# number of shaded squares allowed is 20 (9^2 / 4), hence the only possible grid
# is 7x7.

n = 7
n2 = n * n
# we need to fill out at most 1/4 of the squares
# and as the grid is symmetrical we only need to position half of them
for f in irange(0, n2 // 8):
# so fill out some of the squares
for s in combinations(irange(0, n2 // 2), f):
# make a grid with those squares filled out
g = ['_'] * n2
for i in s:
g[i] = g[n2 - i - 1] = '#'
# find the solutions on the grid
s = spaces(g, n, n2)
# check they fit the required solutions
if list(i[2] for i in s if i[1] == 'A') != ACROSS: continue
if list(i[2] for i in s if i[1] == 'D') != DOWN: continue
# attempt to fill out CROSSED and WORDS
s7 = list(i for i in s if 7 in (i[1], i[2]))
s5 = list(i for i in s if 5 in (i[1], i[2]))
for (c, w) in product(s7, s5):
f = fit(g, n, ('CROSSED', c), ('WORDS', w))
if f:
# print the solution
printf("{n}x{n} grid, CROSSED={c[0]}{c[1]}, WORDS={w[0]}{w[1]}\n")
# print the grid
for i in range(0, n2, n):
print(''.join(f[i:i + n]))
print()
```

Solution: (a) the grid is 7×7; (b) CROSSED is the solution to 3 Down, and WORDS is the solution to 5 Across.