# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1712: Each digit twice From New Scientist #2879, 25th August 2012 [link]

Find the set of perfect squares that between them use each of the digits 0 to 9 exactly twice and whose sum is as small as possible. Your squares must all be different, and 0 may not be a leading digit.

What is the sum of your set of squares?

[enigma1712]

### 11 responses to “Enigma 1712: Each digit twice”

1. Jim Randell 22 August 2012 at 5:22 pm

This struck me as being somewhat similar to Enigma 1536, so I attacked it in a similar way. It runs in 285ms.

```from enigma import irange, split, printf

valid_digits = set('012')

class Puzzle:

# consider squares up to n^2, and increase in chunks of i
def __init__(self, n=50, i=50):
self.chunk = i
self.sum = pow(10, 20)
self.extend(n)

# extend the list of squares up to n^2
def extend(self, n):
self.max = n
# make the list of squares
self.squares = list(i * i for i in irange(n, 1, -1))
# count the digits in each square
self.digits = list(sum(pow(10, i) for i in split(s, int)) for s in self.squares)

# find sets of squares
# ds - digit count
# i - current index into list of squares
# s - sum of squares
# ss - list of squares
def solve(self, ds=0, i=0, s=0, ss=[]):
# are we done?
if ds == 2222222222:
if s < self.sum: self.sum = s
printf("sum={s} squares={ss}", ss=list(reversed(ss)))
return
# find the next candidate square
for j in range(i, self.max):
c = self.squares[j]
# skip sums that are larger than the current smallest
if s + c > self.sum: continue
d = self.digits[j]
# check we have not overused any of the digits
if not set(split(ds + d)).issubset(valid_digits): continue
self.solve(ds + d, j + 1, s + c, ss + [c])

def run(self):
m = self.max
while True:
# choose the largest square
for i in irange(m - 1, 0, -1):
s = self.squares[i]
# if it's larger than the current sum we're done
if not(self.squares < self.sum):
printf("MIN = {self.sum}")
return
# try to find a set including this square
self.solve(self.digits[i], i + 1, s, [s])
# if we've exhausted the list, extend it
n = self.max + self.chunk
printf("extending max square from {self.max} to {n}")
self.extend(n)
m = self.chunk

p = Puzzle()
p.run()
```

Solution: The sum of the set of squares is 2439.

• Jim Randell 23 August 2012 at 10:02 am

The chunking is a bit over the top – it’s much easier to compute the next square then it is the next prime, so it would be cleaner to just go up one square at a time.

Here’s some code that lets you specify the digit count pattern you are looking for, and it keeps a record of the smallest sum it’s found for each digit count as it goes along. So, to solve the original puzzle you would specify the digit count as 2222222222 (which is the default).

```from itertools import count
from enigma import irange, split, printf

import sys
done = 2222222222 if len(sys.argv) < 2 else int(sys.argv)
valid_digits = set(str(x) for x in irange(0, max(split(done, int))))

# map digit count to the smallest sum seen so far
ms = dict()
ms = 0

# go through squares in order
for i in count(1):
s = i * i

# have we completed the exhaustive search?
if done in ms and not(s < ms[done]):
printf("MIN = {m}", m=ms[done])
break

# compute a digit count
d = sum(pow(10, d) for d in split(s, int))

# see if we can improve on any of the current sums
ms2 = ms.copy()
for k, v in ms.items():
dc = k + d
# check we haven't overused any of the digits
if not set(split(dc)).issubset(valid_digits): continue
# see if we already have a smaller sum for this digit count
s2 = s + v
if not(dc in ms and ms[dc] < s2): ms2[dc] = s2
ms = ms2
```

You can use it to determine that the minimum sum using each of the digits 0-9 three times is 6714 and using each of the digits four times the minimum sum is 12528. And (if you have the patience and the RAM) that using each of the digits five times the minimum sum is 17685.

• Jim Randell 5 September 2012 at 9:02 am

