# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1755: Sudoprime II

From New Scientist #2923, 29th June 2013 [link] The grid shows a cross-figure with two digits given as a start. All 11 two- and three-digit answers are prime and none has a leading zero; no digit appears more than once in any row, column or either of the two long diagonals; no even digit appears more than once anywhere.

What are the numbers in the shaded regions?

This puzzle is similar to Enigma 1740 and Enigma 1730 (both also set by Peter Chamberlain).

[enigma1755]

### 28 responses to “Enigma 1755: Sudoprime II”

1. Jim Randell 26 June 2013 at 7:23 pm

A slightly modified version of my recursive solver for Enigma 1750 solves this in 84ms.

```# 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("{G}{H}{J} {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 no even digit appears more than once
if not any(g.count(d) > 1 for d in '02468'):
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('7?????3????????'))
```

Solution: The numbers in the shaded regions are 307 and 41. • Des 26 July 2013 at 7:59 am

Isn’t zero an even digit?

• Jim Randell 26 July 2013 at 9:03 am

Yes, zero is an even digit. But it only appears once in the solution grid, so that’s OK.

I took the phrase “no even digit appears more than once anywhere” to mean “there cannot be more than one occurrence of any particular even digit in the solution grid; there may multiple even digits in the solution grid (but each of them will have to be a different digit)”, rather than “there cannot be more than one even digit in the solution grid”.

There are no solutions if the latter interpretation is used.

• Jim Randell 31 July 2013 at 9:46 pm

I wrote a generic cross-figure solver (the code for which is given in my solution for Enigma 1760). Here’s a solution to this problem using that code. 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('7?????3????????')
# 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: no even digit is repeated
p.set_check(lambda grid: not any(grid.count(d) > 1 for d in '02468'))

# 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("{G}{H}{J} {K}{P}\n")
```
2. saracogluahmet 28 June 2013 at 1:19 pm
```#This is the same algorithm for the first version of this enigma

grid=[[-2]*5 for i in range(5)]#This is the grid
grid,grid=7,3#given the constraints in the puzzle

#start= 

# I move along this path, this means, 0,0 to 1,0 and 1,0 to 1,1
path=[[0,0,1,0],[1,0,1,1],[1,1,3,1],[3,1,3,0],[3,0,4,0],[4,0,2,2],[2,1,2,3],[2,3,0,4],
[0,4,1,4],[1,4,1,3],[1,3,3,3],[3,3,3,4],[3,4,4,4],[4,4,-1,-1]]

primes=[-1]*14
counter=0

def IsPrime(number):

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

#Digits are converted to a number in the corresponding cells
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

#This one is to be able to check the constaints saying that there must not be double of an item in the same row, and....
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:
return False

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

if (X1==2 and Y1==2):
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 grid==0 or grid==0 or grid==0 or grid==0:
return False

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)

# whether the number being got is prime or not
if IsPrime(Sum):
#print("prime",Sum,"X=",X,"X1=",X1,"Y=",Y,"Y1=",Y1)
primes[counter]=Sum
return True

return False

#Only a certain digit may be used once given in the puzzle, it is a controversial point I guess
def Distinct():
count=*10
for i in range(5):
for j in range(5):
item=grid[i][j]
if item>0:
if item%2==0:
count[item]+=1
if count[item]>1:
return False
return True

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

if x1==-1 and y1==-1:
if Distinct():
print(grid)
return
for i in range(10):
grid[x1][y1]=i
#print(nxt)
if valid(x,y,x1,y1,i,nxt):
x,y,x1,y1=path[nxt],path[nxt],path[nxt],path[nxt]
#print("next",nxt,i)
Solve(x,y,x1,y1,nxt+1)
#Backtracking occurs below...
x,y,x1,y1=path[nxt-1],path[nxt-1],path[nxt-1],path[nxt-1]
counter-=1
grid[x1][y1]=-2
Solve(0,0,1,0,1)
```
• saracogluahmet 28 June 2013 at 1:26 pm

The execution time of the algorithm above on my machine is about 15 miliseconds, I guess that is really fast..

• Brian Gladman 29 June 2013 at 1:04 pm

This one is rather long but it is quite fast:

```# digit positions are numbered 0 .. 14 from top left to bottom right

