On peut aussi faire résoudre un sudoku par un ordinateur. La méthode la plus simple consiste à essayer les chiffres un par un dans les cases vides, et à revenir d’un pas en arrière pour recommencer quand on est dans une impasse. On l’appelle le retour sur trace (backtracking).
L’idée du retour sur trace
- En partant du coin supérieur gauche, cherchez la première case vide.
- Essayez d’y mettre les chiffres de 1 à 9, dans l’ordre. Si le chiffre figure déjà dans la ligne, la colonne ou le bloc, passez au suivant.
- Si un chiffre convient, placez-le et passez à la case vide suivante.
- Si aucun chiffre ne convient dans une case, revenez à la case précédente et essayez le chiffre suivant.
- Quand il n’y a plus de case vide, la grille est terminée.
Un joueur évite de deviner au hasard, mais un ordinateur peut revenir en arrière tout de suite après une erreur. Même en essayant tout au hasard, il arrive très vite à la solution.
En Python
On représente la grille par une liste de 81 chiffres, de gauche à droite puis de haut en bas (0 pour une case vide). Pour la case numéro i, le quotient de i÷9 donne la ligne et le reste donne la colonne.
def can_place(grid, r, c, d):
# d peut être placé s’il n’est pas déjà dans la même ligne, colonne ou bloc
for k in range(9):
if grid[r * 9 + k] == d or grid[k * 9 + c] == d:
return False
br, bc = r // 3 * 3, c // 3 * 3
for rr in range(br, br + 3):
for cc in range(bc, bc + 3):
if grid[rr * 9 + cc] == d:
return False
return True
def solve(grid):
# Trouver une case vide et essayer 1 à 9 dans l’ordre. En cas d’impasse, revenir en arrière
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
if solve(grid):
return True
grid[i] = 0
return False
return True
puzzle = "3..5..182.....2.9.8.2.91.4...52.9..6724.1.8396..4.85...5.12.9.7.3.7.....267..4..8"
grid = [0 if ch == "." else int(ch) for ch in puzzle]
solve(grid)
for r in range(9):
print(" ".join(str(v) for v in grid[r * 9 : r * 9 + 9])) Quand on l’exécute, la solution s’affiche ainsi. La grille est une grille ★1 de l’app NumberPlace.
3 4 9 5 6 7 1 8 2
5 1 6 8 4 2 7 9 3
8 7 2 3 9 1 6 4 5
1 8 5 2 3 9 4 7 6
7 2 4 6 1 5 8 3 9
6 9 3 4 7 8 5 2 1
4 5 8 1 2 3 9 6 7
9 3 1 7 8 6 2 5 4
2 6 7 9 5 4 3 1 8 Compter le nombre de solutions
Quand on crée une grille, on veut vérifier qu’elle n’a qu’une seule solution (Pourquoi une grille n’a qu’une seule solution). Il suffit de modifier un peu le programme ci-dessus : au lieu de s’arrêter à la première solution, on continue et on les compte. Dès qu’on en trouve deux, on sait que la solution n’est pas unique, et on s’arrête là.
def count_solutions(grid, limit=2):
# S’arrêter dès que limit solutions sont trouvées (avec 2, on sait que la solution n’est pas unique)
for i in range(81):
if grid[i] == 0:
r, c = divmod(i, 9)
found = 0
for d in range(1, 10):
if can_place(grid, r, c, d):
grid[i] = d
found += count_solutions(grid, limit - found)
grid[i] = 0
if found >= limit:
break
return found
return 1
grid = [0 if ch == "." else int(ch) for ch in puzzle]
print(count_solutions(grid)) Pour la grille ★1 ci-dessus, le programme affiche 1 ; pour une grille qui a deux solutions, il affiche 2.
Pour aller plus vite
Au lieu d’essayer les cases de gauche à droite, si l’on commence par la case où il reste le moins de chiffres possibles, le programme devient beaucoup plus rapide. En remplissant d’abord les cases qui n’ont qu’un seul candidat, on n’a presque jamais besoin de revenir en arrière. L’app NumberPlace essaie les cases dans cet ordre quand elle vérifie le nombre de solutions.
Résoudre avec les mêmes techniques qu’un joueur
Le retour sur trace est rapide et sûr, mais il n’explique pas « pourquoi ce chiffre va là ». Pour Indice et pour évaluer la difficulté d’une grille, l’app NumberPlace utilise une autre méthode.
- Garder, pour chaque case vide, la liste des chiffres possibles (les candidats).
- Chercher une technique applicable, en commençant par les plus simples.
- Après chaque coup joué, repartir de la technique la plus simple.
Les 15 techniques sont classées de la plus simple à la plus difficile : « ce chiffre ne peut aller que dans cette case », « seul ce chiffre peut aller dans cette case », puis les candidats verrouillés, les paires, le X-Wing, le XY-Wing et le Swordfish (Comment résoudre un sudoku). La résolution suit le même ordre qu’un joueur ; on sait donc quelles techniques ont été nécessaires, ce qui permet de fixer les ★ et d’expliquer la raison dans Indice.
