from copy import deepcopy
G = [ [ 4, 7, 0, 0, 0, 3, 0, 0, 0],
[ 0, 0, 5, 0, 2, 6, 1, 4, 0],
[ 0, 1, 2, 7, 5, 0, 0, 8, 0],
[ 0, 0, 4, 8, 0, 0, 2, 0, 0],
[ 5, 8, 0, 2, 0, 1, 0, 9, 4],
[ 0, 0, 3, 0, 0, 5, 8, 0, 0],
[ 0, 5, 0, 0, 1, 2, 9, 3, 0],
[ 0, 9, 8, 5, 6, 0, 4, 0, 0],
[ 0, 0, 0, 3, 0, 0, 0, 6, 5] ]
def affiche_grille(G) :
for i in range(9) :
for j in range(9) :
print(G[i][j], end=' ')
print()
def ligneAllDiff(grille, i) :
""" vérifie que les valeurs non nulles d'une ligne
de la grille sont toutes distinctes."""
for j in range(9) :
if grille[i][j] == 0 : continue
if grille[i][j] in grille[i][j+1:] : return False
return True
def colonneAllDiff(grille, j) :
""" vérifie que les valeurs non nulles d'une colonne
de la grille sont toutes distinctes."""
for i in range(9) :
if grille[i][j] == 0 : pass
elif grille[i][j] in [ grille[k][j] for k in range(i+1,9) ] : return False
return True
def carreAllDiff(grille, c) :
""" vérifie que les valeurs non nulles du carré (numéroté c)
de la grille sont toutes distinctes."""
carre = []
for i in range(9):
for j in range(9) :
if 3*(i//3)+(j//3) == c : carre.append(grille[i][j])
for i in range(9) :
if carre[i] == 0 : continue
if carre[i] in carre[i+1:] : return False
return True
def grilleAcceptable(grille) :
"""retourne True si la grille, partiellement remplie, respecte les règles du sudoku."""
for i in range(9):
if not(ligneAllDiff(grille, i)) : return False
for i in range(9):
if not(colonneAllDiff(grille, i)) : return False
for i in range(9):
if not(carreAllDiff(grille, i)) : return False
return True
def grilleOk(grille) :
""" retourne True si la grille est remplie et
satisfait les règles du sudoku."""
for i in range(9) :
for j in range(9) :
if grille[i][j] == 0 : return False
return grilleAcceptable(grille)
def remplit(grille, ligne=0, colonne=0) :
# on commence par copier la grille
# sinon on modifierait l'objet grille (passage par référence)
GG = deepcopy(grille)
if ligne > 8 :
if grilleOk(GG) : affiche_grille(GG)
else :
if grille[ligne][colonne] != 0 : remplit(GG, ligne + (colonne == 8), (colonne+1)%9 )
else :
for k in (1,2,3,4,5,6,7,8,9) :
GG[ligne][colonne] = k
if grilleAcceptable(GG) : remplit(GG, ligne + (colonne == 8), (colonne+1)%9 )
remplit(G)
On obtient :
4 7 9 1 8 3 5 2 6
8 3 5 9 2 6 1 4 7
6 1 2 7 5 4 3 8 9
1 6 4 8 7 9 2 5 3
5 8 7 2 3 1 6 9 4
9 2 3 6 4 5 8 7 1
7 5 6 4 1 2 9 3 8
3 9 8 5 6 7 4 1 2
2 4 1 3 9 8 7 6 5
On pourra se convaincre, par exemple avec la grille ci-dessous, que la résolution n'est pas toujours
très rapide et qu'une optimisation est à envisager.
G3 = [ [0,0,0,0,0,0,0,0,0],
[0,0,9,6,2,1,5,0,0],
[8,0,0,0,0,0,0,0,9],
[0,4,0,0,0,0,0,6,0],
[0,0,7,8,0,6,9,0,0],
[0,2,0,0,0,0,0,7,0],
[2,0,0,0,0,0,0,0,4],
[0,0,6,5,7,9,3,0,0],
[0,0,0,0,0,0,0,0,0]
]
Le sujet de CAPES de mathématiques 2017, premier à être concerné par une épreuve option informatique, a proposé
un sujet sur ce thème.
Le pdf du sujet.
Des réponses pour la partie code.
Ci-dessous un condensé du solveur obtenu en question C13 de ce sujet.
La différence essentielle entre ce solveur et celui proposé dans l'onglet "un code" est qu'on ne fait pas de copie de la grille
lors des appels récursifs. La conséquence est qu'il faut gérer les remontées (c'est à dire faire
en sorte que la grille retrouve son état du niveau de profondeur p lorsqu'on remonte du
niveau p+1 au niveau p), ce qui explique l'instruction L[i][j] = VIDE
placé en fin de la fonction backtracking.
G3 = [ [0,0,0,0,0,0,0,0,0],
[0,0,9,6,2,1,5,0,0],
[8,0,0,0,0,0,0,0,9],
[0,4,0,0,0,0,0,6,0],
[0,0,7,8,0,6,9,0,0],
[0,2,0,0,0,0,0,7,0],
[2,0,0,0,0,0,0,0,4],
[0,0,6,5,7,9,3,0,0],
[0,0,0,0,0,0,0,0,0]
]
# la liste des valeurs utilisées pour remplir la grille
VALEURS = (1,2,3,4,5,6,7,8,9)
# valeur pour une case vide :
VIDE = 0
def affiche_grille(L) :
"""
Pour afficher les grilles de sudoku à peu près proprement.
"""
for i in range(9) :
for j in range(9) :
print(L[i][j], end=' ')
print()
def chiffres_possibles(L,i,j) :
"""
retourne la liste des valeurs qui ne sont pas déjà présentes
dans la ligne, le carré ou la colonne de la case (i,j)
"""
# valeurs dans la ligne i :
ligne = [ L[i][col] for col in range(9) if L[i][col] != VIDE and col != j]
# valeurs dans la colonne j :
colonne = [ L[lig][j] for lig in range(9) if L[lig][j] != VIDE and lig != i]
# valeurs dans le carré de (i,j)
k = 3*(i//3)+(j//3) # numéro du carré
carre = [ L[lig][col] for lig in range(9) for col in range(9) if 3*(lig//3)+(col//3) == k and L[lig][col] != VIDE and (lig, col) != (i,j) ]
# cumul
cumul = ligne + colonne + carre
return [ v for v in VALEURS if v not in cumul ]
def case_suivante(pos) :
"""
Question C12
"""
if pos[1] == 8 :
if pos[0] < 8 : return [pos[0] + 1, 0]
else : return [9,0]
else : return [pos[0], pos[1]+1]
def backtracking(L,pos) :
"""
Question C13
"""
if pos == [9,0] : return True
i,j = pos[0], pos[1]
if L[i][j] != VIDE : return backtracking(L,case_suivante(pos))
for k in VALEURS :
L[i][j] = k
if k in chiffres_possibles(L,i,j) and backtracking(L,case_suivante(pos)) :
return True
L[i][j] = VIDE
return False
def solution_sudoku(L) :
return backtracking(L,[0,0])
if __name__ == "__main__" :
solution_sudoku(G3)
affiche_grille(G3)
print()
La grille G3 choisie dans le code précédent est choisie pour montrer que le temps de calcul
peut être long.
On peut améliorer le temps de calcul en modifiant la fonction case_suivante
(c'est la question C16 du sujet). Comparez la vitesse du solveur dans le cas de notre grille G3 avec la version
suivante, dans laquelle seule la fonction case_suivante a été modifiée : on choisit à chaque étape une case
ayant un nombre minimal de possibilités (explication : pour une case n'ayant par exemple qu'un seul choix initial, la valeur
posée est correcte dès le départ et on n'aura donc jamais à remonter jusqu'au niveau de ce choix. On sent qu'en faisant
ce choix, on limitera les remontées).
"""
Sujet capes 2017
"""
G3 = [ [0,0,0,0,0,0,0,0,0],
[0,0,9,6,2,1,5,0,0],
[8,0,0,0,0,0,0,0,9],
[0,4,0,0,0,0,0,6,0],
[0,0,7,8,0,6,9,0,0],
[0,2,0,0,0,0,0,7,0],
[2,0,0,0,0,0,0,0,4],
[0,0,6,5,7,9,3,0,0],
[0,0,0,0,0,0,0,0,0]
]
# la liste des valeurs utilisées pour remplir la grille
VALEURS = (1,2,3,4,5,6,7,8,9)
# valeur pour une case vide :
VIDE = 0
def affiche_grille(L) :
"""
Pour afficher les grilles de sudoku à peu près proprement.
"""
for i in range(9) :
for j in range(9) :
print(L[i][j], end=' ')
print()
def chiffres_possibles(L,i,j) :
"""
retourne la liste des valeurs qui ne sont pas déjà présentes
dans la ligne, le carré ou la colonne de la case (i,j)
"""
# valeurs dans la ligne i :
ligne = [ L[i][col] for col in range(9) if L[i][col] != VIDE and col != j]
# valeurs dans la colonne j :
colonne = [ L[lig][j] for lig in range(9) if L[lig][j] != VIDE and lig != i]
# valeurs dans le carré de (i,j)
k = 3*(i//3)+(j//3) # numéro du carré
carre = [ L[lig][col] for lig in range(9) for col in range(9) if 3*(lig//3)+(col//3) == k and L[lig][col] != VIDE and (lig, col) != (i,j) ]
# cumul
cumul = ligne + colonne + carre
return [ v for v in VALEURS if v not in cumul ]
def nombre_de_possibles(L,i,j) :
if L[i][j] != VIDE : return 0
else : return len(chiffres_possibles(L,i,j))
def case_suivante(L, pos) :
"""
Question C16
"""
grille_complete = True
# min des nombres de possibilités pour une case :
minimum_des_vides = 10
for (i,j) in [(lig,col) for lig in range(9) for col in range(9) if L[lig][col] == VIDE] :
grille_complete = False
possible = nombre_de_possibles(L,i,j)
if possible < minimum_des_vides :
lig, col = i, j
minimum_des_vides = possible
if grille_complete : return [9,0]
else : return [lig, col]
def backtracking(L,pos) :
"""
Question C13
"""
if pos == [9,0] : return True
i,j = pos[0], pos[1]
if L[i][j] != VIDE : return backtracking(L, case_suivante(L,pos))
for k in VALEURS :
L[i][j] = k
if k in chiffres_possibles(L,i,j) and backtracking(L,case_suivante(L,pos)) :
return True
L[i][j] = VIDE
return False
def solution_sudoku(L) :
return backtracking( L, case_suivante( L, [0,0] ) )
if __name__ == "__main__" :
solution_sudoku(G3)
affiche_grille(G3)
print()