Aller au contenu

Exercices - Grille de Sudoku☘

Si vous ne connaissez pas encore les règles du Sudoku, cherchez sur la toile !

On dispose de trois grilles de Sudoku :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
A = [ [3,6,7,9,4,1,2,8,5],
      [1,5,2,6,8,3,4,9,7],
      [4,9,8,7,5,2,1,6,3],
      [7,4,6,1,9,5,8,3,2],
      [8,1,9,2,3,7,6,5,4],
      [2,3,5,8,6,4,7,1,9],
      [9,2,1,5,7,8,3,4,6],
      [5,8,4,3,2,6,9,7,1],
      [6,7,3,4,1,9,5,2,8] ]  

B = [ [4,2,7,9,5,1,6,8,3],
      [6,3,9,2,8,4,7,5,1],
      [8,5,1,7,6,3,9,2,4],
      [5,1,4,8,9,6,3,7,2],
      [9,7,6,4,3,2,8,1,5],
      [2,8,3,1,7,5,4,9,6],
      [3,9,2,6,1,8,5,4,7],
      [7,4,5,3,2,9,1,6,8],
      [1,6,8,5,4,7,2,3,9] ]

C = [ [9,8,5,1,3,2,4,7,6],
      [2,7,3,9,4,6,5,1,8],
      [4,1,6,5,7,8,9,2,3],
      [1,6,7,4,8,9,2,3,5],
      [8,5,2,6,1,3,7,9,4],
      [3,9,4,2,5,7,8,6,1],
      [7,4,1,3,9,5,6,8,2],
      [5,2,9,8,6,1,3,4,7],
      [6,3,8,7,2,4,1,5,9] ]

Votre mission est de vérifier que ces grilles ont été correctement complétées, c'est-à-dire qu'elles ne contiennent pas d'erreur :

  • pas de répétition d'un même chiffre dans une ligne,
  • pas de répétition d'un même chiffre dans une colonne,
  • pas de répétition d'un même chiffre dans l'un des 9 carrés 3×3.

Téléchargez le fichier « à trous » ProgB05.70.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [B05_Tableaux_de_Tableaux].

Ajoutez ensuite des tests personnalisés dans la partie principale du programme. Vous pourrez facilement produire une grille fausse pour vos tests !

Rappels
  • Enregistrez le fichier à compléter dans le dossier [B05-Tableaux_de_Tableaux] avec le nom donné à l'exercice : ProgB05.70.py.
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].
  • Le programme principal doit contenir un appel au module doctest : 
    ##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Partie 1 - Ligne correcte☘

Complétez les définitions des fonctions suivantes :

  1. verif_ligne() qui renvoie True si une ligne contient une fois et une seule chacun des chiffres de 1 à 9.

    1
2
3
4
5
6
7
    def verif_ligne(grille, numero_de_ligne):
    """
    grille - matrice sudoku
    numero_de_ligne - numéro de ligne de la grille (entre 0 et 8)
    Sortie: bool - True si la ligne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    Une piste

    On peut définir comme variable globale (c'est-à-dire en dehors du corps des fonctions) le t-uplet
    CHIFFRES = (1,2,3,4,5,6,7,8,9)
    pour y faire référence quelle que soit la fonction programmée dans cette page.

    Solution du 1.
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    ##----- Constantes -----##
CHIFFRES = (1, 2, 3, 4, 5, 6, 7, 8, 9)


##----- Définitions des fonctions -----##
def verif_ligne(grille, numero_de_ligne):
    """
    grille - matrice sudoku
    numero_de_ligne - numéro de ligne de la grille (entre 0 et 8)
    Sortie: bool - True si la ligne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    for chiffre in CHIFFRES:
        if chiffre not in grille[numero_de_ligne]:
            return False
    return True

    Attention à la boucle for et au test des lignes 13 et 14. En effet, le code : 

    13
14
    for chiffre in grille[numero_de_ligne]:
    if chiffre not in CHIFFRES:
    ne peut pas convenir puisque la ligne [1, 1, 1, 1, 1, 1, 1, 1, 1] serait considérée comme correcte. En effet, chaque entier de cette ligne est bien dans CHIFFRES mais ces entiers ne sont pas tous distincts et compris entre 1 et 9.

  2. verif_toutes_lignes() qui renvoie True si chaque ligne contient une fois et une seule chacun des chiffres de 1 à 9.

    1
