Bonjour à tous, j'essaie de coder un programme permettant de générer une grille de sudoku avec une UNIQUE solution. J'ai fais des recherches sur le forum mais je ne trouve pas de solution satisfaisante. J'ai codé un algorithme de résolution par backtracking mais je ne comprends pas comment l'utiliser pour générer la grille avec solution unique, comme il est dit sur internet.
En effet j'ai réussi à faire ceci :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
def creation(nbrdechiffre): #probleme solution non unique
    i,j=0,0
    gr=creerGrille(9,9)
    L=[]
    k=0
    K=[]
    for z in range (7):
        K.append(random.randint(1,9))
        print(K)
    while len (L) != nbrdechiffre:
        i=random.randint(0,8)
        j=random.randint(0,8)
 
        if [i,j] not in L:
 
            L.append([i,j]) #liste des indices
 
        for k in range (len(L)):
            d=L[k][0]
            b=L[k][1]
            y=random.randint(0,6)
            t=K[y]
            gr[d][b]= t
 
            while nbroccurences(gr,gr[d][b],d,b)!= 0:  #nombre d’occurrence est une fonction qui compte l'occurrence d'un chiffre dans la ligne colonne, sous grille
                gr[d][b]=random.randint(1,9)
    print (resolution(gr))
    while resolution(gr) == False:
        print(gr)
        gr=creation(nbrdechiffre)
 
 
    return gr
voici mon algo de résolution
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
def absent_de_la_ligne( k , grille, i): #valeur à vérifier, grille , numéro de ligne
    for j in range(0,9):
        if grille[i][j] == k :
            return False
    return True
 
 
def absent_de_la_colonne( k , grille , j): #valeur à vérifier, grille , numéro de colonne
    for i in range(0,9):
        if grille[i][j] == k :
            return False
    return True
 
def absent_du_bloc ( k , grille , i , j): #valeur à vérifier, grille , numéro de colonne, ligne
    ibis = i - (i%3)
    jbis = j - (j%3)
    for u in range(ibis,ibis+3):
        for v in range(jbis,jbis+3):
            if grille[u][v] == k :
                return False
    return True
 
def backtracking ( grille , position ):
    if (position == 81): #critère d'arret
        return True
    i = position//9 #à expliquer diapo
    j = position%9
    if grille[i][j] != 0 :
        return backtracking( grille , position +1)
    for k in range (1,10):
        if (absent_de_la_ligne( k , grille, i) and absent_de_la_colonne( k , grille , j) and absent_du_bloc ( k , grille , i , j)):
            grille[i][j] = k
            if (backtracking ( grille , position+1)):
                return True
    grille[i][j] = 0  # cas non solvable
    return False			
 
def solution ( grille ):
    sol=creerGrille(9,9)
    for i in range (9):
        for j in range(9):
            sol[i][j]=grille[i][j]
    positions=0
    res = backtracking(sol,positions)
    return res,sol