Sudoku

Le fichier grille-1.txt est un fichier de texte qui contient la description d'une grille de Sudoku à compléter.

In [ ]:
!cat grille-1.txt
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Les cases vides sont représentées par le chiffre 0.

Le jeu consiste à compléter les cases vides par des chiffres de 1 à 9 de sorte que chaque chiffre apparaisse une seule fois sur chaque ligne, chaque colonne et chaque carré $3\times 3$.

Quelques fonctions utilitaires

Question 1

Écrire le code de la fonction lire_grille.

In [ ]:
def lire_grille(nom_fichier):
    """ Retourne un tableau 9x9 qui représente la grille
        enregistrée dans le fichier nom_fichier.
        
        La valeur retournée est une liste de listes d'entiers.
    """
    ### À COMPLÉTER

lire_grille("grille-1.txt")

Question 2

Écrire le code de la fonction imprime_grille.

In [ ]:
def imprime_grille(grille):
    """ Écrit sur la sortie standard une représentation
        de la grille.
    """
    ### À COMPLÉTER
        
grille = lire_grille("grille-1.txt")
imprime_grille(grille)

Question 3

Écrire le code de la fonction ecrire_grille.

In [ ]:
def ecrire_grille(grille, nom_fichier):
    """ Écrit dans le fichier nom_fichier une représentation
        de la grille.
    """
    ### À COMPLÉTER

grille1 = lire_grille("grille-1.txt")
ecrire_grille(grille1, "grille-2.txt")
!cat grille-2.txt

Question 4

Écrire le code de la fonction ligne.

In [ ]:
def ligne(grille, i):
    """ Retourne la liste des 9 chiffres de la i-ème ligne.
    """
    ### À COMPLÉTER
    
grille = lire_grille("grille-1.txt")
imprime_grille(grille)
print(ligne(grille, 4))

Question 5

Écrire le code de la fonction colonne.

In [ ]:
def colonne(grille, j):
    """ Retourne la liste des 9 chiffres de la j-ème colonne.
    """
    ### À COMPLÉTER
    
grille = lire_grille("grille-1.txt")
imprime_grille(grille)
print(colonne(grille, 7))

Question 6

Écrire le code de la fonction carre.

Les carrés sont numérotés de 0 à 9 de cette façon :

 0 1 2
 3 4 5
 6 5 8
In [ ]:
def carre(grille, k):
    """ Retourne la liste des 9 chiffres du k-ème carré.
    """
    ### À COMPLÉTER
    
grille = lire_grille("grille-1.txt")
imprime_grille(grille)
print(carre(grille, 2))
print(carre(grille, 4))

Question 7

Écrire le code de la fonction numero_carre.

In [ ]:
def numero_carre(i, j):
    """ Retourne le numéro du carré qui contient la case (i, j).
    """
    ### À COMPLÉTER

print(numero_carre(5, 2))
print(numero_carre(5, 3))
print(numero_carre(6, 7))

Question 8

Écrire le code de la fonction est_complete.

In [ ]:
def est_complete(grille):
    """ Retourne True si la grille est complète et correcte.
        Retourne False sinon.
    """
    ### À COMPLÉTER

print(est_complete(lire_grille("grille-1.txt")))
print(est_complete(lire_grille("grille-1-sol.txt")))
print(est_complete(lire_grille("grille-1-fausse-sol.txt")))

Question 9

Écrire le code de la fonction possibles.

In [ ]:
def possibles(grille, i, j):
    """ Retourne la liste des chiffres qu'il est possible
        de placer sur la case (i, j).
        
        Si grille[i][j] == k est non nul alors la fonction
        retourne la liste singleton [k].
        Sinon, une valeur est possible si elle n'apparaît ni
        sur la ligne i, ni sur la colonne j, ni dans le
        carré où se trouve (i, j).
    """
    ### À COMPLÉTER

print(possibles(lire_grille("grille-1.txt"), 0, 0))
print(possibles(lire_grille("grille-1.txt"), 4, 7))

Résolution d'une grille de Sudoku

Une stratégie pour trouver une solution est la méthode du backtracking ou retour sur trace. Elle consiste à parcourir les cases dans un certain ordre en essayant pour chacune un chiffre possible. Lorsque l'on est bloqué on revient en arrière sur le dernière case remplie pour essayer une autre valeur.

Pour programmer cette méthode on choisit de classer les cases selon l'ordre lexicographique :

$$(i_1, j_1)\lt (i_2, j_2) \quad\Longleftrightarrow\quad i_1\lt i_2\quad\text{ou}\quad i_1=i_2 \text{ et } j_1\lt j_2$$

On utilise les variables de boucle suivantes :

  • (i, j) est la case que l'on cherche à remplir

  • G est un tableau $9\times 9$ qui correspond à la solution partielle construite jusqu'ici. Les cases qui précèdent (i, j) sont toutes remplies. Les autres cases sont dans le même état que celles de la grille initiale.

  • P est un tableau $9\times 9$ qui mémorise les chiffres qu'il reste encore à tester pour les cases qui précèdent (i, j) en cas de retour arrière nécessaire. De façon précise, P[u][v] est la liste des chiffres qu'il reste à tester pour la case (u, v). Pour les cases (u, v) supérieures à (i, j), P[u][v] est vide.

On ordonne les cases selon l'ordre lexicographique :

On parcourt les cases dans l'ordre en commençant par la case $(0,0)$.

Pour une case donnée Elle consiste à remplir les cases dans un ordre précis

placer une dame sur la première rangée, puis une autre sur la deuxième rangée, etc, tout en veillant à ce que la nouvelle dame placée ne soit en prise avec aucunes des autres dames déjà placées. Les dames sont placées sur les colonnes les plus à gauche possible. En cas d’impossibilité on revient en arrière (backtracking) en déplaçant la dernière dame placée d’une colonne vers la droite.

Question 10

Écrire la fonction incr.

Par exemple, la case qui suit (2, 8) est la case (3, 0)

La dernière case est (8, 8). Dans ce cas la fonction incr retourne (9, 0). Ainsi i == 9 signifie que toutes les cases ont été envisagées.

In [ ]:
def incr(i, j):
    """ Retourne la case qui suit (i, j) 
        dans l'ordre lexicographique.
    """
    ### À COMPLÉTER
    
print(incr(0, 0))
print(incr(2, 7))
print(incr(2, 8))
print(incr(8, 8))

Question 11

Écrire la fonction decr.

Par exemple, la case qui précède (2, 0) est la case (1, 8)

La première case est (0, 0). Dans ce cas la fonction decr retourne (-1, 8). Ainsi i == -1 signifie qu'il n'y a plus de retour arrière possible.

In [ ]:
def decr(i, j):
    """ Retourne la case qui précède (i, j)
        dans l'ordre lexicographique.
    """
    ### À COMPLÉTER
    
print(decr(8, 8))
print(decr(2, 1))
print(decr(2, 0))
print(decr(0, 0))

Question 12

Écrire le code de la fonction resoudre.

In [ ]:
def resoudre(grille):
    """ Retourne une grille complète solution de grille
        si une telle solution existe.
        Retourne None sinon.
    """
    ### À COMPLÉTER
            
resoudre(lire_grille("grille-1.txt"))