Sudoku Solver
Une grille de sudoku est une grille de 9 × 9 divisée en neuf carrés de 3 × 3. Dans une grille résolue, chaque ligne, chaque colonne et chaque carré contient chaque chiffre de 1 à 9 une seule fois.
Le puzzle est fourni sous la forme de 9 chaînes de caractères, une par ligne en partant du haut ; un . représente une case vide. Remplis toutes les cases vides et renvoie la grille résolue sous la même forme. La grille admet exactement une solution.
Fonction
- boardstring-array
- les 9 lignes du puzzle, un point dans chaque case vide
- Renvoiestring-array
- les 9 lignes du plateau résolu
Contraintes
boardcontient 9 chaînes de 9 caractères.- Chaque caractère est
.ou l’un des chiffres1à9. - Les chiffres donnés ne se répètent jamais dans une ligne, une colonne ou un bloc.
- Le plateau a exactement une solution.
Exemples
- Entrée
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Sortie
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Explication
- La ligne du haut
9.7.....6contient déjà 9, 7 et 6, donc ses six cases vides accueillent 1, 2, 3, 4, 5 et 8. Les colonnes et les blocs déterminent où placer chacun, et la ligne devient957214386.
Pour aller plus loin
Dans un sudoku killer, les cages de cases doivent également totaliser les sommes indiquées. Comment ajouteriez-vous cette règle à la recherche et l'utiliseriez-vous pour élaguer les branches plus tôt ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Note quels chiffres figurent déjà dans chaque ligne, chaque colonne et chaque carré de 3 × 3. Tu peux alors déterminer en O(1) si un chiffre peut être placé dans une case vide.
Remplissez les cases vides une par une. Essayez chaque chiffre qui peut aller dans la case, passez à la case suivante et annulez le chiffre si le reste de la grille ne peut pas être complété avec celui-ci.
L’ordre des cellules compte. Remplissez ensuite la cellule vide qui a le moins de chiffres possibles : une cellule avec une seule possibilité ne nécessite aucun embranchement, et une cellule sans possibilité vous indique immédiatement qu’il faut revenir en arrière.
Solution
Résous-le par retour arrière : place un chiffre qui convient, continue, puis annule ce choix lorsque la grille ne peut pas être complétée. L’ordre des cases détermine la vitesse. Sur une grille difficile, l’ordre de lecture peut parcourir des centaines de millions de grilles partielles ; remplir d’abord la case qui a le moins de possibilités en prend environ une centaine.
Retour arrière dans l’ordre de lecture
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Remplis les cases vides dans l’ordre de lecture, chacune avec le plus petit chiffre qui convient. Lorsqu’il ne reste plus aucun chiffre possible pour une case, reviens à la case précédente et essaie le suivant. Toutes les combinaisons qui respectent les règles sont essayées à tour de rôle, de sorte que la recherche trouve la solution.
Trois tableaux rendent chaque vérification d’ajustement O(1) : rowUsed[r][d], colUsed[c][d] et boxUsed[b][d], avec la boîte b = (r / 3) * 3 + c / 3. Placer un chiffre définit trois entrées et le retirer les efface.
L’ordre fixe est le point faible : la recherche peut remplir toute une ligne avec des chiffres qui conviennent localement et découvrir plus tard que de nombreuses cases ne laissent aucune possibilité. Une grille dont les premières lignes contiennent presque aucun indice, et dont les réponses sont des chiffres élevés, lui fait parcourir plus de 300 millions de grilles partielles.
Algorithme
- Lisez le plateau dans une grille avec 0 pour les cellules vides, remplissez
rowUsed,colUsedetboxUsed, et répertoriez les cellules vides dans l’ordre de lecture. backtrack(k): sikest égal au nombre de cellules vides, renvoyez true.- Pour chaque chiffre
dde 1 à 9 qui n’est pas utilisé dans la ligne, la colonne et la boîte de la cellulek, placez-le, marquez-le et renvoyez true sibacktrack(k+1)le fait ; sinon, annulez le marquage. - Si aucun chiffre ne convient, effacez la cellule et renvoyez false. Appelez
backtrack(0)et reconvertissez la grille en chaînes.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Remplissez d’abord la cellule la plus vide
Intuition
La solution ne dépend pas de l’ordre de remplissage ; choisis donc celui qui réduit le plus la recherche : à chaque étape, remplis la case vide qui permet le moins de chiffres. Une case qui n’autorise qu’un seul chiffre est forcée et n’ajoute aucune branche. Une case qui n’en autorise aucun est choisie immédiatement : un plateau incorrect est ainsi détecté aussitôt.
Pour compter rapidement les chiffres autorisés pour les 81 cases à chaque étape, stocke chaque ligne, colonne et bloc sous forme de masque de bits : le bit d de rows[r] est activé lorsque le chiffre d se trouve dans la ligne r. Une case autorise ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, où 0x3FE conserve les bits 1 à 9, et le nombre de chiffres autorisés correspond au nombre de bits activés. Placer d active le bit d dans trois masques ; un ou exclusif le retire.
Algorithme
- Construisez la grille et les masques
rows,colsetboxesà partir des chiffres donnés. backtrack(): parcourez toutes les cellules, calculez les chiffres autorisés pour chaque cellule vide et gardez la première cellule qui a le plus petit nombre de possibilités. S'il n'y a aucune cellule vide, renvoyez true.- Pour chaque chiffre autorisé de cette cellule, placez-le, définissez son bit dans les trois masques et renvoyez true si
backtrack()le fait ; sinon, effacez les bits. - Si aucun chiffre ne convient, videz la cellule et renvoyez false. Appelez
backtrack()et reconvertissez la grille en chaînes.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Pièges et cas limites
- Oublier d’effacer un chiffre des enregistrements de la ligne, de la colonne et du bloc lorsque tu l’annules. Les cases suivantes considèrent alors que le chiffre est déjà utilisé, et la recherche ne trouve pas la solution.
- Utiliser
r / 3 + c / 3pour le bloc. Les cases(0, 4)et(4, 0)aboutissent toutes deux à 1 : deux blocs partagent le même enregistrement et la grille ne peut jamais être remplie. Utilise(r / 3) * 3 + c / 3avec une division entière. - Ne pas s’arrêter à la première solution. Les étapes d’annulation vident alors de nouveau la grille avant que tu ne la lises.
Questions fréquentes3
Quelle est la complexité temporelle d’un solveur de sudoku par retour arrière ?
Exponentiel dans le pire des cas, O(9^m) pour m cellules vides, car chaque cellule peut se ramifier en jusqu’à 9 chiffres. Dans les grilles réelles, les règles de ligne, de colonne et de carré éliminent la plupart des branches, et remplir d’abord la cellule la plus vide élimine la plupart des autres.
Comment vérifier qu’un sudoku a exactement une solution ?
Exécutez la même recherche avec retour arrière, mais comptez les solutions et arrêtez-vous lorsque le compte atteint 2. Un compte de 1 signifie que le puzzle a une solution unique, 0 signifie qu’il n’a aucune solution. Les générateurs de puzzles exécutent cette vérification après avoir supprimé chaque indice.
Existe-t-il une méthode plus rapide que le retour sur trace pour résoudre le sudoku ?
La plupart des solveurs rapides reviennent tout de même en arrière, mais déduisent davantage d’éléments avant chaque essai. La propagation des contraintes remplit chaque case qui n’a qu’une seule possibilité et place chaque chiffre qui ne peut aller que dans une seule case de sa ligne, de sa colonne ou de son bloc, puis recommence. Le Sudoku peut également être formulé comme un problème de couverture exacte et résolu à l’aide de l’algorithme X de Knuth.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def solveSudoku(board):
# Écrivez le code iciTest #1
Argument
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Résultat attendu
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]