sudoku — Solveur de sudoku

Usage

Un solveur de Sudoku

usage: sudoku [-h] [-v] [-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

-v, --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: 4

-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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def solveur(candidats, fonction):
    """Essaye de résoudre l'ensemble des candidats.

    Boucle infinie qui prend des candidats dans la queue, tente de les
    resoudre, et applique la fonction quand ils sont resolu.
    """
    while True:
        grille = candidats.get()
        grille.remplit()
        if grille.resolu:
            fonction(grille)
        elif grille.impossible:
            pass
        else:
            (x, y) = grille.cherche_plus_proche()
            for valeur in grille.possible_case[x][y]:
                copie = grille.copy()
                copie.affecte((x, y), valeur)
                candidats.put(copie)
        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
 2
 3
 4
 5
 6
 7
 8
 9
10
    def remplit(self):
        """Remplit autant que possible la grille, avec les contraintes connues.

        S'arrete quand plus rien ne peut etre deduit.
        """
        while self.contraintes and not self.impossible:
            # Extrait une contrainte
            contrainte = self.contraintes.pop()
            # Applique la contrainte
            contrainte.fonction(*contrainte.argument)