Brian further improved this algorithm by encoding the digit count in hexadecimal, rather than decimal, and then using a neat bit of coding to check for overallocation of digits allows the elimination of superfluous intermediate results. So once the sum and largest square is found it becomes viable to re-run the algorithm with a modified digit count to find the next largest square, and so on until the required sequence of squares is determined.

Here is the result of our combined efforts:

```from itertools import count
import sys

done = 0x2222222222 if len(sys.argv) < 2 else int(sys.argv, 16)

def solve(done, maxs):
# map digit count to the smallest sum seen so far
ms = dict()
ms = (0, 0)

# go through squares in order
for i in count(1):
s = i * i

# have we completed the exhaustive search?
if done in ms and not(s < ms[done] and s < maxs):
return ms[done]

# compute a digit count
d = sum(pow(16, int(d)) for d in str(s))

# see if we can improve on any of the current sums
ms2 = ms.copy()
for k, v in ms.items():
dc = k + d
# check we haven't overused any of the digits
if (done - dc) & 0x8888888888: continue
# see if we already have a smaller sum for this digit count
s2 = s + v
if not(dc in ms and ms[dc] < s2): ms2[dc] = (s2, s)
ms = ms2

# set up digit count, largest square, list of squares
dc, s, ss = done, pow(10, 90), []
while dc > 0:
# find the min sum and max square for this digit count
m, s = solve(dc, s)
ss.insert(0, s)
# subtract the digits used in the square from the digit count
dc -= sum(pow(16, int(d)) for d in str(s))
print("sum={m} squares={ss}".format(m=sum(ss), ss=ss))
```

Note that this algorithm will fail when the count of an individual digit exceeds 7, but as the algorithm is quite memory hungry it is more likely that it will run out of memory before this becomes a problem. Particularly when the program is being used to find solutions with homogeneous digit counts (such as required by the original puzzle).

• Jim Randell 12 September 2012 at 7:41 am

After quite a bit of messing around here is what will probably be the final version of this algorithm.

This version packs the digit count into an integer using as few bits as possible, and also includes some tweaks to discard squares where the digit count exceeds the maximum digit count we are looking for. As the main routine is only interested in finding the smallest square for a specific digit count it no longer drags all the squares around, but just records the one for the digit count we’re looking for. And it provides the updates to the dictionary for each pass as a separate dictionary and merges them in at the end of the pass to ensure it doesn’t use a square twice.

It’s still however something of a memory hungry algorithm.

It takes command line arguments so you can specify the number of each digit you want to look for (e.g. as “9876543210” if you want each digit to appear its own number of times) and you can optionally specify the maximum square it should look for as a second argument.

```from itertools import count
from enigma import irange, printf

from math import log, ceil
from functools import reduce
import sys

# command line arguments: [<digit-count> [<max-square>]]
done = '2222222222' if len(sys.argv) < 2 else sys.argv
done = list(int(d) for d in (done.split(',') if ',' in done else done))
assert len(done) == 10, "Digit count length should be 10"

maxs = pow(10, sum(done)) if len(sys.argv) < 3 else int(sys.argv)

# how many bits per digit?
maxd = max(done)
bits = int(ceil(log(1 + maxd, 2)))
base = pow(2, bits)
printf("using {bits} bits per digit (base={base})")

done = reduce(lambda a, b: base * a + b, done, 0)

# digit count of a number (but no digit can exceed maxd)
def digit_count(n):
dc = dict()
for d in str(n):
if d in dc:
if dc[d] == maxd: return None
dc[d] += 1
else:
dc[d] = 1
return sum(v * pow(base, int(k)) for k, v in dc.items())

# check if each digit in b is not more than the corresponding digit in a
def check(a, b):
m = base - 1
while b > 0:
if (b & m) > (a & m): return True
a >>= bits
b >>= bits
return False

def solve(done, maxs):
# map digit count to the smallest sum seen so far
ms = dict()
ms = 0
sq = None

# go through squares in order
for i in count(1):
s = i * i

# have we completed the exhaustive search?
if done in ms and not(s < ms[done] and s < maxs):
return ms[done], sq

# is it impossible?
if not(s < maxs):
raise ValueError('No Solutions')

# compute a digit count for this square
d = digit_count(s)
if d is None or check(done, d): continue

# see if we can improve on any of the current sums
ms2 = dict()
for k, v in ms.items():
# check we haven't overused any of the digits
if check(done - k, d): continue
# see if we already have a smaller sum for this digit count
dc = d + k
s2 = s + v
if not(dc in ms and ms[dc] < s2):
ms2[dc] = s2
if dc == done: sq = s
ms.update(ms2)

# set up digit count, largest square, list of squares
dc, s, ss = done, maxs, []
while dc > 0:
# find the min sum and max square for this digit count
m, s = solve(dc, s)
ss.insert(0, s)
# subtract the digits used in the square from the digit count
dc -= digit_count(s)
# update the maximum allowable digit
maxd = max(int((dc >> (bits * i)) & (base - 1)) for i in irange(0, 9))
printf("sum={m} squares={ss}", m=sum(ss))
```
2. arthurvause 22 August 2012 at 7:07 pm

