Solveur de Sudoku récursif utilisant Python
Un solveur de Sudoku qui fonctionne de manière récursive. J'apprécierais vos commentaires sur le style de codage, la structure et la façon de l'améliorer. Merci beaucoup pour votre temps.
Structure du code
Le solveur fonctionne en acceptant une chaîne de 81 chiffres pour l'entrée de puzzle Sudoku. Les zéros sont considérés comme des cellules vides. Il l'analyse dans un tableau Numpy 9x9.
La get_candidatesfonction crée des listes de chiffres possibles pour remplir chaque cellule en suivant les règles de Sudoku (pas de répétition de 1 à 9 chiffres le long des lignes, des colonnes et des sous-grilles 3x3).
La fonction principale du solveur est solve. Premièrement, il rejette les mauvais candidats avec la filter-candidatesfonction. Les «mauvais candidats» sont ceux qui, lorsqu'ils sont remplis dans une cellule vide, ont conduit à une autre cellule n'ayant plus de candidats ailleurs sur la grille Sudoku.
Après avoir filtré les candidats, fill_singlesest appelé pour remplir les cellules vides qui n'ont qu'un seul candidat restant. Si ce processus conduit à une grille de Sudoku complètement remplie, il est renvoyé comme solution. Il y a une clause à retourner Nonequi est utilisée pour revenir en arrière par la make_guessfonction. Cette fonction remplira la prochaine cellule vide avec le moins de candidats avec l'un de ses candidats, une valeur «deviner». Il appelle ensuite récursivement solvepour trouver une solution ou atteindre une grille sans solution (dans ce cas, solveretourne Noneet les dernières modifications sont annulées).
from copy import deepcopy
import numpy as np
def create_grid(puzzle_str: str) -> np.ndarray:
"""Create a 9x9 Sudoku grid from a string of digits"""
# Deleting whitespaces and newlines (\n)
lines = puzzle_str.replace(' ','').replace('\n','')
digits = list(map(int, lines))
# Turning it to a 9x9 numpy array
grid = np.array(digits).reshape(9,9)
return grid
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
subgrids = []
for box_i in range(3):
for box_j in range(3):
subgrid = []
for i in range(3):
for j in range(3):
subgrid.append(grid[3*box_i + i][3*box_j + j])
subgrids.append(subgrid)
return np.array(subgrids)
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
def is_valid_grid(grid : np.ndarray) -> bool:
"""Verify the input grid has a possible solution"""
candidates = get_candidates(grid)
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 0:
return False
return True
def is_solution(grid : np.ndarray) -> bool:
"""Verify if the input grid is a solution"""
if np.all(np.sum(grid, axis=1) == 45) and \
np.all(np.sum(grid, axis=0) == 45) and \
np.all(np.sum(get_subgrids(grid), axis=1) == 45):
return True
return False
def filter_candidates(grid : np.ndarray) -> list:
"""Filter input grid's list of candidates"""
test_grid = grid.copy()
candidates = get_candidates(grid)
filtered_candidates = deepcopy(candidates)
for i in range(9):
for j in range(9):
# Check for empty cells
if grid[i][j] == 0:
for candidate in candidates[i][j]:
# Use test candidate
test_grid[i][j] = candidate
# Remove candidate if it produces an invalid grid
if not is_valid_grid(fill_singles(test_grid)):
filtered_candidates[i][j].remove(candidate)
# Revert changes
test_grid[i][j] = 0
return filtered_candidates
def merge(candidates_1 : list, candidates_2 : list) -> list:
"""Take shortest candidate list from inputs for each cell"""
candidates_min = []
for i in range(9):
row = []
for j in range(9):
if len(candidates_1[i][j]) < len(candidates_2[i][j]):
row.append(candidates_1[i][j][:])
else:
row.append(candidates_2[i][j][:])
candidates_min.append(row)
return candidates_min
def fill_singles(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill input grid's cells with single candidates"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
any_fill = True
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
return grid
def make_guess(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill next empty cell with least candidates with first candidate"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
# Getting the shortest number of candidates > 1:
min_len = sorted(list(set(map(
len, np.array(candidates).reshape(1,81)[0]))))[1]
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == min_len:
for guess in candidates[i][j]:
grid[i][j] = guess
solution = solve(grid)
if solution is not None:
return solution
# Discarding a wrong guess
grid[i][j] = 0
def solve(grid : np.ndarray) -> np.ndarray:
"""Recursively find a solution filtering candidates and guessing values"""
candidates = filter_candidates(grid)
grid = fill_singles(grid, candidates)
if is_solution(grid):
return grid
if not is_valid_grid(grid):
return None
return make_guess(grid, candidates)
# # Example usage
# puzzle = """100920000
# 524010000
# 000000070
# 050008102
# 000000000
# 402700090
# 060000000
# 000030945
# 000071006"""
# grid = create_grid(puzzle)
# solve(grid)
```
Réponses
J'ai pu améliorer les performances du programme d'environ 900% sans comprendre ni modifier une grande partie de l'algorithme en une heure environ. Voici ce que j'ai fait:
Tout d'abord, vous avez besoin d'un benchmark. C'est très simple, chronométrez simplement votre programme
start = time.time()
solve(grid)
print(time.time()-start)
Sur mon ordinateur, cela a pris environ 4,5 secondes. Ceci est notre base.
La prochaine chose est de profiler. L'outil que j'ai choisi est VizTracer, qui est développé par moi-même :)https://github.com/gaogaotiantian/viztracer
VizTracer générera un rapport HTML (ou json qui pourrait être chargé par chrome :: // tracing) de la chronologie de l'exécution de votre code. Cela ressemble à ceci dans votre version originale:
Comme vous pouvez le constater, il y a beaucoup d'appels là-bas. La chose que nous devons faire est de déterminer quel est le goulot d'étranglement ici. La structure n'est pas compliquée, beaucoup fill_singlessont appelées, et nous devons zoomer pour vérifier ce qu'il y a là-dedans.
Il est très clair que get_candidatesc'est la fonction qui a causé la plupart du temps fill_singles, qui occupe la majeure partie de la chronologie. C'est donc la fonction que nous voulons examiner en premier.
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
La chose qui a attiré mon attention en premier était la fin de votre boucle imbriquée pour. Vous avez vérifié si grid[i][j]est rempli. Si c'est le cas, c'est le seul candidat. Cependant, s'il est rempli, cela n'a rien à voir avec candidatesce que vous avez calculé très durement dans votre boucle for imbriquée.
Donc, la première chose que j'ai faite a été de déplacer le chèque au début de la boucle for.
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
row_candidates.append(list(candidates))
Cette optimisation à elle seule réduit de moitié le temps de fonctionnement, nous en sommes maintenant à environ 2,3 secondes.
Ensuite, j'ai remarqué que dans votre boucle for imbriquée, vous faites beaucoup d'opérations de set redondantes. Même row / col / sub ne doit être calculé que 9 fois, vous le calculez 81 fois, ce qui est plutôt mauvais. J'ai donc déplacé le calcul hors de la boucle for.
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
row_sets = [set(grid[i]) for i in range(9)]
col_sets = [set(grid[:, j]) for j in range(9)]
subgrid_sets = [set(subgrids[i]) for i in range(9)]
total_sets = set(range(10))
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = row_sets[i]
col = col_sets[j]
sub = subgrid_sets[subgrid_index(i, j)]
common = row | col | sub
candidates = total_sets - common
# If the case is filled take its value as the only candidate
row_candidates.append(list(candidates))
grid_candidates.append(row_candidates)
return grid_candidates
Cela a réduit le temps de fonctionnement à environ 1,5 s. Remarquez que je n'ai pas encore essayé de comprendre votre algorithme. La seule chose que j'ai faite a été d'utiliser VizTracer pour trouver la fonction qui doit être optimisée et faire la même transformation logique. J'ai amélioré les performances d'environ 300% en 15 minutes environ.
À ce stade, la surcharge de VizTracer sur WSL est importante, j'ai donc désactivé la trace de la fonction C. Seules les fonctions Python étaient restées et la surcharge était d'environ 10%.
Maintenant que cela a get_candidatesété amélioré (bien que cela puisse être mieux fait), nous devons prendre une image plus grande de cela. Ce que je peux observer à partir du résultat de VizTracer est que fill_singlesappelé get_candidatestrès souvent, à trop d'appels. (C'est quelque chose qui est difficile à remarquer sur cProfiler)
L'étape suivante consistait donc à déterminer si nous pouvions fill_singlesappeler get_candidatesmoins souvent. Ici, cela nécessite un certain niveau de compréhension de l'algorithme.
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
Il semble qu'ici vous avez essayé de remplir un espace avec un seul candidat, et de recalculer les candidats de la grille entière, puis de trouver le vide suivant avec un candidat. C'est une méthode valide, mais cela a provoqué trop d'appels à get_candidates. Si vous y réfléchissez, lorsque nous remplissons un blanc avec un nombre n, tous les autres blancs avec un seul candidat qui n'est npas affecté ne seront pas affectés. Ainsi, lors d'un passage de la grille, nous pourrions en fait essayer de remplir plus de blancs, tant que nous ne remplissons pas deux fois le même nombre. De cette façon, nous pouvons appeler get_candidatesmoins souvent, ce qui est un énorme consommateur de temps. J'ai utilisé un ensemble pour ce faire.
filled_number = set()
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0 and candidates[i][j][0] not in filled_number:
grid[i][j] = candidates[i][j][0]
filled_number.add(candidates[i][j][0])
any_fill = True
candidates = merge(get_candidates(grid), candidates)
Cela a porté le temps de fonctionnement à 0,9 s.
Ensuite, j'ai regardé le rapport VizTracer, je me suis rendu compte qu'il fill_singlesétait presque toujours appelé par filter_candidateset que la seule chose qui filter_candidatesm'intéressait, c'est de savoir si fill_singlesrenvoie une grille valide. C'est une information que nous pourrions connaître tôt, à condition de fill_singlestrouver un poste sans candidat. Si nous revenons tôt, nous n'avons pas besoin de calculer get_candidatescela plusieurs fois.
J'ai donc changé un peu la structure du code, j'ai fait un fill_singlesretour Nones'il ne trouve pas de grille valide.
Enfin, j'ai pu rendre le temps d'exécution à 0,5 s, ce qui est 900% plus rapide que la version originale.
C'était en fait une aventure amusante car je testais mon projet VizTracer et essayais de déterminer s'il était utile de localiser la partie qui prend du temps. Cela a bien fonctionné :)
Numpyification
get_subgridsréorganise essentiellement un tableau numpy avec un minimum de numpy. Cela pourrait être fait avec numpy lui-même, par exemple:
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
swapped = np.swapaxes(np.reshape(grid, (3, 3, 3, 3)), 1, 2)
return np.reshape(swapped, (9, 9))
L'inconvénient, je suppose, c'est que l'échange des deux axes du milieu d'un tableau 4D est un peu hallucinant.
Performance
Presque tout le temps est passé get_candidates. Je pense que les raisons en sont principalement:
- Il est appelé trop souvent. Par exemple, après avoir rempli une cellule (comme dans
fill_singles), plutôt que de recalculer les candidats à partir de zéro, il serait plus rapide de simplement supprimer la nouvelle valeur des candidats dans la même ligne / colonne / maison. - Si une cellule est remplie, la liste des candidats est juste la valeur remplie, mais le calcul de l'ensemble coûteux est quand même effectué. C'est facile à éviter en déplaçant simplement ces instructions dans le fichier
if.
Performances algorithmiques
Ce solveur utilise uniquement Naked Singles comme "technique de propagation", l'ajout de Hidden Singles est selon mon expérience un très grand pas en avant vers un solveur efficace.