Aller au contenu

Grille de Sudoku☘

Attention

Page facultative, exercices d'entraînement.

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

On dispose de grilles complétées de Sudoku.

Votre mission est de vérifier qu'elles 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.

Voici quelques exemplaires des grilles dont on dispose:

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

Ces trois grilles sont correctes. Vous pourrez facilement en produire une fausse pour vos tests!

Vérifier qu'une ligne est correcte☘

  • Écrire une fonction vérifiant qu'une ligne contient une fois et une seule chacun des chiffres de 1 à 9.
def verifieLigne(grille, numero_de_ligne):
    """
    grille -- matrice suddoku
    numero_de_ligne -- numéro de ligne de la grille (entre 0 et 8)

    renvoie True si la ligne contient chacun des chiffres une fois et une seule, 
    False sinon.
    """
  • Écrire une fonction vérifiant que chaque ligne contient une fois et une seule chacun des chiffres de 1 à 9.
def verifieLignes(grille):
    """
    grille -- matrice sudoku

    renvoie True si chaque ligne respecte les règles du Sudoku, False sinon.
    """
une ligne

Comme une ligne présente 9 cellules et qu'il y a neuf chiffres à placer, on peut par exemple vérifier que chacun s'y trouve (il est alors impossible que l'un d'eux s'y trouve plusieurs fois).

CHIFFRES = (1,2,3,4,5,6,7,8,9)        

def verifieLigne(grille, numero_de_ligne):
    """
    grille -- matrice suddoku
    numero_de_ligne -- numéro de ligne de la grille (entre 0 et 8)

    renvoie 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
toutes les lignes

Ce fichier ipynb propose un code possible.

Version html:

Vérifier qu'une colonne est correcte☘

  • Écrire une fonction vérifiant qu'une colonne contient une fois et une seule chacun des chiffres de 1 à 9.
def verifieColonne(grille, numero_de_colonne):
    """
    grille -- matrice suddoku
    numero_de_colonne -- numéro de colonne de la grille (entre 0 et 8)

    renvoie True si la colonne contient chacun des chiffres une fois et une seule, 
    False sinon.
    """
  • Écrire une fonction vérifiant que chaque colonne contient une fois et une seule chacun des chiffres de 1 à 9.
def verifieColonnes(grille):
    """
    grille -- matrice sudoku

    renvoie True si chaque colonne respecte les règles du Sudoku, False sinon.
    """
une colonne
def verifieColonne(grille, numero_de_colonne):
    """
    grille -- matrice suddoku
    numero_de_colonne -- numéro de colonne de la grille (entre 0 et 8)

    renvoie True si la colonne contient chacun des chiffres une fois et une seule, False sinon.
    """
    colonneDeChiffres = [grille[num_ligne][numero_de_colonne] for num_ligne in range(9)]
    for chiffre in CHIFFRES:
        if chiffre not in colonneDeChiffres:
            return False
    return True
toutes les colonnes

Ce fichier ipynb propose un code possible.

Version html:

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

  • Vérifier que la cellule haut gauche de chaque carré a pour couple (ligne, colonne) le couple (3 * (numero//3), 3 * (numero%3)) où numero est le numéro du carré.
Vérification
  • La cellule haut gauche du carré 0 a pour coordonnées (ligne, colonne) = (0, 0). Et (3 * (0//3), 3 * (0%3)) = (0, 0).
  • La cellule haut gauche du carré 1 a pour coordonnées (ligne, colonne) = (0, 3). Et (3 * (1//3), 3 * (1%3)) = (0, 3).
  • La cellule haut gauche du carré 2 a pour coordonnées (ligne, colonne) = (0, 6). Et (3 * (2//3), 3 * (2%3)) = (0, 6).
  • La cellule haut gauche du carré 3 a pour coordonnées (ligne, colonne) = (3, 0). Et (3 * (3//3), 3 * (0%3)) = (3, 0).
  • La cellule haut gauche du carré 4 a pour coordonnées (ligne, colonne) = (3, 3). Et (3 * (4//3), 3 * (4%3)) = (3, 3).
  • ...etc
  • En déduire un code permettant de créer la liste des chiffres contenus par un carré (identifié par son numéro).
Contenu d'un carré

Un code possible:

def contenuCarre(grille, numero):
    """
    grille -- matrice 9*9 sudoku
    numéro -- numéro d'une zone carrée

    renvoie la liste 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é

    carreDeChiffres = []
    for i in range(ligneHG, ligneHG+3):
        for j in range(colonneHG, colonneHG+3):
            carreDeChiffres.append(grille[i][j])
    return carreDeChiffres
  • Si ce n'est pas déjà fait, écrire la création de la liste de la question précédente par compréhension.
Contenu d'un carré par compréhension

Un code possible:

def contenuCarre(grille, numero):
    """
    grille -- matrice 9*9 sudoku
    numéro -- numéro d'une zone carrée

    renvoie la liste 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)]

Vérifier qu'une zone carrée est correcte☘

Écrire:

  • Une fonction vérifiant qu'un des 9 carrés 3×3 contient une fois et une seule chacun des chiffres de 1 à 9.
  • Une fonction vérifiant que chacun des 9 carrés 3×3 contient une fois et une seule chacun des chiffres de 1 à 9.
un carré

Un code possible:

def verifieCarre(grille, numero):
    """
    grille -- matrice 9*9 sudoku
    numero -- numéro entre 0 et 8 d'une zone carrée 

    renvoie True si la zone contient exactement une fois chacun des chiffres de 1 à 9, False sinon.
    """
    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é
    carreDeChiffres = [grille[i][j] for i in range(ligneHG, ligneHG+3) for j in range(colonneHG, colonneHG+3)]
    for chiffre in CHIFFRES:
        if chiffre not in carreDeChiffres:
            return False
    return True
tous les carrés

Un code possible:

def verifieCarres(grille):
    """
    grille -- matrice 9*9 sudoku

    renvoie True si chaque carré est rempli en respectant les règles sudoku, False sinon.
    """
    for num_carre in range(9):
        if not verifieCarre(grille, num_carre):
            return False
    return True

Vérifier qu'une grille est correcte☘

Écrire maintenant une fonction vérifiant qu'une grille est correctement remplie.

Note

Il suffit de faire appel aux trois fonctions précédentes, c'est à dire de vérifier que chaque ligne, chaque colonne, chaque carré est correctement rempli.

Grille correcte

Ce fichier ipynb propose un code possible.

Version html:

Factorisation de code☘

Dans le code complet de la question précédente, vous pouvez remarquer que les fonctions verifieCarres, verifieColonnes et verifieLignes ont exactement la même structure.

Remplacez ces trois fonctions par une seule fonction verifieBlocs puis réécrire la fonction verifieGrille à l'aide de cette fonction verifieBlocs.

factorisons

Un code:

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



# une grille avec erreur:
D = [ [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],
      [5,3,8,7,2,4,1,5,9]
    ]


CHIFFRES = (1,2,3,4,5,6,7,8,9)        

def verifieLigne(grille, ligne):
    """
    grille -- matrice suddoku
    ligne -- numéro de ligne de la grille (entre 0 et 8)

    renvoie True si la ligne contient chacun des chiffres une fois et une seule, False sinon.
    """
    for chiffre in CHIFFRES:
        if chiffre not in grille[ligne]:
            return False
    return True










def verifieColonne(grille, colonne):
    """
    grille -- matrice suddoku
    colonne -- numéro de colonne de la grille (entre 0 et 8)

    renvoie True si la colonne contient chacun des chiffres une fois et une seule, False sinon.
    """
    colonneDeChiffres = [grille[ligne][colonne] for ligne in range(9)]
    for chiffre in CHIFFRES:
        if chiffre not in colonneDeChiffres:
            return False
    return True





def contenuCarre(grille, numero):
    """
    grille -- matrice 9*9 sudoku
    numéro -- numéro d'une zone carrée

    renvoie la liste 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 verifieCarre(grille, numero):
    """
    grille -- matrice 9*9 sudoku
    numero -- numéro entre 0 et 8 d'une zone carrée 

    renvoie True si la zone contient exactement une fois chacun des chiffres de 1 à 9, False sinon.
    """
    carreDeChiffres = contenuCarre(grille, numero)
    for chiffre in CHIFFRES:
        if chiffre not in carreDeChiffres:
            return False
    return True    






def verifieBlocs(grille, fonctionBloc):
    """
    grille -- matrice sudoku
    fonctionBloc -- fonction de vérification d'un bloc (ligne, colonne ou carré)

    renvoie True si chaque bloc respecte les règles du Sudoku, False sinon.
    """
    for numeroBloc in range(9):
        if not fonctionBloc(grille, numeroBloc):
            return False
    return True    

def verifieGrille(grille):
    """
    grille -- matrice 9*9 sudoku

    renvoie True si grille est remplie suivant les règles du sudoku, False sinon.
    """
    if not verifieBlocs(grille, verifieLigne): return False
    if not verifieBlocs(grille, verifieColonne): return False
    if not verifieBlocs(grille, verifieCarre): return False
    return True


print(verifieGrille(A))
print(verifieGrille(B))
print(verifieGrille(C))
print(verifieGrille(D))