# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1740: Sudoprime

From New Scientist #2908, 16th March 2013 [link]

The grid above shows a cross-figure with two digits given as a start. The 11 answers are distinct primes and none has a leading zero. No digit appears more than once in any row, column or either of the two long diagonals.

What are the numbers in the shaded regions?

[enigma1740]

### 11 responses to “Enigma 1740: Sudoprime”

1. Jim Randell 13 March 2013 at 8:31 pm

This (not very pretty) Python program runs in 60ms. It’s somewhat similar to my original solution of Enigma 1730.

```# in the grid:
#
#  A # # # B
#  C D # E F
#  # G H J #
#  K L # M N
#  P # # # Q
#
# the primes are:
# p1 = AC, p2 = BF, p3 = CD, p4 = DGL, p5 = EF, p6 = EJM
# p7 = GHJ, p8 = KL, p9 = KP, p10 = MN, p11 = NQ

from enigma import Primes, is_duplicate, printf

# record 1, 2, 3 digit primes
ps = [ None, [], [], [] ]
for n in Primes(999):
p = str(n)
if not is_duplicate(p):
ps[len(p)].append(p)

# p7 is a 3-digit prime with 9 in the middle
for p7 in ps[3]:
if p7[1] != '9': continue
# p4 is a 3-digit prime with p7[0] in the middle
for p4 in ps[3]:
if p4[1] != p7[0]: continue
# p6 is a 3-digit prime with p7[2] in the middle
for p6 in ps[3]:
if p6[1] != p7[2]: continue
# p3 is a 2-digit prime ending in p4[0]
for p3 in ps[2]:
if p3[1] != p4[0]: continue
# p1 is now defined, so check it's a 2-digit prime
p1 = '5' + p3[0]
if p1 not in ps[2]: continue
# p5 is a 2-digit prime starting with p6[0]
for p5 in ps[2]:
if p5[0] != p6[0]: continue
# check all the digits in row 2 are different
if is_duplicate(p3 + p5): continue
# p8 is a 2-digit prime ending with p4[2]
for p8 in ps[2]:
if p8[1] != p4[2]: continue
# p9 is a 2-digit prime starting with p8[0]
for p9 in ps[2]:
if p9[0] != p8[0]: continue
# check all the digits in column 1 are different
if is_duplicate(p1 + p9): continue
# p2 is a 2-digit prime ending with p5[1]
for p2 in ps[2]:
if p2[1] != p5[1]: continue
# check all the digits in row 1 are different
if p1[0] == p2[0]: continue
# check all the digits in the NE/SW diagonal are different
if is_duplicate(p2[0] + p5[0] + p7[1] + p4[2] + p9[1]): continue
# p10 is a 2-digit prime starting with p6[2]
for p10 in ps[2]:
if p10[0] != p6[2]: continue
# check all the digits in row 4 are different
if is_duplicate(p8 + p10): continue
# p11 is a 2-digit prime starting with p10[1]
for p11 in ps[2]:
if p11[0] != p10[1]: continue
# check all the digits in row 4 are different
if p9[1] == p11[1]: continue
# check all digits in column 4 are different
if is_duplicate(p2 + p11): continue
# check all digits on the NW/SE diagonal are different
if is_duplicate(p1[0] + p3[1] + p7[1] + p6[2] + p11[1]): continue
if len(set((p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11))) != 11: continue

printf("p6={p6} p9={p9} [p1={p1} p2={p2} p3={p3} p4={p4} p5={p5} p7={p7} p8={p8} p10={p10} p11={p11}]")
```

Solution: The numbers in the shaded regions are 617 and 41.

• Jim Randell 14 March 2013 at 11:44 am

Here’s a recursive approach that runs in 79ms. So it’s a little bit slower, but it was more interesting to program.

