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.