from primes import Primes

# two and three digit primes with no repeated digits
prms = Primes().list(10, 1000)
prms = [x for x in prms if len(str(x)) == len(set(str(x)))]

# the digit positions for the eleven primes
pr_ix = ((0, 2), (1, 5), (2, 3), (4, 5), (9, 10), (11, 12), (9, 13),
(12, 14), (6, 7, 8), (3, 6, 10), (4, 8, 11))

# the positions in the same rows, columns and diagonals
rows = ((0, 1), (2, 3, 4, 5), (6, 7, 8), (9, 10, 11, 12), (13, 14))
cols = ((0, 2, 9, 13), (3, 6, 10), (4, 8, 11), (1, 5, 12, 14))
diag = ((0, 3, 7, 11, 14), (1, 4, 7, 10, 13))

# remove 'digit' from allowed values in a row, column or diagonal
def rem(digit, position, friends_list, d):
for friends in friends_list:
if position in friends:
for friend in friends:
if friend != position:
d[friend] -= set((digit,))

# remove 'digit' from the possible values for other positions
# in rows, columns and diagonals that include it
def remove(digit, position, d):
e = d.copy()
rem(digit, position, rows, e)
rem(digit, position, cols, e)
rem(digit, position, diag, e)
return e

# check if all completed numbers in the grid are prime
def test_primes(g, p_ix):
for t in p_ix:
# compile digits for this prime
ps = ''.join(str(g[i]) for i in t)
# if it is complete but it is not prime
if not ('None' in ps or int(ps) in prms):
return False
# all completed numbers are prime
return True

# compile a dictionary of the possible digit values for
# each grid position
dmap = dict()
for position in range(15):
# for each prime in the grid
for digit_indexes in pr_ix:
# if this position is the last digit of a prime, it
# can only be 1, 3, 7 or 9
if position == digit_indexes[-1]:
dmap[position] = set((1, 3, 7, 9))
break
else:
# otherwise allow any digit
dmap[position] = set(range(10))

# remove 7 and 3 from as possible values for positions
# in the same rows, columns and diagonals
dmap = remove(3, 6, remove(7, 0, dmap))

# place a digit in grid 'g' with a map in 'dmap' giving
# the possible values for each position
def solve(g, dmap):
# we have more values to set
if None in g:
# find a position with the fewest possible values
min_len, min_pos = 1000, -1
for position, val in enumerate(g):
if val == None and len(dmap[position]) < min_len:
min_len, min_pos = len(dmap[position]), position
# try these values in this position
for v in tuple(dmap[min_pos]):
# add this value to a new copy of the grid
new_g = g[:]
new_g[min_pos] = v
# and test if all the complted numbers are prime
if test_primes(new_g, pr_ix):
# continue to place digits with an updated map
solve(new_g, remove(v, min_pos, dmap))
else:
# check that any even digits are not used more than once
if all(g.count(x) < 2 for x in range(0,10, 2)):
# output the answer and the corresponding grid
print('{:d}{:d}{:d} and {:d}{:d}'.format(g, g, g, g, g))
print('{:2d} # # #{:2d}'.format(g, g))
print('{:2d}{:2d} #{:2d}{:2d}'.format(g, g, g, g))
print(' #{:2d}{:2d}{:2d} #'.format(g, g, g))
print('{:2d}{:2d} #{:2d}{:2d}'.format(g, g, g, g))
print('{:2d} # # #{:2d}'.format(g, g))

# set an empty grid
g = [None] * 15
# and add 7 and 3 to it
g, g = 7, 3
# now solve for other digit positions
solve(g, dmap)
```
• Ahmet Saracoğlu 29 June 2013 at 6:02 pm

Hi Brian, what is the execution time of it?

• Brian Gladman 29 June 2013 at 7:07 pm

If I replace lines 1 to 7 with

```# digit positions are numbered 0 .. 14 from top left to bottom right

from enigma import Primes

