Activité Nsi : SUDOKU

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

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

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:

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

• En déduire un code permettant de créer la liste des chiffres contenus par un carré (identifié par son numéro).

• Si ce n'est pas déjà fait, écrire la création de la liste de la question précédente par compréhension.

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.

Vérifier qu'une grille est correcte

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

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