sudoku — Solveur de sudoku¶
Usage¶
Un solveur de Sudoku
usage: sudoku [-h] [--version] [-f {short,long}] [-j PROCESSUS] [-a ACTIONS]
[fichier]
Positional Arguments¶
- fichier
File containing the starting array. If absent, array is read from standard input.
Default:
<_io.TextIOWrapper name='<stdin>' mode='r' encoding='utf-8'>
Named Arguments¶
- --version
show program’s version number and exit
- -f, --format
Possible choices: short, long
Input file format: « short » (…232….4….1) or long (lines of « … 2 3 »).
Default:
'long'- -j, --jobs
Number of jobs to run simultaneously. Default is the number of cpu cores.
Default:
2- -a, --actions
Action to perform on solved arrays. This argument is a combination of letters “p” (print solution), “c” (count solutions), and “t” (time solutions).
Default:
'p'
Algorithme¶
Autres algorithmes¶
Je suis loin d’être le seul à m’être intéressé à ce problème, et je suis loin de proposer la meilleure solution. Par exemple, Peter Norvig a réalisé un solveur de sudoku bien plus rapide que le mien. En revanche, il ne peut résoudre que des grilles de 9x9.
Représentation des données¶
Grille¶
Une grille de sudoku est représentée par l’objet
Grille, dont un de ses attributs est un
tableau (sous la forme d’une liste de listes) des valeurs de ses cellules
(None si elles sont inconnues). Elle contient également un ensemble des
contraintes connues sur la grille, dans l’attribut Grille.contraintes.
Contraintes¶
Les contraintes sur la grille sont stockées de deux manières différentes.
Celles déjà prises en compte sont stockées dans les attributs
Grille.possible_{case,ligne,colonne,bloc}:
- Grille.possible_case¶
L’élément possible_case[x][y] contient l’ensemble des entiers possibles pour la case (x, y). Lorsque cette liste ne contient qu’un élément, cet élément peut être attribué à la case.
- Grille.possible_ligne¶
L’élément possible_ligne[y][valeur] contient l’ensemble des absisses possibles pour la valeur valeur dans la ligne d’abscisse y. Lorsque cette liste ne contient qu’un élément, valeur peut être attribué à la case (x, y).
- Grille.possible_colonne¶
Même fonction que
Grille.possible_ligne, pour les colonnes.
- Grille.possible_bloc¶
L’élément possible_bloc[bloc][valeur] contient l’ensemble des indices possibles pour valeur dans le bloc d’indice bloc (un bloc désigne ici une carré de la grille devant contenir tous les nombres de 1 à \(taille^2\)). Lorsque cette liste ne contient qu’un élément, valeur peut être attribué à la case d’indice correspondant dans le bloc.
Les contraintes en cours de traitement, elles, sont stockées dans l’attribut
Grille.contraintes. Cette liste contient une liste de contraintes à
vérifier. La raison de cette liste (pourquoi les contraintes ne sont-elles pas
reportées immédiatement dans les attributs Grille.possible_* ?) est
expliquée dans la partie suivante.
Recherche de solutions¶
Une file contient l’ensemble des grilles incomplètes à étudier. La résolution,
mise en œuvre dans la fonction solveur()
consiste à prendre une grille dans cette liste, et la remplir autant que
possible sans faire d’hypothèses (avec la méthode Grille.remplit()).
Si la grille est remblie, une solution a été trouvée. Sinon, à partir de la
case qui a le moins de possibilités, mettre dans la file les grilles
correspondant aux hypothèses sur cette case.
1def solveur(candidats, fonction):
2 """Essaye de résoudre l'ensemble des candidats.
3
4 Boucle infinie qui prend des candidats dans la queue, tente de les
5 resoudre, et applique la fonction quand ils sont resolu.
6 """
7 while True:
8 grille = candidats.get()
9 grille.remplit()
10 if grille.resolu:
11 fonction(grille)
12 elif grille.impossible:
13 pass
14 else:
15 (x, y) = grille.cherche_plus_proche()
16 for valeur in grille.possible_case[x][y]:
17 copie = grille.copy()
18 copie.affecte((x, y), valeur)
19 candidats.put(copie)
20 candidats.task_done()
La fonction Grille.remplit() prend l’ensemble des contraintes en
attente de traitement (l’attribut Grille.contraintes), et applique les
effets sur la grille. Ces opérations pouvant faire naitre de nouvelles
contraintes, la taille de la boucle n’est pas connue à l’avance. Lorsque la
liste des contraintes est vide, c’est que la grille n’est pas possible, qu’elle
est résolue, ou qu’il est impossible de la remplir davantage sans faire
d’hypothèses.
1 def remplit(self):
2 """Remplit autant que possible la grille, avec les contraintes connues.
3
4 S'arrete quand plus rien ne peut etre deduit.
5 """
6 while self.contraintes and not self.impossible:
7 # Extrait une contrainte
8 contrainte = self.contraintes.pop()
9 # Applique la contrainte
10 contrainte.fonction(*contrainte.argument)