Sunday Times Teaser 2655 – Sudoprime

1. 
   brian gladman permalink

   This solution uses my prime class which is available here.

   Python

   from collections import defaultdict from primes import Primes # list the indexes of the digits in each answer nbr_ix = ( (0, 2), (1, 5), (2, 3), (4, 5), (9, 10), (11, 12), (9, 13), (12, 14), (3, 6, 10), (4, 8, 11), (6, 7, 8) ) # list the indexes of the digits in the rows, columns and diagonals rcd_ix = ( (0, 1), (2, 3, 4, 5), (6, 7, 8), (9, 10, 11, 12), (13, 14), (0, 2, 9, 13), (3, 6, 10), (7,), (4, 8, 11), (1, 5, 12, 14), (0, 3, 7, 11, 14), (1, 4, 7, 10, 13) ) # list one, two and three digit primes with no duplicate digits prms = defaultdict(set) for p in Primes(1000): sp = str(p) if len(sp) == len(set(sp)): prms[len(sp)].add(sp) # check that rows, columns and diagonals have no repeated digits def check_rcd(dgts): for ix in rcd_ix: # compile row, column or diagonal as a string x = ''.join(dgts[i] for i in ix if dgts[i] != '*') # and test for repeated digits if len(x) != len(set(x)): return False return True # check that all completed answers are prime def check_prm(dgts): seen = set() for ix in nbr_ix: # compile each answer ans = ''.join(dgts[i] for i in ix) # if it is complete if '*' not in ans: # if not a suitable prime or one already seen if ans not in prms[len(ans)] or ans in seen: return False seen.add(ans) return True # a recursive function to place each answer in turn def place(dgts): pr = (''.join(dgts[i] for i in ix) for ix in nbr_ix) # if all digits have been allocated if '*' not in dgts: # list the answers pr = sorted(int(x) for x in pr) # and print the two largest ones and the list of digits print(pr[-2], pr[-1], ''.join(dgts)) else: # count the number of missing digits in each answer cnt = [x.count('*') for x in pr] # find a partial answer with the fewest missing digits n = cnt.index(min(x for x in cnt if x)) # and search for primes that can match this answer nbr = ''.join(dgts[i] for i in nbr_ix[n]) # look for primes of the same length as this partial answer for pr in prms[len(nbr)]: # check whether any digits in this partial answer match # the digits at the same positions in this prime if all(x in ('*', y) for x, y in zip(nbr, pr)): # if so, insert these digits into a copy of the digit list new = dgts[:] for i, p in zip(nbr_ix[n], pr): new[i] = p # now check that rows, columns and diagonals have no duplicated # digits and that any completed answers are different primes if check_rcd(new) and check_prm(new): place(new) # start with the 15 digits, of which two are known dgts = ['*'] * 15 dgts[6], dgts[13] = '8', '7' place(dgts)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

   from collections import defaultdict from primes import Primes   # list the indexes of the digits in each answer nbr_ix = ( (0, 2), (1, 5), (2, 3), (4, 5), (9, 10), (11, 12),            (9, 13), (12, 14), (3, 6, 10), (4, 8, 11), (6, 7, 8) )   # list the indexes of the digits in the rows, columns and diagonals rcd_ix = ( (0, 1), (2, 3, 4, 5), (6, 7, 8), (9, 10, 11, 12), (13, 14),            (0, 2, 9, 13), (3, 6, 10), (7,), (4, 8, 11), (1, 5, 12, 14),            (0, 3, 7, 11, 14), (1, 4, 7, 10, 13) )   # list one, two and three digit primes with no duplicate digits prms = defaultdict(set) for p in Primes(1000):   sp = str(p)   if len(sp) == len(set(sp)):     prms[len(sp)].add(sp)   # check that rows, columns and diagonals have no repeated digits def check_rcd(dgts):   for ix in rcd_ix:     # compile row, column or diagonal as a string     x = ''.join(dgts[i] for i in ix if dgts[i] != '*')     # and test for repeated digits     if len(x) != len(set(x)):       return False   return True   # check that all completed answers are prime def check_prm(dgts):   seen = set()   for ix in nbr_ix:     # compile each answer     ans = ''.join(dgts[i] for i in ix)     # if it is complete     if '*' not in ans:       # if not a suitable prime or one already seen       if ans not in prms[len(ans)] or ans in seen:         return False       seen.add(ans)   return True   # a recursive function to place each answer in turn def place(dgts):   pr = (''.join(dgts[i] for i in ix) for ix in nbr_ix)   # if all digits have been allocated   if '*' not in dgts:     # list the answers     pr = sorted(int(x) for x in pr)     # and print the two largest ones and the list of digits     print(pr[-2], pr[-1], ''.join(dgts))   else:     # count the number of missing digits in each answer     cnt = [x.count('*') for x in pr]     # find a partial answer with the fewest missing digits     n = cnt.index(min(x for x in cnt if x))     # and search for primes that can match this answer     nbr = ''.join(dgts[i] for i in nbr_ix[n])     # look for primes of the same length as this partial answer     for pr in prms[len(nbr)]:       # check whether any digits in this partial answer match       # the digits at the same positions in this prime       if all(x in ('*', y) for x, y in zip(nbr, pr)):         # if so, insert these digits into a copy of the digit list         new = dgts[:]         for i, p in zip(nbr_ix[n], pr):           new[i] = p         # now check that rows, columns and diagonals have no duplicated         # digits and that any completed answers are different primes         if check_rcd(new) and check_prm(new):           place(new)   # start with the 15 digits, of which two are known dgts = ['*'] * 15 dgts[6], dgts[13] = '8', '7' place(dgts)

Comments are closed.