# two and three digit primes with no repeated digits
prms = [x for x in Primes(1000) if len(str(x)) == len(set(str(x))) > 1]
```

so that Jim’s enigma can be used, I then get PyPy 2.0.2 timings for Jim’s, your’s and mine of 1040, 980 and 30 milliseconds respectively (this is on a 1.8GHz i7 laptop). On CPython 3.3 I get 250, 240 and 31 milliseconds respectively.

These are timings using Python’s CProfile module. My experience is that timings vary wildly between machines and Python versions so the different versions have to be run on the same machine using the saame timing approach to be meaningful. Even then I am not very convinced about the results.

• Ahmet Saracoğlu 29 June 2013 at 7:13 pm

I see, frankly when ı get the 15 ms on my machine which is 2.6 ghz laptop, I dont need to optimize more, however your codes execution time on my machine is 45 ms

• Brian Gladman 29 June 2013 at 10:01 pm

Hi Ahmet,

Jim timed his own version, your version and mine and got yours and his similar and mine aboutr twice the speed. I have timed them and I have also asked two colleagues to do so and all the results are reasonably close to those that Jim has reported.

But you are suggesting that my version takes three times as long on your machine as your version – 45 ms compared with 15 ms. So something that others find to be about twice as fast, you are measuring as three times slower – a factor of six different!

Since this seems very unlikely, it suggests that there may be something wrong with the way you are measuring running times.

• Ahmet Saracoğlu 29 June 2013 at 10:12 pm

Ok, then I am going to post the output, that is impossible that my code’s execution time is 90ms, it is working just 15 ms on my machine, and yours is about 45 ms, and one thing, if the execution time is not so important, then no need to talk about it, this is just python, and a child play for me, the point is to construct a good algortihm, and I believe that I am succesfull at construcing good one, in my opinion, then no need to talk about the execution times, because nobody can prove their execution time, and it is really dependent on the processors speed, I know that mine is working on my machine in 15 ms, I dont know and can not know the rest 🙂

• Brian Gladman 29 June 2013 at 10:49 pm

It is not the algorithm that I am seeking to explain. I am seeking to understand how a program that seems to be about twice as fast for a number of people is three times slower for you! I suspect that this is a problem with timing but it could be something else. Either way it would be useful to know why this is as it may tell us something.

I am timing in the following way. I have a batch file called ‘profile.bat’ in the same directory as my Python files. It contains the two lines:

@echo off
“c:\program files\python33\python” -mcProfile -scumulative %1

I then run a command prompt (a DOS window) in this directory and enter the command:

profile ns1755.py

where ns1755.py is the name of the program being timed.

How are you producing your timing results?

• Ahmet Saracoğlu 30 June 2013 at 7:53 am

What I am trying to understand is the same as you did tell me the differences of the execution times between two different machines, on my machine my code’s execution time is about 15 ms, how is it possible to be 90 ms on other machine, this is 6 times slower, that is unbelievable. I guess if I do not misunderstand that your code, you have a prime a list given on the top of the code, you have not coded a function of primarility test,

As to my timing issue, I run the code on the Python editor, as I showed you before, and although there is overhead because of the editor itself, when I use the time function on my code, it gives me a 15ms on my machine,now the point is this, how is it possible for it to be working on a diiferent machine with the 6 times slower execution time than mine

• Jim Randell 29 June 2013 at 6:19 pm

For comparison I ran the same timing tests that I run for my own code on this one and it comes out at 92ms. So the running times are very similar.

As I noted in my solution for Enigma 1740 you can write a faster program for solving this kind of problem, but I find the more general algorithm to be more interesting to program.

Personally I’m happy with any code that runs in under 100ms, as that’s pretty much instantaneous.

• Ahmet Saracoğlu 29 June 2013 at 6:33 pm

Hi Jim, which one do you mean, mine or Brian s?

• Jim Randell 29 June 2013 at 6:37 pm

@Ahmet: I’m referring to the code you posted above (28 June 2013 at 1:19 pm).

• Ahmet Saracoğlu 29 June 2013 at 6:51 pm

I do not know, my execution time is 15 ms on my machine, I can post the image of the output if you wish, and also I can speed up mine, if you have noted that, I did not use some constraints like the prime numbers end wirh the 1 3 7 9 and some other stuff, anyway, i dont know how yo do test the codes

• Jim Randell 29 June 2013 at 7:15 pm

I don’t doubt the times you report. I was just running your code under the same environment to give a comparable figure. The code Brian published (with a little tweak to use the [[ `Primes` ]] class from enigma.py) came in at 44ms.

As noted on the Notes page I time all phases of the command execution, so it’s quite hard to get a runtime reported of less than around 30ms.

But for me the challenge is not about coming up with the fastest executing program, or the shortest program, but a program that is easy to understand and that runs fast enough and doesn’t take too long to write. For this puzzle I just adapted a program I’d written for a previous puzzle, so it only took me a few minutes to come up with a viable program, and it ran in less than 100ms, so I was happy with it.

• Ahmet Saracoğlu 29 June 2013 at 7:32 pm

I agree with you, the previous puzzle is so similar to this, I did code this first, after, İ did code the previous one in a few minutes, and I agree with you about the point is algorithm, and sure execution time, the code might be longer but the execution time does matter

3. saracogluahmet 1 July 2013 at 10:02 am
```def Run():
for i in range(100000):
mul=i+10

