Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Table des matières
Solveur de Sudoku
Présentation
Soit une grille de 9×9 cases. La grille est notamment subdiviser en 9 zones (dans l'exemple, entourées en gros traits). Quelques cases de la grille sont déjà remplies par un chiffre.
On souhaite compléter les cases de la grille en choisissant des chiffres entre 1 et 9 (compris) La solution doit respecter les contraintes :
- dans chaque colonne, chaque chiffre présent 1x,
- dans chaque ligne, chaque chiffre présent 1x,
- dans chaque zone, chaque chiffre présent 1x.
Tenant compte des chiffres déjà écrits dans la grille, il existe une et une seule solution.
Méthode de résolution
Première technique, la plus simple, chercher les cases dans lesquelles un seul candidat est possible.
Exemple, dans la première case, seul le 1 est possible. On peut donc écrire 1 dans cette case. Tenant compte de choix, on peut mettre à jour les candidats dans les cases concernées.
On peut continuer tant que l'on trouve des cases pour lesquelles il y a un candidat unique.
Pour cette grille facile, cette technique suffit.
Implémentation
Choix d'une représentation pour la grille
Prenons la grille exemple. On peut adopter deux approches qui ont leurs qualités et leurs défauts.
# grille, tableau 2D
grille = [ [0, 0, 0, 0, 3, 0, 2, 0, 0],
[7, 0, 5, 2, 0, 0, 0, 9, 0],
[8, 3, 0, 4, 6, 9, 1, 5, 0],
[2, 0, 0, 0, 9, 4, 0, 3, 0],
[9, 8, 0, 0, 0, 3, 0, 0, 2],
[6, 1, 3, 8, 0, 2, 0, 0, 9],
[4, 0, 0, 1, 0, 0, 7, 0, 3],
[3, 7, 8, 0, 2, 0, 4, 0, 0],
[0, 6, 1, 0, 0, 0, 0, 0, 0] ]
# lecture de la ligne 3 colonne 2
grille[3][2]
# le coin supérieur gauche est en ligne 0 colonne 0
# grille ramenée à une simple ligne
grille = [0, 0, 0, 0, 3, 0, 2, 0, 0,
7, 0, 5, 2, 0, 0, 0, 9, 0,
8, 3, 0, 4, 6, 9, 1, 5, 0,
2, 0, 0, 0, 9, 4, 0, 3, 0,
9, 8, 0, 0, 0, 3, 0, 0, 2,
6, 1, 3, 8, 0, 2, 0, 0, 9,
4, 0, 0, 1, 0, 0, 7, 0, 3,
3, 7, 8, 0, 2, 0, 4, 0, 0,
0, 6, 1, 0, 0, 0, 0, 0, 0]
# lecture de la ligne 3 colonne 2
grille[3*9+2]
# le coin supérieur gauche est en ligne 0 colonne 0
La grille à 1 dimension me parait meilleure. Dans tous les cas, il est préférable de ne pas manipuler la grille directement. Mieux vaut créer les fonctions read_cell et set_cell qui prennent charge la lecture et l'écriture dans une case du tableau.
Fonctions utiles
Je vous propose l'implémentation suivante – à vous de compléter les fonctions.
# solveur de sudoku
# grille représente une grille de sudoku.
def read_cell(grille:list, ligne:int, col:int) -> int:
'''
renvoie le contenu de la grille pour ligne et colonne indiquée
'''
def set_cell(grille:list, ligne:int, col:int, valeur:int):
'''
Écrit la valeur désirée dans la grille, à la ligne et colonne indiquée.
'''
def connnus_ligne(grille:list, ligne:int) -> list:
'''
cette fonction renvoie tous les chiffres déjà écrits dans une certaine ligne
sous forme d'un tableau, pas forcément dans l'ordre
par exemple [7,5,2,9] pour la ligne 1 (la 2e ligne donc)
'''
def connus_colonne(grille:list, colonne:int) -> list:
'''
même chose pour une colonne
'''
def connus_region(grille:list, ligne:int, colonne:int) -> list:
'''
même chose pour une région
'''
def restants(grille:list, ligne:int, colonne:int) -> list:
'''
cette fonction, pour une certaine ligne et colonne,
à condition que cette case soit actuellement vide,
commence par chercher tous les nombres déjà connus dans la même ligne , colonne, région
et déduit les valeurs restantes possibles, ceux qu'on appelle les candidats
par exemple pour ligne = 0 et colonne = 1, devrait renvoyer [4, 9]
'''
def solve(grille:list):
'''
parcourt la grille à la recherche de case vides
pour chaque case vide, regarde les candidats possibles,
s'il n'y en a qu'un seul, écrit ce candidat dans la case.
Chaque fois qu'on a pu écrire une valeur dans la grille, on prévoit
un nouveau parcours complet de grille.
On s'arrête si la grille est pleine ou si on l'a parcouru entièrement sans pouvoir rien ajouter.
'''
À faire
- Réaliser l'implémentation.
- Bien documenter les fonctions
- prévoir au moins un exemple de résolution
J'ai vu de nombreuses fois des élèves utilisant une méthode toute faite à base de fonction récursive et à laquelle ils ne comprenaient pas grand chose…
Cette méthode est interdite pour ce projet : pas de fonction récursive.