Resolver um sudoku.
cp devolve todos os números possíveis num quadrado, se houver algum quadrado na posição do quadrado testado no sudoku [linha, coluna].
ec indica se um subconjunto da grelha de sudoku contém um número mais do que uma vez, caso em que a grelha contém uma contradição.
Esta é uma tradução do script de Nicolas Patrois.
def sudoku(): def af(g): for n,l in enumerate(g): for m,c in enumerate(l): P(str(c).replace("0"," "),end="") if m in {2,5}: P("+",end="") P() if n in {2,5}: P("+"*11) f=[ "004903008", "003050002", "978200000", "269030000", "000060000", "000090615", "000005489", "700080100", "400109500"] def cp(q,s): l=set(s[q[0]]) l|={s[i][q[1]] for i in range(9)} k=q[0]//3,q[1]//3 for i in range(3): l|=set(s[k[0]*3+i][k[1]*3:(k[1]+1)*3]) return set(range(1,10))-l def ec(l): q=set(l)-{0} for c in q: if l.count(c)!=1: return True return False # Preenchimento da grelha e testes de formato P=print af(f) input("Resolver ?") s=[] t=[] for nl,l in enumerate(f): try: n=list(map(int,l)) except: P("A linha "+str(nl+1)+" contém algo mais do que um algarismo.") return if len(n)!=9: P("A linha "+str(nl+1)+" não contém 9 algarismos.") return t+=[[nl,i] for i in range(9) if n[i]==0] s.append(n) if nl!=8: P("O jogo contém "+str(nl+1)+" linhas em vez de 9.") return # Testes de validade for l in range(9): if ec(s[l]): P("A linha "+str(l+1)+" é contraditória.") return for c in range(9): k=[s[l][c] for l in range(9)] if ec(k): P("A coluna "+str(c+1)+" é contraditória.") return for l in range(3): for c in range(3): q=[] for i in range(3): q+=s[l*3+i][c*3:(c+1)*3] if ec(q): P("A célula ("+str(l+1)+";"+str(c+1)+") é contraditória.") return # Resolução p=[[] for i in t] cr=0 while cr<len(t): p[cr]=cp(t[cr],s) try: while not p[cr]: s[t[cr][0]][t[cr][1]]=0 cr-=1 except: P("O sudoku não tem solução.") return s[t[cr][0]][t[cr][1]]=p[cr].pop() cr+=1 # Apresentação da grelha resolvida af(s)