Discussion :

[aabdoulay]

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

[wiztricks]

Salut,

j'essaie de coder un programme permettant de générer une grille de sudoku avec une UNIQUE solution.

Pour faire cela, il faut un algorithme... Et la rubrique algorithme est là pour vous en suggérer un.

- W

[aabdoulay]

dois je reposter dans l'autre section?
j'ai déjà parcouru les posts, mais je ne comprends pas la méthode de création liée au backtracking
edit: en fait, ce que je ne comprends pas, c'est la méthode pour compter le nombre de solution d'un sudoku. Je ne vois pas comment modifier le programme backtracking en ajoutant un compteur, puisqu'il s'arrete quand il trouve une solution.

[wiztricks]

edit: en fait, ce que je ne comprends pas, c'est la méthode pour compter le nombre de solution d'un sudoku. Je ne vois pas comment modifier le programme backtracking en ajoutant un compteur, puisqu'il s'arrete quand il trouve une solution.

On dirait que vous avez du code qui implémente un algo. (que vous avez récupéré on ne sait où) que vous voudriez le modifier pour qu'il retourne un nombre de solutions plutôt que la première solution trouvée...
Comme on ne sait pas comment a été construit l'algo. pas évident qu'il sache énumérer toutes les solutions possibles... En tout cas c'est pas en lisant le code qu'on peut le savoir.

- W