```# in the grid:
#
#  A # # # B
#  C D # E F
#  # G H J #
#  K L # M N
#  P # # # Q

from enigma import irange, Primes, is_duplicate, printf

# label the indices to make things easier
(A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = irange(0, 14)

# digits that form primes
primes = (
(A, C), (K, P), (B, F), (N, Q),
(C, D), (E, F), (K, L), (M, N),
(D, G, L), (G, H, J), (E, J, M)
)

# groups of distinct digits
groups = (
(A, B), (C, D, E, F), (G, H, J), (K, L, M, N), (P, Q),
(A, C, K, P), (D, G, L), (E, J, M), (B, F, N, Q),
(A, D, H, M, Q), (B, E, H, L, P)
)

# 2- and 3-digit primes without repeated digits
ps = [None, set(), set(), set()]
for p in Primes(999):
s = str(p)
if is_duplicate(s): continue

# output a solution
def output(g):
(A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = g
printf("{A} # # # {B}\n{C} {D} # {E} {F}\n# {G} {H} {J} #\n{K} {L} # {M} {N}\n{P} # # # {Q}")
printf("{E}{J}{M} {K}{P}\n")

# match numbers in ns to the template t
def match(t, ns):
for n in ns:
if all(a in ('?', b) for (a, b) in zip(t, n)):
yield n

# return an updated grid with digits in template t set to n
def update(g, t, n):
g = list(g)
for (i, d) in zip(t, n):
g[i] = d
return g

# check that groups don't have repeating digits
def check(g):
for d in groups:
s = tuple(g[i] for i in d if g[i] != '?')
if len(s) > 0 and len(set(s)) < len(s): return False
return True

# solve a grid
def solve(g):
# are we done?
if '?' not in g:
# check the numbers are distinct primes
ns = set(''.join(g[i] for i in p) for p in primes)
if len(ns.intersection(ps[2].union(ps[3]))) == len(primes):
output(g)
return
# find a partially filled out prime
for p in primes:
t = tuple(g[i] for i in p)
if 0 < t.count('?') < len(t): break
# and fill it out
for n in match(t, ps[len(p)]):
g2 = update(g, p, n)
if check(g2): solve(g2)

#           ABCDEFGHJKLMNPQ
solve(list('5??????9???????'))
```

If you relax the condition that all 11 primes are distinct there is a second solution.

• Jim Randell 31 July 2013 at 9:59 pm

Here’s a version written using the generic cross figure solver the code for which I put up in my solution for Enigma 1760. It runs in 70ms.

```# consider the grid:
#
#  A # # # B
#  C D # E F
#  # G H J #
#  K L # M N
#  P # # # Q

from enigma import CrossFigure, irange, Primes, is_duplicate, printf

# label the indices to make things easier
(A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) = irange(0, 14)

# 2- and 3-digit primes without repeated digits
primes = Primes(1000)
p2s = list(p for p in primes.range(10, 99) if not is_duplicate(p))
p3s = list(p for p in primes.range(100, 999) if not is_duplicate(p))

#                ABCDEFGHJKLMNPQ
p = CrossFigure('5??????9???????')
# solutions that are 2-digit primes
p.set_answer([(A, C), (K, P), (B, F), (N, Q), (C, D), (E, F), (K, L), (M, N)], p2s)
# solutions that are 3-digit primes
p.set_answer([(D, G, L), (G, H, J), (E, J, M)], p3s)
# no digit is repeated in a row, column or diagonal
p.set_distinct([
(A, B), (C, D, E, F), (G, H, J), (K, L, M, N), (P, Q),
(A, C, K, P), (D, G, L), (E, J, M), (B, F, N, Q),
(A, D, H, M, Q), (B, E, H, L, P)
])

# final check: all answers in the grid are distinct
def check(p, grid):
p.set_check(lambda grid: check(p, grid))

# solve it
for (A, B, C, D, E, F, G, H, J, K, L, M, N, P, Q) in p.solve():
printf("[{A} # # # {B}]\n[{C} {D} # {E} {F}]\n[# {G} {H} {J} #]\n[{K} {L} # {M} {N}]\n[{P} # # # {Q}]")
printf("{E}{J}{M} {K}{P}\n")
```
2. Brian Gladman 13 March 2013 at 10:36 pm

Mine is similar except that I did more work up front to save time later (hopefully!)

