Résout un sudoku.
cp renvoie tous les chiffres possibles dans une case s’il y en a case est la position de la case testée dans le sudoku [ligne, colonne].
ec signale si un sous-ensemble de la grille du sudoku contient un chiffre plus d’une fois auquel cas la grille contient une contradiction.
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 # Remplissage de la grille et tests de format P=print af(f) input("Resoudre ?") s=[] t=[] for nl,l in enumerate(f): try: n=list(map(int,l)) except: P("La ligne "+str(nl+1)+" contient autre chose qu'un chiffre.") return if len(n)!=9: P("La ligne "+str(nl+1)+" ne contient pas 9 chiffres.") return t+=[[nl,i] for i in range(9) if n[i]==0] s.append(n) if nl!=8: P("Le jeu contient "+str(nl+1)+" lignes au lieu de 9.") return # Tests de validite for l in range(9): if ec(s[l]): P("La ligne "+str(l+1)+" est contradictoire.") return for c in range(9): k=[s[l][c] for l in range(9)] if ec(k): P("La colonne "+str(c+1)+" est contradictoire.") 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("La cellule ("+str(l+1)+";"+str(c+1)+") est contradictoire.") return # Resolution 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("Le sudoku n'a pas de solution.") return s[t[cr][0]][t[cr][1]]=p[cr].pop() cr+=1 # Presentation de la grille resolue af(s)