Tout le monde connaît les casse-tête nommés Sudoku. Leur résolution automatique par ordinateur est très simple à mettre en place, et nous allons en présenter une méthode dans cet article.
Mise en place
Une grille de Sudoku sera représentée par une chaîne de caractères de la forme suivante :
>>> grille = """\
.1......6
....9..2.
.56.18.7.
89.2....7
.........
1....9.32
.8.34.76.
.4..8....
7......1."""
Cette forme est peu pratique pour l'ordinateur, et nous allons la transformer en une liste de listes grâce à la fonction suivante :
def prepare_grille(grille):
return [list(ligne) for ligne in grille.split()]
On obtient par exemple :
>>> prepare_grille(grille)
[['.', '1', '.', '.', '.', '.', '.', '.', '6'],
['.', '.', '.', '.', '9', '.', '.', '2', '.'],
['.', '5', '6', '.', '1', '8', '.', '7', '.'],
['8', '9', '.', '2', '.', '.', '.', '.', '7'],
['.', '.', '.', '.', '.', '.', '.', '.', '.'],
['1', '.', '.', '.', '.', '9', '.', '3', '2'],
['.', '8', '.', '3', '4', '.', '7', '6', '.'],
['.', '4', '.', '.', '8', '.', '.', '.', '.'],
['7', '.', '.', '.', '.', '.', '.', '1', '.']]
À l'inverse, on peut prévoir une fonction qui affichera de façon lisible une grille sous la forme précédente :
def affiche_grille(grille):
for l in range(9):
for c in range(9):
print(grille[l][c], end=" ")
if c == 2 or c == 5:
print(" ", end=" ")
if l == 2 or l == 5:
print("")
print("")
Ainsi, la grille précédente devient :
>>> affiche_grille(prepare_grille(grille))
. 1 . . . . . . 6
. . . . 9 . . 2 .
. 5 6 . 1 8 . 7 .
8 9 . 2 . . . . 7
. . . . . . . . .
1 . . . . 9 . 3 2
. 8 . 3 4 . 7 6 .
. 4 . . 8 . . . .
7 . . . . . . 1 .
Pour finir l'introduction, définissons la formule pour déterminer le numéro de bloc d'une case :
def bloc(ligne, colonne):
return (colonne // 3) + 3 * (ligne // 3)
On peut vérifier que cela est correct :
>>> affiche_grille([[bloc(l, c) for c in range(9)] for l in range(9)])
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
0 0 0 1 1 1 2 2 2
3 3 3 4 4 4 5 5 5
3 3 3 4 4 4 5 5 5
3 3 3 4 4 4 5 5 5
6 6 6 7 7 7 8 8 8
6 6 6 7 7 7 8 8 8
6 6 6 7 7 7 8 8 8
Une première méthode de résolution
Une méthode très simple pour résoudre un sudoku est la suivante : on regarde la première case non remplie, on essaye tous les chiffres de 1 à 9 et, à chaque fois que c'est possible, on mets le chiffre dans la case et on passe à la case vide suivante. Si on est coincé, on revient à la case à remplir précédente et on essaye le chiffre suivant. La grille est résolue dès qu'il n'y a plus de case vide.
Une première fonction
vérifie s'il est possible de mettrevaleur dans la case de grille désignée par ses numéros de ligne et de colonne. Pour cela, on teste toute les cases de la ligne, de la colonne et du bloc contenant la case. Dès que l'on rencontre une case contenant valeur, on s'arrête et on renvoie False. Sinon, si l'on arrive au bout des tests, on n'a pas rencontré valeur et on peut donc renvoyer True. Cela correspond à l'évaluation paresseuse d'une conjonction, l'adjectif paresseuse correspondant au fait que dès que l'on rencontre un False, on sait que le résultat final sera False donc on peut s'arrêter là sans évaluer le reste. On parle de lazy evaluation en anglais.def est_possible(grille, ligne, colonne, valeur):
# test de la ligne
for i in range(9):
if grille[ligne][i] == valeur:
return False
# test de la colonne
for i in range(9):
if grille[i][colonne] == valeur:
return False
# test du bloc
# la case en haut à gauche de bloc a pour coordonnées
# (3 * (ligne // 3), 3 * (colonne // 3))
for i in range(3 * (ligne // 3), 3 * (ligne // 3) + 3):
for j in range(3 * (colonne // 3), 3 * (colonne // 3) + 3):
if grille[i][j] == valeur:
return False
return True
Voici maintenant la fonction principale, qui va tester chaque case une par une (on les suppose numérotées de 0 à 80). À chaque fois, deux cas sont possibles :
- soit la case contient déjà un chiffre (c'est alors un chiffre de la grille initiale),
- soit elle contient un point.
Dans ce second cas, on essaye tous les chiffres possibles un par un et on continue en traitant la case suivante.
def essaye_case(grille, numero):
if numero == 81:
# on a pu remplir toutes les cases,
# on a gagné
return True
ligne = numero // 9
colonne = numero % 9
if grille[ligne][colonne] != ".":
# c'est une case déjà remplie
return essaye_case(grille, numero + 1)
# sinon, on essaye dans l'ordre toutes les valeurs possibles
for val in "123456789":
if est_possible(grille, ligne, colonne, val):
# si val peut être mis dans la case...
# ...on l'inscrit sur la grille...
grille[ligne][colonne] = val
# ...et on essaye la case suivante.
if essaye_case(grille, numero + 1):
# si on a trouvé une solution, on
# propage True en retour.
return True
# si on n'a pas trouvé de solution,
# on nettoie
grille[ligne][colonne] = "."
# et on revient en arrière.
return False
La résolution se fait alors très simplement, en commençant par la première case.
def resolution(grille):
return essaye_case(grille, 0)
Tout est en place, on peut tester nos fonctions et résoudre notre première grille de sudoku.
>>> g = prepare_grille(grille)
>>> affiche_grille(g)
. 1 . . . . . . 6
. . . . 9 . . 2 .
. 5 6 . 1 8 . 7 .
8 9 . 2 . . . . 7
. . . . . . . . .
1 . . . . 9 . 3 2
. 8 . 3 4 . 7 6 .
. 4 . . 8 . . . .
7 . . . . . . 1 .
>>> resolution(g)
True
>>> affiche_grille(g)
4 1 9 7 2 3 8 5 6
3 7 8 5 9 6 1 2 4
2 5 6 4 1 8 3 7 9
8 9 3 2 5 1 6 4 7
5 2 7 6 3 4 9 8 1
1 6 4 8 7 9 5 3 2
9 8 1 3 4 2 7 6 5
6 4 5 1 8 7 2 9 3
7 3 2 9 6 5 4 1 8
Améliorons cela
Dans le programme précédent, dans le corps de la fonction
, on parcourt à chaque fois l'intégralité des lignes, colonnes et blocs pour déterminer si une valeur donnée peut être inscrite dans une case donnée.Pour rendre cela plus efficace, on peut tenir à jour des ensembles, un par ligne, par colonne et par bloc, indiquant les valeurs autorisées dans l'ensemble de cases correspondant.
Nous allons définir donc trois listes d'ensembles :
lsets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
csets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
bsets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
qui, au départ, contiennent toutes les valeurs possibles (la grille est vide, tout est autorisé).
Lors de la préparation, nous allons parcourir la grille et, pour chaque case comportant un chiffre, ôter ce dernier des valeurs possibles pour les ligne, colonne et bloc correspondants.
# préparation
for l in range(9):
for c in range(9):
b = (c // 3) + 3 * (l // 3)
if grille[l][c] != ".":
lsets[l].remove(grille[l][c])
csets[c].remove(grille[l][c])
bsets[b].remove(grille[l][c])
else:
...
Pour les cases marquées d'un ".", autrement dit celles dont on doit déterminer la valeur, nous allons en faire une liste.
else:
cases.append((l, c, b))
Dans la phase de résolution, on travaillera donc sur la liste
plutôt que de chercher quelle est la case suivante. La fonctionessaye_case devient alors :def essaye_case(pos):
if pos == len(cases):
# on a rempli toutes les cases,
# on a gagné
return True
# sinon, il faut essayer de remplir la case courante
l, c, b = cases[pos]
lset = lsets[l]
cset = csets[c]
bset = bsets[b]
# lset & cset & bset est l'ensemble des valeurs possibles,
# celles que l'on doit tester
for v in lset & cset & bset:
# on marque dans les ensembles la valeur testée
lset.remove(v)
cset.remove(v)
bset.remove(v)
if essaye_case(pos + 1):
# on a trouvé une solution, on peut modifier
# la grille de départ
grille[l][c] = v
# puis propager le résultat
return True
# sinon, on enlève la valeur testée
lset.add(v)
cset.add(v)
bset.add(v)
return False
On obtient le programme suivant, où toutes les étapes précédentes ont été encapsulées dans une unique fonction :
def sudoku2(grille):
lsets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
csets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
bsets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
cases = []
def essaye_case(pos):
if pos == len(cases):
return True
l, c, b = cases[pos]
lset = lsets[l]
cset = csets[c]
bset = bsets[b]
for v in lset & cset & bset:
lset.remove(v)
cset.remove(v)
bset.remove(v)
if essaye_case(pos + 1):
grille[l][c] = v
return True
lset.add(v)
cset.add(v)
bset.add(v)
return False
# préparation
for l in range(9):
for c in range(9):
b = (c // 3) + 3 * (l // 3)
if grille[l][c] == ".":
cases.append((l, c, b))
else:
lsets[l].remove(grille[l][c])
csets[c].remove(grille[l][c])
bsets[b].remove(grille[l][c])
# résolution
return essaye_case(0)
Améliorons encore cela
Le programme précédent peut encore être amélioré. Pour l'instant, la liste cases est simplement parcourue de gauche à droite. Or, il peut être judicieux de réfléchir à la case suivante à traîter. En particulier, si un case ne peut, à un moment donné, recevoir qu'une seule valeur possible, autant mettre directement cette valeur.
On peut généraliser ce raisonnement en choisissant, à chaque fois, une case ayant le moins de valeurs possibles.
def selectionne_case(pos):
# on regarde la case actuelle
l, c, b = cases[pos]
lset = lsets[l]
cset = csets[c]
bset = bsets[b]
courant = pos
cardinal_courant = len(lset & cset & bset)
for i in range(pos + 1, len(cases)):
l, c, b = cases[pos]
lset = lsets[l]
cset = csets[c]
bset = bsets[b]
cardinal_i = len(lset & cset & bset)
if cardinal_i < cardinal_courant:
courant = i
cardinal_courant = cardinal_i
if courant != pos:
# on échange les cases
cases[courant], cases[pos] = cases[pos], cases[courant]
Il suffit alors d'appeler selectionne_case(pos) dans essaye_case pour s'assurer que l'on va utiliser une case avec un minimum de valeurs possibles.
def sudoku3(grille):
lsets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
csets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
bsets = [{"1", "2", "3", "4", "5", "6", "7", "8", "9"} for _ in range(9)]
cases = []
def selectionne_case(pos):
# on regarde la case actuelle
l, c, b = cases[pos]
courant = pos
cardinal_courant = len(lsets[l] & csets[c] & bsets[b])
for i in range(pos + 1, len(cases)):
l, c, b = cases[i]
cardinal_i = len(lsets[l] & csets[c] & bsets[b])
if cardinal_i < cardinal_courant:
courant = i
cardinal_courant = cardinal_i
if courant != pos:
# on échange les cases
cases[courant], cases[pos] = cases[pos], cases[courant]
def essaye_case(pos):
if pos == len(cases):
return True
selectionne_case(pos)
l, c, b = cases[pos]
lset = lsets[l]
cset = csets[c]
bset = bsets[b]
for v in lset & cset & bset:
lset.remove(v)
cset.remove(v)
bset.remove(v)
if essaye_case(pos + 1):
grille[l][c] = v
return True
lset.add(v)
cset.add(v)
bset.add(v)
return False
# préparation
for l in range(9):
for c in range(9):
b = (c // 3) + 3 * (l // 3)
if grille[l][c] == ".":
cases.append((l, c, b))
else:
lsets[l].remove(grille[l][c])
csets[c].remove(grille[l][c])
bsets[b].remove(grille[l][c])
# résolution
return essaye_case(0)
Voici le déroulement de la résolution, beaucoup moins linéaire et nettement plus efficace que la méthode naïve :
Pour finir, testons l'efficacité des différentes fonctions. Pour cela, utilisons le module timeit :
def essaye(solveur, grille):
return timeit.timeit("{0}(prepare_grille({1}))".format(solveur, grille),
"from __main__ import {0}, {1}, prepare_grille".format(solveur, grille),
number=1000)
Il est très facile de trouver des grilles de sudoku à résoudre sur internet. Avec une grille classée facile (et j'ai renommé en sudoku1 la première méthode utilisée), on obtient les temps suivants :
>>> essaye("sudoku1", "facile")
28.803839526954107
>>> essaye("sudoku2", "facile")
1.3932488220161758
>>> essaye("sudoku3", "facile")
0.6789553799899295
Avec une grille démoniaque, on a :
>>> essaye("sudoku1", "demon")
44.38040982896928
>>> essaye("sudoku2", "demon")
7.604977662966121
>>> essaye("sudoku3", "demon")
1.4741591259953566