```# grid layout
# 5  X  X  X  a
# b  c  X  d  e
# X  f  9  g  X
# h  i  X  j  k
# l  X  X  X  m

from collections import defaultdict as dfd
from enigma import Primes

p2_tens, p2_unit = dfd(list), dfd(list)
p3_hnrd, p3_tens, p3_unit = dfd(list), dfd(list), dfd(list)

for p in Primes(1000):
if p < 10:
continue
elif p < 100:
# compute two digit primes xy and store (xy, (x, y), set(x, y))
# when x != y in dictionaries indexed on x and y
digits = (p // 10, p % 10)
t = (p, digits, frozenset(digits))
if len(t[2]) == 2:
p2_unit[p % 10] += [t]
p2_tens[p // 10] += [t]
else:
# compute three digit primes xyz and store (xy, (x, y, z), set(x, y, z))
# when x <> y <> z in dictionaries indexed on x, y and z
digits = (p // 100, (p // 10) % 10, p % 10)
t = (p, digits, frozenset(digits))
if len(t[2]) == 3:
p3_unit[p % 10] += [t]
p3_tens[(p // 10) % 10] += [t]
p3_hnrd[p // 100] += [t]

# now set values progressively, checking for distinct primes
# and for different digits in rows as they are completed
for _5b, (_, b), dgt_5b in p2_tens[5]:
# select bc from 2 digit primes with tens digit b
for bc, (b, c), dgt_bc in p2_tens[b]:
if bc == _5b:
continue
# select cfi from 3 digit primes with hundreds digit c
for cfi, (_, f, i), dgt_cfi in p3_hnrd[c]:
# select hi from 2 digit primes with units digit i
for hi, (h, _), s_hi in p2_unit[i]:
if hi in (_5b, bc):
continue
# select hl from 2 digit primes with tens digit h
for hl, (_, l), dgt_hl in p2_tens[h]:
if hl in (_5b, bc, hi) or dgt_5b & dgt_hl:
continue
# select f9g from 3 digit primes with hundreds digit f
for f9g, (f, _, g), dgt_f9g in p3_hnrd[f]:
if f9g == cfi or _ != 9:
continue
for dgj, (d, _, j), dgt_dgj in p3_tens[g]:
if dgj in (cfi, f9g):
continue
# select de from 2 digit primes with tens digit d
for de, (_, e), dgt_de in p2_tens[d]:
if de in (_5b, bc, hi, hl) or dgt_bc & dgt_de:
continue
# select de from 2 digit primes with units digit e
for ae, (a, _), dgt_ae in p2_unit[e]:
if ae in (_5b, bc, hi, hl, de) or a == 5:
continue
# select jk from 2 digit primes with tens digit j
for jk, (_, k), dgt_jk in p2_tens[j]:
if jk in (_5b, bc, hi, hl, de, ae) or s_hi & dgt_jk:
continue
# select km from 2 digit primes with tens digit k
for km, (_, m), dgt_km in p2_tens[k]:
if km in (_5b, bc, hi, hl, de, ae, jk) or dgt_ae & dgt_km:
continue

# now check the last row and the two diagonals
if (l == m or len(set((5, c, 9, j, m))) != 5 or
len(set((a, d, 9, i, l))) != 5):
continue
# print the grid and the answer
print(' {:2d}  X  X  X {:2d}'.format(5, a))
print(' {:2d} {:2d}  X {:2d} {:2d}'.format(b, c, d, e))
print('  X {:2d} {:2d} {:2d}  X '.format(f, 9, g))
print(' {:2d} {:2d}  X {:2d} {:2d}'.format(h, i, j, k))
print(' {:2d}  X  X  X {:2d}'.format(l, m))
```
3. ahmet çetinbudaklar 14 March 2013 at 6:03 am

Starting from 5 and moving vertically then horizontally one gets 3 possibilities.
Then taking care of the diagonal from bottom left to top right amd moving from 3-digit lowest primes one can reach the answer quite easily