for j in range(10):
Run()

```

This one’s execution time on my machine is about 260ms,what about on yours?

• Jim Randell 2 July 2013 at 1:23 pm

That would come out as 97ms on my machine.

```% mtime python test.py
python test.py  0.11s user 0.01s system 96% cpu 0.123 total
python test.py  0.10s user 0.01s system 96% cpu 0.121 total
python test.py  0.11s user 0.01s system 96% cpu 0.123 total
python test.py  0.11s user 0.01s system 96% cpu 0.126 total
python test.py  0.11s user 0.01s system 96% cpu 0.123 total
python test.py  0.11s user 0.01s system 97% cpu 0.131 total
python test.py  0.10s user 0.01s system 96% cpu 0.118 total
python test.py  0.09s user 0.01s system 96% cpu 0.099 total
python test.py  0.09s user 0.01s system 96% cpu 0.101 total
python test.py  0.09s user 0.01s system 96% cpu 0.103 total
python test.py  0.08s user 0.01s system 96% cpu 0.097 total
python test.py  0.10s user 0.01s system 96% cpu 0.116 total
python test.py  0.11s user 0.01s system 96% cpu 0.124 total
python test.py  0.10s user 0.01s system 96% cpu 0.117 total
python test.py  0.08s user 0.01s system 95% cpu 0.098 total
python test.py  0.09s user 0.01s system 95% cpu 0.108 total
16 runs: best 97.0ms, worst 131.0ms, avg=114.2ms
```

I wouldn’t get too hung up on comparing runtimes though, as they will vary depending on the hardware, operating system, Python version and what else is running on the machine at the time. I only report them as a rough guide to the amount of computation involved in determining the solution.

Python has its own `timeit` module for doing more detailed calculation of the runtimes of code fragments, but I like using the shell’s `time` command as it gives me a reasonable basis for comparison between programs written in different languages. (I used to do Enigma problems in Perl).

4. Ahmet Saracoğlu 3 July 2013 at 6:35 pm
```#This is the second version of the same algorihm, just changed the path....
import time
print(time.time())
grid=[[-2]*5 for i in range(5)]#This is the grid
grid,grid=7,3#given the constraints in the puzzle

#start= 

# I move along this path, this means, 0,0 to 1,0 and 1,0 to 1,1
path=[[0,0,1,1],[1,1,3,3],[3,3,4,4],[4,4,4,0],[4,0,3,1],[3,1,2,3],[2,3,1,3],[1,3,1,0],
[1,0,1,4],[1,4,0,4],[0,4,2,2],[2,2,3,0],[3,0,3,4],[3,4,-1,-1]]

flag=False

def IsPrime(number):

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

#Digits are converted to a number in the corresponding cells
def CalculateNumber(X,X1,Y,Y1,coeff):
Sum=0
for i in range(X,X1):
for j in range(Y,Y1):
Sum=Sum+(grid[i][j]*coeff)
coeff//=10
return Sum

def valid(X,Y,X1,Y1,Item,nxt):

Sum=0

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:
return False

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

if X1==2 and Y1==2:
return (IsPrime(CalculateNumber(2,3,1,4,100)))

if X1==1 and Y1==3 and Item!=0:
return (IsPrime(CalculateNumber(1,4,3,4,100)))

if X1==3 and Y1==0 and Item!=0:
return(IsPrime(CalculateNumber(3,5,0,1,10)))

if X1==0 and Y1==4 and Item!=0:
return(IsPrime(CalculateNumber(0,2,4,5,10)))

if Item not in [1,3,7,9]:
return False

#This one is to be able to check the constaints saying that there must not be double of an item in the same row, and....

if X1==1 and Y1==0:
return(IsPrime(CalculateNumber(0,2,0,1,10)))

if X1==3 and Y1==1:
return(IsPrime(CalculateNumber(1,4,1,2,100)))

if X1==1 and Y1==4:
return(IsPrime(CalculateNumber(1,2,3,5,10)))

if X1==3 and Y1==4:
return(IsPrime(CalculateNumber(3,5,4,5,10)))
return True

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

global flag

if x1==-1 and y1==-1:
print(grid)
return

if flag==False:
for i in range(10):
grid[x1][y1]=i
#print(nxt)
if valid(x,y,x1,y1,i,nxt):
x,y,x1,y1=path[nxt],path[nxt],path[nxt],path[nxt]
#print("next",nxt,i)
if nxt==13:
flag=True
Solve(x,y,x1,y1,nxt+1)
#Backtracking occurs below...
x,y,x1,y1=path[nxt-1],path[nxt-1],path[nxt-1],path[nxt-1]

grid[x1][y1]=-2

Solve(0,0,1,1,1)
print(time.time())
```

I changed the path array, I have been moving on the diagonals first, and this one’s execution time on my machine is about 15ms…

5. saracogluahmet 8 July 2013 at 2:00 pm

This one is java version with the same algorithm and it is a simulation of the depth first search,

```import java.awt.*;
import java.applet.Applet;

/*
*/

public class LineApplet extends Applet implements Runnable {
public TextField [] f=new TextField;

int K=-1;
int [][] grid=new int[];
int cellnumber=0,value=7;

int [][] path={{0,0,1,0},{1,0,1,1},{1,1,3,1},{3,1,3,0},{3,0,4,0},{4,0,2,2},{2,1,2,3},{2,3,0,4},
{0,4,1,4},{1,4,1,3},{1,3,3,3},{3,3,3,4},{3,4,4,4},{4,4,-1,-1}};

// Set the size of the applet...
public void init() {
int i,j;
resize(300,300);
for (i=0;i<25;i++){
f[i]=new TextField();
}
for (i=0;i<5;i++){
grid[i]=new int;
for (j=0;j<5;j++){
grid[i][j]=-2;
}
}
grid=7;
grid=3;
t.start();

}

public void run() {
if (K==-1){
K=-2;
Solve(0,0,1,0,1);
}
}

public void stop(){
t=null;
}

public void paint(Graphics g){
int X=40,Y=40,count=0;
f.setText(Integer.toString(7));
f.setText(Integer.toString(3));

for (int i=0;i<5;i++){
for(int j=0;j<5;j++){
f[count].setSize(40, 40);
f[count].setBackground(Color.white);
f[count].setEditable(false);
/*f[count].setBackground(Color.red);*/

f[count++].setLocation(X,Y);
X+=40;
}
Y+=40;
X=40;
}

f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);
f.setBackground(Color.black);

if (K==-2){
f[cellnumber].setText(Integer.toString(value));
f[cellnumber].setBackground(Color.yellow);
}

}
// Run the thread. Lines everywhere!

public boolean IsPrime(double number){
int root=(int)(Math.pow(number, 0.5)+1);

if (number==0)
return false;

int i;
for (i=2;i<=root;i++){
if (number%i==0)
return false;
}
return true;
}

public int CalculateNumber(int X,int X1,int Y,int Y1,int way){
int Sum=0,coeff=1,i,j;

if (way>0)
{
for (i=X;i<X1+way;i+=way){
for (j=Y;j<Y1+way;j+=way){
Sum=Sum+(grid[i][j]*coeff);
coeff*=10;
}
}
}
else {
for (i=X;i>X1+way;i+=way){
for(j=Y;j>Y1+way;j+=way){
Sum=Sum+(grid[i][j]*coeff);
coeff*=10;
}
}
}
return Sum;
}

public boolean Valid(int X,int Y,int X1,int Y1,int Item,int nxt){
int Sum=0,i,Xc,Yc;

for (i=0;i<5;i++){
if (Y1!=i)
if (grid[X1][i]==Item)
return false;

if (X1!=i)
if (grid[i][Y1]==Item)
return false;

if ((X1!=i) && (Y1!=i)&& (X1==Y1))
if (grid[i][i]==Item)
return false;

if ((X1+Y1)==4)
if (X1!=i && grid[i][4-i]==Item)
return false;
}

if (X1==2 && Y1==2)
return true;

if (X1==0 && Y1==4)
return true;

if (X1==3 && Y1==1)
X=1;

if (X1==1 && Y1==4){
X=0;
X1=1;
}

Xc=X1-X;
Yc=Y1-Y;

if (grid==0 || grid==0 || grid==0 || grid==0)
return false;

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

if (IsPrime(Sum)){
return true;
}
return false;

}

public boolean Distinct(){
int [] count=new int;
int i,j,item;

for (i=0;i<5;i++){
for (j=0;j<5;j++){
item=grid[i][j];
if (item>0)
{
if (item%2==0)
{
count[item]+=1;
}

if (count[item]>1)
return false;
}

}
}
return true;
}

public void Solve(int x,int y,int x1,int y1,int nxt){
int i;

if ((x1==-1) && (y1==-1)){

return;
}
for (i=0;i<10;i++){
grid[x1][y1]=i;
cellnumber=(5*x1)+y1;
value=i;
repaint();

try {
}
catch (InterruptedException e) { }

if (Valid(x,y,x1,y1,i,nxt))
{

/*g.drawString(str,0,140);*/
x=path[nxt];
y=path[nxt];
x1=path[nxt];
y1=path[nxt];

Solve(x,y,x1,y1,nxt+1);
x=path[nxt-1];
y=path[nxt-1];
x1=path[nxt-1];
y1=path[nxt-1];

}

grid[x1][y1]=-2;
}
}
}
```
• saracogluahmet 8 July 2013 at 2:01 pm

For the animation in the applet, I did use threads for paralell processing

6. geoffrounce 20 July 2017 at 7:27 pm

This enigma is different to Enigma 1740, in that it does not state that all primes are to be different.
In fact, prime number 31 appears twice and this time (!) I get the published single answer for this Enigma.

I had to use a new ‘ at_most’ predicate in MiniZinc to allow for the condition that no even digit appears more than once anywhere:
Usage:
% predicate at_most (int: n, array [int] of var int: x, int: v)
% Requires at most n variables in x to take the value v.

Even digits 0, 4, and 6 appear once and digits 2 and 8 are absent from the grid in the answer.

```% A Solution in MiniZinc
% In the grid below, ghi and jn needed as shaded numbers

% a X X X b
% c d X e f
% X g h i X
% j k X l m
% n X X X p

include "globals.mzn";

% parameter variables
int: a = 7;
int: g = 3;

% decision variables
var 1..9:b;  var 1..9:c;   var 0..9:d;   var 1..9:e;  var 0..9:f;
var 0..9:h;  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;

array[1..13] of var 0..9: nbr = [b,c,d,e,f,h,i,j,k,l,m,n,p];

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};

% All eleven two and three digit answers are prime
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;

% No digit appears more than once in any row, column or either of the two long diagonals
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]);

% No even digit (ie 0,2,4,6 or 8) appears more than once anywhere
% nbr = [b,c,d,e,f,h,i,j,k,l,m,n,p], so this array includes all variables used (but not a and g)

constraint at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 0)
/\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 2)
/\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 4)
/\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 6)
/\ at_most(1, [b,c,d,e,f,h,i,j,k,l,m,n,p], 8);

solve satisfy;

output[ "Shaded area values: " ++ show(jn) ++ " and " ++ show(ghi) ++ "\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 307

% Grid Output:
% 7XXX3
% 31X67
% X307X
% 47X31
% 1XXX9
%----------
% Finished in 58msec

```

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