Sudoku
Professeurs référents :
M FAURY (ISN)
Objectif:
Créer un solveur de Sudoku à partir d’une photo qu’un logiciel a décrypté.
Cahier des charges
Production finale attendue : Avoir un sudoku résolu
Il faut que ce soit lisible afin de pouvoir remplir la grille de sudoku papier
On utilise le langage python pour coder: Winpython, Pyzo ,…
Tâches à réaliser
Élève 1 : Baptiste Denoue |
Élève 2 : Baptiste Esposito |
|
A partir de l’image décrypté, coder un algorithme afin qu’il lise la grille et qu’il résolve le sudoku en remplaçant les caractères | ||
On a déduit que les cases vides devront être marqués par un zéro pour qu’on puisse les remplacer plus facilement.
Il faut créer des fonctions qui vérifient des conditions pour qu’on puisse remplir les cases vides pour que la grille soit correcte à la fin.
|
Cheminement du projet
Pour la partie du solveur :
-La liste va être constituée de 9 sous listes qui constituera une ligne de sudoku chacune.
-l’affichage doit se faire en découpant les lignes, les colonnes et les blocs tous les 3 chiffres pour qu’on ait une ressemblance avec une vraie grille de sudoku.
-On a une fonction qui va devoir vérifier si la case, dans laquelle on travaille, est déjà remplie ou pas. Si elle est vide alors on essaye des chiffres de 1 à 9 et on appelle des fonctions de vérification pour avoir les bonnes valeurs dans les bonnes cases.
Ce qu’on doit comprendre
Pour la partie du solveur:
Le fonctionnement de l’algorithme ici est appelé « Back-Tracking ». Il consiste à faire des retours en arrière afin de tester toutes les possibilités et de trouver la solution qui permet de remplir la grille sans erreur. Cette technique permet donc de ne pas s’arrêter à la première erreur, et donc de repartir un peu en arrière pour tester d’autres possibilités
Code de Résolution
[reveal heading= »%image% Afficher le code complet »]# Une échelle de Richter pour les grilles de sudoku (grille considérée comme la plus difficile au monde) : http://passeurdesciences.blog.lemonde.fr/2012/08/12/une-echelle-de-richter-pour-les-grilles-de-sudoku/ #grille=[[0,0,0,0,0,0,0,1,2],[0,0,0,0,0,0,0,0,3],[0,0,2,3,0,0,4,0,0],[0,0,1,8,0,0,0,0,5],[0,6,0,0,7,0,8,0,0],[0,0,0,0,0,9,0,0,0],[0,0,8,5,0,0,0,0,0],[9,0,0,0,4,0,5,0,0],[4,7,0,0,0,6,0,0,0]] # Une grille difficile #grille=[[9,0,0,1,0,0,0,0,5],[0,0,5,0,9,0,2,0,1],[8,0,0,0,4,0,0,0,0],[0,0,0,0,8,0,0,0,0],[0,0,0,7,0,0,0,0,0],[0,0,0,0,2,6,0,0,9],[2,0,0,3,0,0,0,0,6],[0,0,0,2,0,0,9,0,0],[0,0,1,9,0,4,5,7,0]] # Une grille facile grille=[[0,0,0,4,0,0,0,9,2],[0,0,1,0,5,9,0,8,0],[0,0,0,6,0,7,0,0,0],[0,3,0,0,0,0,6,7,0],[0,0,6,8,0,4,5,0,0],[0,9,4,0,0,0,0,1,0],[0,0,0,1,0,2,0,0,0],[0,5,0,9,8,0,3,0,0],[2,1,0,0,0,5,0,0,0]] # La grille vide #grille=[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]] iteration = 0 # pour compter le nombre d'appels à la fonction estvalide test = 0 # pour compter le nombre chiffres testés lors de la résolution def affichage(grille): # Fonction qui affiche la grille comme un sudoku réel dans la console for l in range(9): lig = "" for c in range(9) : lig += str(grille[l][c]) if (c+1)%3 ==0: lig += " " print(lig) if 0==(l+1)%3: print("------------------") #k=chiffre a placer , grille=grille qu'on va changer, l= ligne concernée, c= colonne concernée def absentsurligne(k, grille, l): # Fonction qui vérifie si le chiffre 'k' est deja présent sur la ligne for c in range(9): if grille[l][c] == k: return False return True def absentsurcolonne(k, grille, c): # Fonction qui vérifie si le chiffre 'k' est deja présent sur la colonne for l in range(9): if grille[l][c] == k: return False return True def absentsurbloc(k , grille , l , c): # Fonction qui vérifie si le chiffre 'k' est deja présent sur le bloc _l = l-(l%3) _c = c-(c%3) for c in range(_c,_c+3): for l in range(_l,_l+3): if grille[l][c] == k: return False return True def estvalide(grille , position): # Fonction qui vérifie si on doit modifier la case, la case est défini avec le paramètre position qui s'agrémente de 1 à chaque fois global test global iteration iteration = iteration+1 if position == 9*9: return True l = position//9 c = position%9 if grille[l][c] != 0: return estvalide(grille , position+1) else: for k in range(1,10): test = test+1 if absentsurligne(k,grille,l) \ and absentsurcolonne(k,grille,c) \ and absentsurbloc(k,grille,l,c): grille[l][c] = k if estvalide(grille,position+1): return True grille[l][c] = 0 return False #grille=[[9,0,0,1,0,0,0,0,5],[0,0,5,0,9,0,2,0,1],[8,0,0,0,4,0,0,0,0],[0,0,0,0,8,0,0,0,0],[0,0,0,7,0,0,0,0,0],[0,0,0,0,2,6,0,0,9],[2,0,0,3,0,0,0,0,6],[0,0,0,2,0,0,9,0,0],[0,0,1,9,0,4,5,7,0]] print("Grille avant\n") # C'st la partie du programme qui appelle les fonctions affichages et estvalide affichage(grille) estvalide(grille,0) print("Grille apres\n") affichage(grille) print("\nNombre d'appels à la fonction estvalide : ") print(iteration) print("\nNombre de chiffres testés lors de la résolution : ") print(test)
[/reveal]
Fichiers du projet
- Ajouter un(des) fichier(s) puis cliquer sur Téléverser.
- Rafraichir la page pour vérifier que le dépôt a bien eu lieu.