4. saracogluahmet 28 June 2013 at 12:49 pm
```
#In Fact, I did code this for the second version of the puzzle... The same algorithm does work for twos.
#My algorithm is based upon traversing the grid one cell by one, and the tour starts at (0,0) denoting the top left corner of the grid.
#It moves (0,0), (1,0),(1,1),(2,1),(3,1),(3,0),(4,0),(0,4),(1,4)....................
#The search is a depth-search and the algorithm is a recursive backtracking algorithm
grid=[[-2]*5 for i in range(5)]#This is the grid
grid[0][0],grid[2][2]=5,9#given the constraints in the puzzle

#start= [0][0]
path=[[0,0,1,0],[1,0,1,1],[1,1,2,1],[2,1,3,1],[3,1,3,0],[3,0,4,0],[4,0,0,4],
[0,4,1,4],[1,4,1,3],[1,3,2,3],[1,3,3,3],[3,3,3,4],[3,4,4,4],[4,4,-1,-1]]

primes=[-1]*14
counter=0

#if The number is prime
def IsPrime(number):

root=(int)(pow(number,0.5))+1
for i in range(2,root):
if number%i==0:
return False
return True

#Convert digits to number at base 10
def CalculateNumber(X,X1,Y,Y1,way):
Sum,coeff=0,1

for i in range(X,X1+way,way):
for j in range(Y,Y1+way,way):
Sum=Sum+(grid[i][j]*coeff)
coeff*=10

return Sum

def valid(X,Y,X1,Y1,Item,nxt):
global counter
Sum,count=0,0

counter+=1

#print(X,Y,X1,Y1,Item)

#This is for checking the row, column and diagonals constraint given in the puzzle
for i in range(5):
if (Y1!=i):
if grid[X1][i]==Item:
return False

if (X1!=i):
if grid[i][Y1]==Item:
return False

if (X1!=i) and (Y1!=i)and (X1==Y1):
if grid[i][i]==Item:
count+=1
if count>0:
return False
count=0

if (X1+Y1)==4:
if X1!=i and grid[i][4-i]==Item:
count+=1
if count>0:
return False

if (X1==2 and Y1==1): #If the move is at the center of the grid, it certainly must have 9 at that cell, in order not to change that cell's value.
return True

if X1==3 and Y1==1:
X=1

if X1==1 and Y1==4:
X,X1=0,1

Xc=X1-X #How many digits have
Yc=Y1-Y

if Xc>0:
Sum=CalculateNumber(X1,X,Y1,Y,-1)
elif Xc<0:
Sum=CalculateNumber(X,X1,Y,Y1,1)
elif Yc>0:
Sum=CalculateNumber(X,X1,Y1,Y,-1)
elif Yc<0:
Sum=CalculateNumber(X,X1,Y,Y1,-1)

if grid[0][4]==0 or grid[1][1]==0 or grid[1][3]==0 or grid[3][0]==0 or grid[3][3]==0 or grid[2][1]==0:
return False #No leading ones int the grid

if IsPrime(Sum): # The digits converted into base here for being checked if the converted number is  prime or not.
primes[counter]=Sum

return True

return False

def Distinct():
count=[0]*1000
for i in range(13):
prime=primes[i]
if prime>i:
count[prime]+=1
if count[prime]>1:
return False
return True

def Solve(x,y,x1,y1,nxt):
global counter

if x1==-1 and y1==-1:
if Distinct():#Primes are distinct given in the puzzle.
print(grid)
return
for i in range(10):
grid[x1][y1]=i

if valid(x,y,x1,y1,i,nxt):
x,y,x1,y1=path[nxt][0],path[nxt][1],path[nxt][2],path[nxt][3]
Solve(x,y,x1,y1,nxt+1)
#Backtracking occurs in the following
x,y,x1,y1=path[nxt-1][0],path[nxt-1][1],path[nxt-1][2],path[nxt-1][3]
counter-=1
grid[x1][y1]=-2

#Stars from the top corner of the grid.
Solve(0,0,1,0,1)
```
5. geoffrounce 20 July 2017 at 4:16 pm

Answers were (41 and 617) and (47 and 617)

