# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1529: Square corbel

From New Scientist #2692, 24th January 2009 [link]

I invite you to fill in the grid with non-zero digits so that each row is a perfect square with different digits and each row contains all the digits in all rows below it. In no case must a digit be identical with the one below or above it. This can be done in several different ways.

(a) Find an example with the number in the top row divisible by 3.

(b) Find an example in which the number in the right-hand column is palindromic.

In each case what is the number in the top row?

[enigma1529]

### 2 responses to “Enigma 1529: Square corbel”

1. Jim Randell 15 July 2012 at 5:55 pm

My original Perl code is too ugly and too slow (and too embarrassing) to show. Here’s a recursive solution in Python. It runs in 48ms.

```from itertools import count
from collections import defaultdict
from enigma import is_duplicate, concat, printf

# find squares up to 5 digits, and store them by length and digits
squares = defaultdict(lambda: defaultdict(list))
for i in count(1):
n = str(i * i)
l = len(n)
if l > 5: break
if '0' in n or is_duplicate(n): continue
squares[l][tuple(sorted(n))].append(n)

# check a list for a solution
a, b = set(), set()
def check(l):
n = list(int(x) for x in l)
# (a) the top row is divisible by 3
if n[0] % 3 == 0:
printf("(a) {n}")
# (b) the right column is palindromic
p = concat(*(x[-1] for x in l))
if p[::-1] == p:
printf("(b) {n}")

def solve(i=1, l=[], d=set()):
# are we done?
if i == 6:
check(l[::-1])
return
# try and add another layer
for ds, ns in squares[i].items():
ds = set(ds)
# digits in the new layer should superset the previous layer
if not ds.issuperset(d): continue
for n in ns:
# and no digit can be in the same position as the previous layer
if i > 1 and any(n[-j] == l[-1][-j] for j in range(1, i)): continue
solve(i + 1, l + [n], ds)

solve()
printf("a: {a}, b: {b}")
```

Solution: (a) 13689, (b) 96721.

2. Brian Gladman 16 July 2012 at 4:26 pm

I don’t normally try the old ones that you publish but this one caught my interest. Here is my version:

```from itertools import permutations

sqr = {str(x * x):1 for x in range(1, 100)}

def solve(s, seq, l3, lp):
ln = len(s) - 1
if not ln:
# if in last row check the single digit is a non-zero square
if s in sqr:
# form solution as a tuple of integers
t = tuple(map(int, seq[:] + [s]))
# add to l3 if the top row is divisible by three
if t[0] % 3 == 0:
l3 += [t]
# add to lp if the last column is a paalindrome
if not (t[0] - t[4]) % 10 and not (t[1] - t[3]) % 10:
lp += [t]
else:
# now permute digits of s to find squares with one less digit
for p in permutations(s, ln):
sq = ''.join(p)
# check for a square and that its digits don't match those above
if sq in sqr and all(sq[i] != s[i + 1] for i in range(ln)):
# and repeat for the next lower row
solve(sq, seq + [s], l3, lp)

# output solutions in grid format
def outs(h, s):
print(h)
for j in range(5):
print(''.join('{0:7d}'.format(s[i][j]) for i in range(len(s))))

l3, lp = [], []
for i in range(100, 317):
sq = str(i * i)
if '0' not in sq and len(set(sq)) == 5:
solve(sq, [], l3, lp)
outs('The top row is divisible by three:', l3)
outs('The last column is a palindrome:', lp)
```