This one runs a bit slower, but gets the same answer as Jim

```from itertools import combinations as comb

sq1 = [n*n for n in range(1,4)]
sq2 = [n*n for n in range(4,10)]
sq3 = [n*n for n in range(10,32)]

bestsum=99999999
for c1 in range(4):
for c2 in range(7):
if (20-c1-c2*2)%3==0:
c3=(20-c1-c2*2)//3
for com3 in comb(sq3, c3):
for com2 in comb(sq2, c2):
for com1 in comb(sq1, c1):
st=com3+com2+com1
so = ''.join([str(x) for x in st])
so2 = ''.join(sorted(so))
if so2=='00112233445566778899':
newsum=sum(st)
if newsum<bestsum:
print st, sum(st)
bestsum=newsum
```
3. arthurvause 22 August 2012 at 9:12 pm

A faster version:

```from itertools import combinations as comb

sq1 = [n*n for n in range(1,4)]
sq2 = [n*n for n in range(4,10)]
sq3 = [n*n for n in range(10,32)]

def notExceed(numlis):
s=''.join([str(x) for x in numlis])
for n in range(10):
if s.count(str(n)) > 2:
return False
return True

bestsum=99999999
for c1 in range(4):
for c2 in range(7):
if (20-c1-c2*2)%3==0:
c3=(20-c1-c2*2)//3
for com3 in comb(sq3, c3):
if notExceed(com3):
for com2 in comb(sq2, c2):
if notExceed(com3+com2):
for com1 in comb(sq1, c1):
if notExceed(com3+com2+com1):
newsum=sum(com3+com2+com1)
if newsum<bestsum:
print com3+com2+com1, newsum
bestsum=newsum
```
4. briangladman 22 August 2012 at 10:32 pm

Here is my version:

```from operator import add

# square root of the maximum square
max_sqr = 100
# minimum sum of squares so far
min_sum = 10000

# a dictionary of suitable squares indexed on their
# square root, returning a tuple of digit counts
sq = { n : tuple(str(n ** 2).count(d) for d in '0123456789')
for n in range(1, max_sqr) }

# list_srt holds the square roots of the squares used so far
# dig_cnt is a tuple of the digit counts for these squares

global min_sum

top, sqr_sum = list_srt[-1], sum(x * x for x in list_srt)
while True:
top += 1
if top >= max_sqr:
return
if top not in sq:
continue

# new sum with the current square
new_sum = sqr_sum + top ** 2
# exit if this is larger than the current minimum
if new_sum >= min_sum:
return

# calculate the digit counts if this square is added
# skip this square if any digit count is greater than two
if any(x > 2 for x in dc):
continue

# check if we have a solution (all diigits used twice)
if all(x == 2 for x in dc):
# is its sum below the current minimum?
if new_sum <= min_sum:
# if so store the new minimum and print output
min_sum = new_sum
print(new_sum, tuple(x * x for x in list_srt[1:] + [top]))
else:
# otherwise try to add another value to our list

```
5. Naim Uygun 23 August 2012 at 1:13 am
```#Here is my version for Enigma 1712

from itertools import combinations
squares=list()
x=int(input("How many perfect squares numbers :"))
for i in range(1,x):
squares.append(i*i)

for q in range(2,x):
print(" Checking combination : ",q)
for c in combinations(squares,q):
top=sum(c)
if  top %9 != 0: continue
s=""
for i in range(0,q):
s=s+str(c[i])

u=len(s)
if u != 20: continue

l=list(s)
durum= True
for i in range(0,10):
if l.count(str(i))!=2:
durum=False
break

if durum==True:print(c,top)
```
6. Jim Randell 28 April 2013 at 12:03 am

