Programme exclusif première version. Fonction gensudoku(). Cette fonction génère de manière aléatoire une grille de sudoku case par case (le temps est assez long) environ 5 min en cas de blocage il y a un retour en arrière voire même un TIME OUT qui se déclenche au bout de 60 s, cela est indiqué lors du déroulement du programme. A la fin la grille solution est indiquée (il faut remonter pour la voir) suivi de la grille à résoudre correspondante. Mettre la police python en grand dans paramètres pour plus de confort
from random import randint import time def valposs(mat,ii,jj): enspasposs = {0} for kk in range(9) : enspasposs.add(mat[ii][kk]) enspasposs.add(mat[kk][jj]) icoin, jcoin = 3 * (ii//3), 3 * (jj//3) for k in range(icoin, icoin + 3): for p in range (jcoin, jcoin + 3): enspasposs.add(mat[k][p]) return sorted({1,2,3,4,5,6,7,8,9} - enspasposs) def pastr(mat,valeur, ii, jj) : for kk in range(9) : if valeur == mat[ii][kk]%10 or valeur == mat[kk][jj]%10: return False icoin, jcoin = 3 * (ii//3), 3 * (jj//3) for k in range(icoin, icoin + 3): for p in range (jcoin, jcoin + 3): if valeur == mat[k][p] % 10: return False return True def arr (mat, nh) : a_rajouter = 0 for ir in range (9): for jr in range (9): if mat[ir][jr]//10 == nh: mat[ir][jr] = 0 a_rajouter += 1 return (a_rajouter) def ajout_nh(mat, tabh): # rajout d'un niveau d'hypothèse tabh.append([]) nbre_de_sol = 0 ih = 0 while ih < 9 : jh = 0 # recherche 1ère case vide qui sera remplie au prochain balayage while jh < 9 : if mat[ih][jh] == 0 : for k in range(1,10) : if pastr(mat, k, ih, jh) : nbre_de_sol += 1 ih , jh = 8 , 8 jh += 1 ih += 1 tabh[-1].append(nbre_de_sol) # nbre de valeurs possibles 1ère case vide tabh[-1].append(0) # 0 valeur du premier indice def cherche(mat, tabh): global acomp, debut, gene flagnh = False while acomp > 0 : if time.monotonic() - debut > 60 and gene : # 10:ordi et 60:calculette print ("######## TIMEOUT #########") return False trouve = True while trouve : trouve = False ; i = 0 while i < 9 : j = 0 while j < 9 : if mat[i][j] == 0 : tabsol = [] for k in range(1,10) : if pastr(mat,k, i, j) : tabsol.append(k + ((len(tabh)-1)*10)) if len(tabsol) == 1 : trouve = True ; flagnh = False mat[i][j] = tabsol[0] acomp -= 1 if len(tabsol)>1 and flagnh and len(tabh)>1 : trouve = True ; flagnh = False mat[i][j] = tabsol[tabh[-1][1]] acomp -= 1 if len(tabsol) == 0 and len(tabh)>1 : trouve = True ; flagnh = True acomp += arr(mat,len(tabh)-1) tabh[-1][1] += 1 while tabh[-1][1] >= tabh[-1][0] : del(tabh[-1]) if len(tabh) < 2 and gene : return False else : acomp += arr(mat,len(tabh)-1) tabh[-1][1] += 1 i , j = 8 , 8 j += 1 i += 1 if acomp > 0 : ajout_nh(mat, tabh) flagnh = True return True def recherche(matrice): global acomp, debut, gene debut = time.monotonic() gene = True mat = [] ; acomp = 0 for i in range(9): mat.append([]) for j in range(9): mat[i].append(matrice[i][j]) if mat[i][j] == 0 : acomp += 1 nbsolutions = 0 tabh = [] ; tabh.append([]) tabh[0].append(1) ; tabh[0].append(0) pasfini = True while pasfini : gene = True if cherche(mat, tabh) == False : return 0 nbsolutions += 1 if nbsolutions > 1 : return nbsolutions autre_solution = True while autre_solution and pasfini : if len(tabh) > 1 : if tabh[-1][1] + 1 < tabh[-1][0]: acomp += arr(mat,len(tabh)-1) tabh[-1][1] += 1 autre_solution = False else : acomp += arr(mat,len(tabh)-1) del(tabh[-1]) else : autre_solution = False pasfini = False return nbsolutions ###### PROGRAMME PRINCIPAL ##### def gensudoku(): global acomp, debut, gene matrice = [[0]*9, [0]*9, [0]*9, [0]*9, [0]*9, [0]*9, [0]*9, [0]*9, [0]*9] indtabvide=[] for i in range(81): indtabvide.append(i) # indtabvide initialise de 0 à 80 nb_cases_completees = 0 nbsolutionsretour = 2 while nbsolutionsretour != 1 : if nb_cases_completees > 6 : nbsolutionsretour = recherche(matrice) # Le coeur du programme if nbsolutionsretour > 1 : i = randint(0,len(indtabvide)-1) indv = indtabvide[i] del indtabvide[i] ilig = indv // 9 icol = indv - (ilig * 9) lvp = valposs(matrice,ilig,icol) # lvp : table des valeurs possibles iii = randint(0,len(lvp)-1) matrice[ilig][icol] = lvp[iii] nb_cases_completees += 1 print ("Nbre de cases remplies =",nb_cases_completees) elif nbsolutionsretour == 0 : print ("Retour en arrière") matrice[ilig][icol] = 0 nb_cases_completees -= 1 indtabvide.append(indv) # Fini : la variable matrice contient la grille proposée ############ SOLUTION DE LA GRILLE PROPOSEE ############ mat = [] ; acomp = 0 # Copie "profonde" de matrice dans mat for i in range(9): mat.append([]) for j in range(9): mat[i].append(matrice[i][j]) if mat[i][j] == 0 : acomp += 1 tabh = [] ; tabh.append([]) tabh[0].append(1) ; tabh[0].append(0) gene = False # pour s'affranchir du timing nécessaire lors de la génération if cherche(mat, tabh) == False : # résolution de la grille print("PB dans la résolution") # ne doit pas arriver #### MISE EN FORME ET AFFICHAGE DE LA GRILLE RESOLUE for ir in range (9) : for jr in range (9) : mat[ir][jr] %= 10 print("\nSolution") for k in range(9) : # affichage print (mat[k]) #### AFFICHAGE DE LA GRILLE PROPOSEE A RESOUDRE print("\nGrille proposée avec") print(81-nb_cases_completees, "cases à remplir") for k in range(9): print (matrice[k])