```% A Solution in MiniZinc

% grid references used - shaded regions jn and eil
% 5 X X X b
% c d X e f
% X g 9 i X
% j k X l m
% n X X X p

include "globals.mzn";

% parameter variables
int: a = 5;
int: h = 9;

% decision variables
var 1..9:b;  var 1..9:c;   var 0..9:d;   var 1..9:e;  var 0..9:f;
var 1..9:g;  var 0..9:i;   var 1..9:j;   var 0..9:k;  var 1..9:l;
var 1..9:m;  var 0..9:n;   var 0..9:p;

var 100..999 : dgk = 100*d + 10*g + k;
var 100..999 : ghi = 100*g + 10*h + i;
var 100..999 : eil = 100*e + 10*i + l;

var 10..99 : ac = 10*a + c;
var 10..99 : jn = 10*j + n;
var 10..99 : bf = 10*b + f;
var 10..99 : mp = 10*m + p;
var 10..99 : jk = 10*j + k;
var 10..99 : cd = 10*c + d;
var 10..99 : ef = 10*e + f;
var 10..99 : lm = 10*l + m;

% predicate is_prime
predicate is_prime(var int: x) = x > 1 /\
forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) (
(i < x) -> (x mod i > 0));

% 2-digit Primes
set of int: primes = {11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

constraint cd in primes /\ ef in primes /\ is_prime(ghi) /\ jk in primes
/\ lm in primes /\ ac in primes /\ jn in primes
/\ is_prime(dgk) /\ is_prime(eil) /\ bf in primes /\ mp in primes;

constraint alldifferent ([a,b]) /\ alldifferent([c,d,e,f])
/\ alldifferent ([g,h,i]) /\ alldifferent([j,k,l,m])
/\ alldifferent([n,p]) /\ alldifferent([a,c,j,n])
/\ alldifferent ([d,g,k]) /\ alldifferent([e,i,l])
/\ alldifferent([b,f,m,p]) /\ alldifferent([a,d,h,l,p])
/\ alldifferent([b,e,h,k,n]);

solve satisfy;

output[ "Shaded area values: " ++ show(jn) ++ " and " ++ show(eil) ++ "\n"
++ show(a) ++ "XXX" ++ show(b) ++ "\n"
++ show(cd) ++ "X" ++ show(ef) ++ "\n"
++ "X" ++ show(ghi) ++ "X" ++ "\n"
++ show(jk) ++ "X" ++ show(lm) ++ "\n"
++ show(n) ++ "XXX" ++ show(p)] ;

% Shaded area values: 41 and 617
% 5XXX4
% 31X67
% X691X
% 43X71
% 1XXX3

% Shaded area values: 47 and 617
% 5XXX4
% 31X67
% X691X
% 43X71
% 7XXX3
% Finished in 57msec

```
• Jim Randell 20 July 2017 at 4:24 pm

@geoff: Your second solution has 47 in it twice, so is disallowed as all 11 answers have to be different primes. (I think this check is missing from your MiniZinc model).

Here’s a run-file that solves the problem using the SubstitutedExpression() solver from the enigma.py library. The conditions that the primes are all different are checked in line 27 and line 31.

```#!/usr/bin/env python -m enigma -r

#
#  A # # # B
#  C D # E F
#  # G H J #
#  K L # M N
#  P # # # Q
#

SubstitutedExpression

--distinct=""
--assign="A,5"
--assign="H,9"

# the 11 answers are distinct primes
"is_prime(AC)"
"is_prime(BF)"
"is_prime(CD)"
"is_prime(EF)"
"is_prime(KL)"
"is_prime(MN)"
"is_prime(KP)"
"is_prime(NQ)"
"all_different(AC, BF, CD, EF, KL, MN, KP, NQ)"
"is_prime(DGL)"
"is_prime(EJM)"
"is_prime(GHJ)"
"all_different(DGL, EJM, GHJ)"

# no digit appears more than once in any row column or diagonal
"all_different(A, B)"
"all_different(C, D, E, F)"
"all_different(G, H, J)"
"all_different(K, L, M, N)"
"all_different(P, Q)"
"all_different(A, C, K, P)"
"all_different(D, G, L)"
"all_different(E, J, M)"
"all_different(B, F, N, Q)"
"all_different(A, D, H, M, Q)"
"all_different(B, E, H, L, P)"
```
6. saracogluahmet 20 July 2017 at 4:36 pm

Oh it was 2013, how are you all? I hope you all great, best wishes

• Jim Randell 20 July 2017 at 10:36 pm

@ahmet: Enigmatic Code is still here. Although New Scientist stopped publishing new Enigma puzzles at the end of 2013, I am putting up two puzzles a week (sometimes three) from New Scientist back issues, and there are now over 1000 puzzles on the site. There are about 700 Enigma puzzles left for me to post, so it’ll keep me busy for a while longer.

7. saracogluahmet 21 July 2017 at 11:51 am

@Jim You are doing good job, as soon as I find an occasion, I will be here, I have been following you, have a nice day