If you’re short on time or RAM, and you have PyMathProg installed you can program up a solver to use GLPK to solve this Enigma. The following Python code (similar to my GLPK solution to Enigma 1536) can find solutions for squares using each digit from 1 to 10 times in under 500ms.

```import pymprog
from enigma import irange, sqrt, printf

# digits
digits = list(irange(0, 9))

# find a solution for primes up to maxp
def solve(ds, maxs):

squares = list(i * i for i in irange(1, int(sqrt(maxs))))

# map squares to digit counts
dc = dict()
for n in squares:
s = str(n)
dc[n] = list(s.count(str(d)) for d in digits)

# create the model
m = pymprog.model('enigma1712')

# we need a decision variable for each square
x = m.var(squares, 'x', bool)

# objective: minimise the sum of the squares used
m.min(sum(n * x[n] for n in squares))

# constraints: each digit is used the required number of times
m.st([sum(dc[n][d] * x[n] for n in squares) == ds[d] for d in digits])

# find a solution
try:
m.solve(int)
except RuntimeError:
return None

# which squares are used?
ss = list(n for n in squares if bool(x[n].primal))
s = sum(ss)

printf("sum={s} {ss}")
return s

import sys
ds = '2222222222' if len(sys.argv) < 2 else sys.argv
ds = list(int(d) for d in (ds.split(',') if ',' in ds else ds))
assert len(ds) == 10, "Digit count length should be 10"

# increase the max square until it's larger than the best solution
n = 10000
while True:
s = solve(ds, n)
if s is not None and not(n < s): break
n *= 10

printf("min sum = {s}")
```
7. arthurvause 28 April 2013 at 5:16 pm

Here is a version of 1712 using the technique of my recursive solution to 1536.

This one constructs the optimal search sequence of digits in code (the sequence being the increasing frequency of the digit in the list of squares).

The performance is improved significantly by the converting the “containingsingle” and “containingdouble” entries to lists, so that smaller numbers are used first.

The program runs in about 90 ms

```
from  itertools import combinations as combs

def notexceed(s):
set_s = set(s)
set_s.remove(" ")
for n in set_s:
if s.count(n) > 2:
return False
return True

squares = [n*n for n in xrange(100) if all(str(n*n).count(str(i))<3 for i in xrange(10)) ]
containingsingle = *10
containingdouble = *10
for n in xrange(10):
containingsingle[n] = [ str(x) for x in squares if str(x).count(str(n))==1 ]
containingdouble[n] = [ str(x) for x in squares if str(x).count(str(n))==2 ]

frequencies = sorted([ (len([1 for x in squares if str(x).count(str(n))]),n) for n in xrange(10)])
seq = [n for (f,n) in frequencies]

global besttotal

if total>besttotal:
return

L = len(s)-s.count(" ")
if L>20:
return

if L==20:
if notexceed(s):
besttotal=total
print "result", s, ", Total=",total
return

if n==10:
return

if notexceed(s):

d=seq[n]
d_sofar = s.count(str(d))
if d_sofar==0:
for p,q in combs(containingsingle[d],2):

for p in containingdouble[d]:

elif d_sofar==1:
for p in containingsingle[d]: