Enigmatic Code
Programming Enigma Puzzles
Enigma 1755: Sudoprime II
Posted by on 26 June 2013
From New Scientist #2923, 29th June 2013 [link] [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]
Enigmatic Code 
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 ps[len(s)].add(s) # 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.
Isn’t zero an even digit?
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.
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")#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[0][0],grid[2][1]=7,3#given the constraints in the puzzle #start= [0][0] # 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 #The numbers must not start with "0" if grid[0][4]==0 or grid[1][3]==0 or grid[3][0]==0 or grid[3][3]==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=[0]*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][0],path[nxt][1],path[nxt][2],path[nxt][3] #print("next",nxt,i) Solve(x,y,x1,y1,nxt+1) #Backtracking occurs below... 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 Solve(0,0,1,0,1)The execution time of the algorithm above on my machine is about 15 miliseconds, I guess that is really fast..
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[6], g[7], g[8], g[9], g[13])) print('{:2d} # # #{:2d}'.format(g[0], g[1])) print('{:2d}{:2d} #{:2d}{:2d}'.format(g[2], g[3], g[4], g[5])) print(' #{:2d}{:2d}{:2d} #'.format(g[6], g[7], g[8])) print('{:2d}{:2d} #{:2d}{:2d}'.format(g[9], g[10], g[11], g[12])) print('{:2d} # # #{:2d}'.format(g[13], g[14])) # set an empty grid g = [None] * 15 # and add 7 and 3 to it g[0], g[6] = 7, 3 # now solve for other digit positions solve(g, dmap)Hi Brian, what is the execution time of it?
If I replace lines 1 to 7 with
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.
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
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.
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 🙂
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?
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
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.
Hi Jim, which one do you mean, mine or Brian s?
@Ahmet: I’m referring to the code you posted above (28 June 2013 at 1:19 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
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.
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
You can view my output with the execution time above the link.
Erm, if those numbers are measuring seconds then the three examples you post are:
0.172s = 172ms, 0.156s = 156ms and 0.156s = 156ms.
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?
That would come out as 97ms on my machine.
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
timeitmodule for doing more detailed calculation of the runtimes of code fragments, but I like using the shell’stimecommand as it gives me a reasonable basis for comparison between programs written in different languages. (I used to do Enigma problems in Perl).#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[0][0],grid[2][1]=7,3#given the constraints in the puzzle #start= [0][0] # 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][0],path[nxt][1],path[nxt][2],path[nxt][3] #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][0],path[nxt-1][1],path[nxt-1][2],path[nxt-1][3] 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…
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; /* @author asks */ public class LineApplet extends Applet implements Runnable { Thread t=new Thread(this); // This is the thread! public TextField [] f=new TextField[25]; int K=-1; int [][] grid=new int[5][]; 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(); add(f[i]); } for (i=0;i<5;i++){ grid[i]=new int[5]; for (j=0;j<5;j++){ grid[i][j]=-2; } } grid[0][0]=7; grid[2][1]=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[0].setText(Integer.toString(7)); f[11].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[1].setBackground(Color.black); f[2].setBackground(Color.black); f[3].setBackground(Color.black); f[7].setBackground(Color.black); f[10].setBackground(Color.black); f[14].setBackground(Color.black); f[17].setBackground(Color.black); f[21].setBackground(Color.black); f[22].setBackground(Color.black); f[23].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][4]==0 || grid[1][3]==0 || grid[3][0]==0 || grid[3][3]==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[10]; 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 { Thread.sleep(100); } catch (InterruptedException e) { } if (Valid(x,y,x1,y1,i,nxt)) { /*g.drawString(str,0,140);*/ x=path[nxt][0]; y=path[nxt][1]; x1=path[nxt][2]; y1=path[nxt][3]; Solve(x,y,x1,y1,nxt+1); x=path[nxt-1][0]; y=path[nxt-1][1]; x1=path[nxt-1][2]; y1=path[nxt-1][3]; } grid[x1][y1]=-2; } } }For the animation in the applet, I did use threads for paralell processing
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