2
3
4
5
6
    def verif_toutes_lignes(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque ligne respecte les règles du Sudoku,
            False sinon.
    """
    Solution du 2.
    18
19
20
21
22
23
24
25
26
27
    def verif_toutes_lignes(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque ligne respecte les règles du Sudoku,
            False sinon.
    """
    for numero_de_ligne in range(9):
        if not verif_ligne(grille, numero_de_ligne):
            return False
    return True

Partie 2 - Colonne correcte☘

Complétez les définitions des fonctions suivantes :

  1. verif_colonne() qui renvoie True si une colonne contient une fois et une seule chacun des chiffres de 1 à 9.

    1
2
3
4
5
6
7
    def verif_colonne(grille, numero_de_colonne):
    """
    grille - matrice sudoku
    numero_de_colonne - numéro de colonne de la grille (entre 0 et 8)
    Sortie: bool - True si la colonne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    Solution du 1.

    Pour faciliter la manipulation, on extrait les valeurs présentent dans la colonne numero_de_colonne et on les place dans un tableau nommé colonne :

    30
31
32
33
34
35
36
37
38
39
40
41
    def verif_colonne(grille, numero_de_colonne):
    """
    grille - matrice sudoku
    numero_de_colonne - numéro de colonne de la grille (entre 0 et 8)
    Sortie: bool - True si la colonne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    colonne = [grille[num_ligne][numero_de_colonne] for num_ligne in range(9)]
    for chiffre in CHIFFRES:
        if chiffre not in colonne:
            return False
    return True

  2. verif_toutes_colonnes() qui renvoie True si chaque colonne contient une fois et une seule chacun des chiffres de 1 à 9.

    1
2
3
4
5
6
    def verif_toutes_colonnes(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque colonne respecte les règles du Sudoku,
            False sinon.
    """
    Solution du 2.
    44
45
46
47
48
49
50
51
52
53
    def verif_toutes_colonnes(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque colonne respecte les règles du Sudoku,
            False sinon.
    """
    for numero_de_colonne in range(9):
        if not verif_colonne(grille, numero_de_colonne):
            return False
    return True

Partie 3 - Repérer les zones carrées☘

Pour traiter le cas des zones carrées, nous allons faire un choix de numérotation des carrés et remarquer que nous pouvons décrire assez facilement les coordonnées de la cellule haut gauche de chaque carré à partir de cette numérotation.

Le choix de la numérotation des carrés est la suivante :

numéroter les carrés

  1. Vérifier que la cellule haut-gauche de chaque carré a pour coordonnées le couple (ligne, colonne) tel que :

    • ligne = 3 * (numero//3)
    • colonne = 3 * (numero%3)

    où numero est le numéro du carré.

    Solution du 1.
    • La cellule haut gauche du carré numéro 0 a pour coordonnées (ligne, colonne) = (0, 0).
      Et (3 * (0//3), 3 * (0%3)) = (0, 0).
    • La cellule haut gauche du carré numéro 1 a pour coordonnées (ligne, colonne) = (0, 3).
      Et (3 * (1//3), 3 * (1%3)) = (0, 3).
    • La cellule haut gauche du carré numéro 2 a pour coordonnées (ligne, colonne) = (0, 6).
      Et (3 * (2//3), 3 * (2%3)) = (0, 6).
    • La cellule haut gauche du carré numéro 3 a pour coordonnées (ligne, colonne) = (3, 0).
      Et (3 * (3//3), 3 * (0%3)) = (3, 0).
    • La cellule haut gauche du carré numéro 4 a pour coordonnées (ligne, colonne) = (3, 3).
      Et (3 * (4//3), 3 * (4%3)) = (3, 3).
    • etc...

  2. En déduire la définition de la fonction suivante permettant de créer le tableau des chiffres contenus par un carré (identifié par son numéro) : 

    1
2
3
4
5
6
    def contenu_carre(grille, numero):
    """
    grille - matrice sudoku
    numéro - numéro d'une zone carrée
    Sortie: list - le tableau des chiffres contenus dans le carré
    """

    Solution du 2.
    56
57
58
59
60
61
62
63
64
65
66
67
68
    def contenu_carre(grille, numero):
    """
    grille - matrice sudoku
    numéro - numéro d'une zone carrée
    Sortie: list - le tableau des chiffres contenus dans le carré
    """
    ligneHG = 3*(numero//3)     # numéro de ligne de la cellule haute gauche du carré
    colonneHG = 3*(numero%3)    # numéro de colonne de la cellule haute gauche du carré
    chiffres_du_carre = []
    for i in range(ligneHG, ligneHG+3):
        for j in range(colonneHG, colonneHG+3):
            chiffres_du_carre.append(grille[i][j])
    return chiffres_du_carre
    Solution avec une définition par compréhension
    56
57
58
59
60
61
62
63
64
65
    def contenu_carre(grille, numero):
    """
    grille - matrice sudoku
    numéro - numéro d'une zone carrée
    Sortie: list - le tableau des chiffres contenus dans le carré
    """
    ligneHG = 3*(numero//3)     # numéro de ligne de la cellule haute gauche du carré
    colonneHG = 3*(numero%3)    # numéro de colonne de la cellule haute gauche du carré

    return [grille[i][j] for i in range(ligneHG, ligneHG+3) for j in range(colonneHG, colonneHG+3)]

Partie 4 - Zone carrée correcte☘

Complétez les définitions des fonctions suivantes :

  1. verif_carre() qui renvoie True si un des 9 carrés 3×3 contient une fois et une seule chacun des chiffres de 1 à 9.

    1
2
3
4
5
6
7
    def verif_carre(grille, numero):
    """
    grille - matrice sudoku
    numero - numéro d'une zone carrée (entre 0 et 8)
    Sortie: bool - True si le carré contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    Solution du 1.

    On fait bien sûr appel à la fonction contenu_carre() définie dans la partie précédente. 

    71
72
73
74
75
76
77
78
79
80
81
82
    def verif_carre(grille, numero):
    """
    grille - matrice sudoku
    numero - numéro d'une zone carrée (entre 0 et 8)
    Sortie: bool - True si le carré contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    carre = contenu_carre(grille, numero)
    for chiffre in CHIFFRES:
        if chiffre not in carre:
            return False
    return True

  2. verif_tous_carres() qui renvoie True si chacun des 9 carrés 3×3 contient une fois et une seule chacun des chiffres de 1 à 9.

    1
2
3
4
5
6
    def verif_tous_carres(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque carré respecte les règles du Sudoku,
            False sinon.
    """
    Solution du 2.
    85
86
87
88
89
90
91
92
93
94
    def verif_tous_carres(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque carré respecte les règles du Sudoku,
            False sinon.
    """
    for numero_de_carre in range(9):
        if not verif_carre(grille, numero_de_carre):
            return False
    return True

Partie 5 - Grille correcte☘

Conclure en complétant la définition de la fonction verif_grille() qui vérifie qu'une grille est correctement remplie.

1
2
3
4
5
6
def verif_grille(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si la grille respecte les règles du Sudoku,
            False sinon.
    """
Une réponse
 97
 98
 99
100
101
102
103
def verif_grille(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si la grille respecte les règles du Sudoku,
            False sinon.
    """
    return verif_toutes_lignes(grille) and verif_toutes_colonnes(grille) and verif_tous_carres(grille)
Le programme complet
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
##----- Constantes -----##
CHIFFRES = (1, 2, 3, 4, 5, 6, 7, 8, 9)


##----- Définitions des fonctions -----##
def verif_ligne(grille, numero_de_ligne):
    """
    grille - matrice sudoku
    numero_de_ligne - numéro de ligne de la grille (entre 0 et 8)
    Sortie: bool - True si la ligne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    for chiffre in CHIFFRES:
        if chiffre not in grille[numero_de_ligne]:
            return False
    return True

def verif_toutes_lignes(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque ligne respecte les règles du Sudoku,
            False sinon.
    """
    for numero_de_ligne in range(9):
        if not verif_ligne(grille, numero_de_ligne):
            return False
    return True


def verif_colonne(grille, numero_de_colonne):
    """
    grille - matrice sudoku
    numero_de_colonne - numéro de colonne de la grille (entre 0 et 8)
    Sortie: bool - True si la colonne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    colonne = [grille[num_ligne][numero_de_colonne] for num_ligne in range(9)]
    for chiffre in CHIFFRES:
        if chiffre not in colonne:
            return False
    return True


def verif_toutes_colonnes(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque colonne respecte les règles du Sudoku,
            False sinon.
    """
    for numero_de_colonne in range(9):
        if not verif_colonne(grille, numero_de_colonne):
            return False
    return True


def contenu_carre(grille, numero):
    """
    grille - matrice sudoku
    numéro - numéro d'une zone carrée
    Sortie: list - le tableau des chiffres contenus dans le carré
    """
    ligneHG = 3*(numero//3)     # numéro de ligne de la cellule haute gauche du carré
    colonneHG = 3*(numero%3)    # numéro de colonne de la cellule haute gauche du carré
    chiffres_du_carre = []
    for i in range(ligneHG, ligneHG+3):
        for j in range(colonneHG, colonneHG+3):
            chiffres_du_carre.append(grille[i][j])
    return chiffres_du_carre


def verif_carre(grille, numero):
    """
    grille - matrice sudoku
    numero - numéro d'une zone carrée (entre 0 et 8)
    Sortie: bool - True si le carré contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    carre = contenu_carre(grille, numero)
    for chiffre in CHIFFRES:
        if chiffre not in carre:
            return False
    return True


def verif_tous_carres(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si chaque carré respecte les règles du Sudoku,
            False sinon.
    """
    for numero_de_carre in range(9):
        if not verif_carre(grille, numero_de_carre):
            return False
    return True


def verif_grille(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si la grille respecte les règles du Sudoku,
            False sinon.
    """
    return verif_toutes_lignes(grille) and verif_toutes_colonnes(grille) and verif_tous_carres(grille)


##----- Tests des fonctions -----##
if __name__ == "__main__":

    A = [ [3,6,7,9,4,1,2,8,5],
        [1,5,2,6,8,3,4,9,7],
        [4,9,8,7,5,2,1,6,3],
        [7,4,6,1,9,5,8,3,2],
        [8,1,9,2,3,7,6,5,4],
        [2,3,5,8,6,4,7,1,9],
        [9,2,1,5,7,8,3,4,6],
        [5,8,4,3,2,6,9,7,1],
        [6,7,3,4,1,9,5,2,8] ]

    B = [ [4,2,7,9,5,1,6,8,3],
        [6,3,9,2,8,4,7,5,1],
        [8,5,1,7,6,3,9,2,4],
        [5,1,4,8,9,6,3,7,2],
        [9,7,6,4,3,2,8,1,5],
        [2,8,3,1,7,5,4,9,6],
        [3,9,2,6,1,8,5,4,7],
        [7,4,5,3,2,9,1,6,8],
        [1,6,8,5,4,7,2,3,9] ]

    C = [ [9,8,5,1,3,2,4,7,6],
        [2,7,3,9,4,6,5,1,8],
        [4,1,6,5,7,8,9,2,3],
        [1,6,7,4,8,9,2,3,5],
        [8,5,2,6,1,3,7,9,4],
        [3,9,4,2,5,7,8,6,1],
        [7,4,1,3,9,5,6,8,2],
        [5,2,9,8,6,1,3,4,7],
        [6,3,8,7,2,4,1,5,9] ]

    D = [ [9,8,5,1,3,2,4,7,6],
          [2,9,3,9,4,6,5,1,8],
          [4,1,6,5,7,8,9,2,3],
          [1,6,7,4,8,9,2,3,5],
          [8,5,2,6,1,3,7,9,4],
          [3,9,4,2,5,7,8,6,1],
          [7,4,1,3,9,5,6,8,2],
          [5,2,9,8,6,1,3,4,7],
          [6,3,8,7,2,4,1,5,9] ]

    print("Grille A :", verif_grille(A))
    print("Grille B :", verif_grille(B))
    print("Grille C :", verif_grille(C))
    print("Grille D :", verif_grille(D))

Partie 6 - Factorisation de code☘

Dans le code complet de la question précédente, vous pouvez remarquer que les fonctions verif_toutes_lignes(), verif_toutes_colonnes() et verif_tous_carres() ont exactement la même structure.

Remplacez ces trois fonctions par une seule fonction verif_blocs() puis réécrivez la fonction verif_grille() à l'aide de cette fonction verif_blocs().

Une solution
##----- Constantes -----##
CHIFFRES = (1,2,3,4,5,6,7,8,9)


##----- Définitions des fonctions -----##
def verif_ligne(grille, numero_de_ligne):
    """
    grille - matrice sudoku
    numero_de_ligne - numéro de ligne de la grille (entre 0 et 8)
    Sortie: bool - True si la ligne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    for chiffre in CHIFFRES:
        if chiffre not in grille[numero_de_ligne]:
            return False
    return True


def verif_colonne(grille, numero_de_colonne):
    """
    grille - matrice sudoku
    numero_de_colonne - numéro de colonne de la grille (entre 0 et 8)
    Sortie: bool - True si la colonne contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    colonne = [grille[num_ligne][numero_de_colonne] for num_ligne in range(9)]
    for chiffre in CHIFFRES:
        if chiffre not in colonne:
            return False
    return True


def contenu_carre(grille, numero):
    """
    grille - matrice sudoku
    numéro - numéro d'une zone carrée
    Sortie: list - le tableau des chiffres contenus dans le carré
    """
    ligneHG = 3*(numero//3)     # numéro de ligne de la cellule haute gauche du carré
    colonneHG = 3*(numero%3)    # numéro de colonne de la cellule haute gauche du carré

    return [grille[i][j] for i in range(ligneHG, ligneHG+3) for j in range(colonneHG, colonneHG+3)]


def verif_carre(grille, numero):
    """
    grille - matrice sudoku
    numero - numéro d'une zone carrée (entre 0 et 8)
    Sortie: bool - True si le carré contient chacun des chiffres une fois et une seule,
            False sinon.
    """
    carre = contenu_carre(grille, numero)
    for chiffre in CHIFFRES:
        if chiffre not in carre:
            return False
    return True


def verif_blocs(grille, fonction_bloc):
    """
    grille - matrice sudoku
    fonction_bloc - fonction de vérification d'un bloc (ligne, colonne ou carré)
    Sortie: bool - True si chaque bloc respecte les règles du Sudoku,
            False sinon.
    """
    for numero_bloc in range(9):
        if not fonction_bloc(grille, numero_bloc):
            return False
    return True

def verif_grille(grille):
    """
    grille - matrice sudoku
    Sortie: bool - True si la grille respecte les règles du Sudoku,
            False sinon.
    """
    if not verif_blocs(grille, verif_ligne):
        return False
    if not verif_blocs(grille, verif_colonne):
        return False
    if not verif_blocs(grille, verif_carre):
        return False
    return True


##----- Tests des fonctions -----##
if __name__ == "__main__":

    A = [ [3,6,7,9,4,1,2,8,5],
        [1,5,2,6,8,3,4,9,7],
        [4,9,8,7,5,2,1,6,3],
        [7,4,6,1,9,5,8,3,2],
        [8,1,9,2,3,7,6,5,4],
        [2,3,5,8,6,4,7,1,9],
        [9,2,1,5,7,8,3,4,6],
        [5,8,4,3,2,6,9,7,1],
        [6,7,3,4,1,9,5,2,8] ]

    B = [ [4,2,7,9,5,1,6,8,3],
        [6,3,9,2,8,4,7,5,1],
        [8,5,1,7,6,3,9,2,4],
        [5,1,4,8,9,6,3,7,2],
        [9,7,6,4,3,2,8,1,5],
        [2,8,3,1,7,5,4,9,6],
        [3,9,2,6,1,8,5,4,7],
        [7,4,5,3,2,9,1,6,8],
        [1,6,8,5,4,7,2,3,9] ]

    C = [ [9,8,5,1,3,2,4,7,6],
        [2,7,3,9,4,6,5,1,8],
        [4,1,6,5,7,8,9,2,3],
        [1,6,7,4,8,9,2,3,5],
        [8,5,2,6,1,3,7,9,4],
        [3,9,4,2,5,7,8,6,1],
        [7,4,1,3,9,5,6,8,2],
        [5,2,9,8,6,1,3,4,7],
        [6,3,8,7,2,4,1,5,9] ]

    D = [ [9,8,5,1,3,2,4,7,6],
          [2,9,3,9,4,6,5,1,8],
          [4,1,6,5,7,8,9,2,3],
          [1,6,7,4,8,9,2,3,5],
          [8,5,2,6,1,3,7,9,4],
          [3,9,4,2,5,7,8,6,1],
          [7,4,1,3,9,5,6,8,2],
          [5,2,9,8,6,1,3,4,7],
          [6,3,8,7,2,4,1,5,9] ]

    print("Grille A :", verif_grille(A))
    print("Grille B :", verif_grille(B))
    print("Grille C :", verif_grille(C))
    print("Grille D :", verif_grille(D))