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

 

 

 

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
toutes les colonnes

 

 

 

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

 

 

 

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

 

 

 

  • 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

 

 

 

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é
tous les carrés

 

 

 

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

 

 

 

Factorisation de code

Dans le code complet de la question précédente, vous pouvez remarquer que les fonctions verifieCarresverifieColonnes 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 

footer2

Richard GAUTHIER
Professeur de Physique Appliquée
Certification ISN
Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.

www.carhaix2020.bzh