Résolveur de Sudoku complet et efficace

Présentation

Images

Sudoku solver

Sudoku solver : La grille la plus dure de sudoku Résout même "The hardest Sudoku Grid !" (2ème image)

Description

Ce code illustre une nouvelle fois la récursivité.
Il se charge de calculer tous les sudoku possibles selon ce que vous lui donnez en entrée.
Si vous ne lui donnez rien (en laissant toutes les cases vides), il se "contentera" de vous sortir toutes les grilles de sudoku existantes (oui oui, les 6'670'903'752'021'072'936'960. grilles possibles !

Enfin, soyons franc, votre PC risque fortement d'être à court de mémoire avant que vous n'en voyez la couleur !

Le tout tient en moins de 80 lignes de code... vive la récursivité (la source est abondamment détaillée).
En moyenne, il lui faut 0.2 secondes pour résoudre une grille diabolique...et il a résolu la grille "Near worst case" (la grille la plus complexe à résoudre) en moins de 5 minutes, là ou les autres algorithmes prennent en moyenne entre 30 et 45 minutes : (Wikipedia)

Based on the specific construction of the computer code, programmers have found the solution time for this puzzle to be between 30 and 45 minutes with a computer processor running at 3 GHz.

Je l'ai laissé tourner pendant une heure et demie sur mon PC, j'ai recu 2 000 000 de solutions...ce qui prend 1.52 Go de mémoire (il y a une option pour enregistrer les solutions dans un fichier).

Plus d'informations

La résolution d'une grille de Sudoku standard peut se concevoir de plusieurs façons, et la méthode itérative fait partie des solutions possibles.
Mais imaginons maintenant que l'on souhaite résoudre une grille qui peut posséder plus d'une solution. Ce n'est pas le cas des grilles de jeux données dans les magazines, mais cela peut être l'objet d'un petit défi mathématique.

Cette fois, la méthode itérative s'avère beaucoup plus lourde, voire ingérable : il faudrait utiliser une méthode de Brute-Force, et les résultats risqueraient de prendre beaucoup de temps pour sortir...examinons donc la méthode récursive, qui se révélera un petit peu plus fine, et qui ne demandera pas d'acheter un ordinateur Deep Blue 4 !

Prenons le raisonnement suivant :

Fonction Sudoku_Solver : reçoit une grille de sudoku
Si la grille est pleine, l'enregistrer
Sinon,
1. Trouver UNE case vide
2. Tester pour tous les chiffres de 1 à 9 :
  1. Si le chiffre testé est envisageable pour la case vide choisie, placer le chiffre sur la grille à cet emplacement. Envoyer la grille à la fonction Sudoku_Solver
3. Si aucun chiffre n'est envisageable pour cette position, c'est que la grille est incorrecte. Ce n'est pas grave : cette branche de la récursivité s'arrêtera ici.
Arrêter la fonction

A chaque itération, la grille se remplit d'une case. (Comme on teste pour tous les nombres de 1 à 9, on est sur qu'au moins une des grilles contient la bonne réponse...si la bonne réponse existe)

On peut voir cet algorithme de résolution comme un arbre : à chaque passage, on rajoute quelques branches. Si aucune solution n'est possible, la grille est fausse : la branche n'engendre pas d'enfants, et meurt donc.

On peut remarquer que si on envoie à la fonction Sudoku_Solver une grille complètement vide, on peut en théorie obtenir toutes les grilles de Sudoku du monde. Cependant, au vu du nombre de possibilités (6 670 903 752 021 072 936 960) et des défauts de l'algorithme listés ci-dessous, il faudrait un ordinateur disposant d'une énorme quantité de mémoire vive.

Un article détaillé a été écrit couvrant les tenants et aboutissants de la méthode récursive par rapport à la méthode itérative : À propos de la récursivité

Téléchargement

Version Zippée : EXE + Code source

Version EXE

EXE
VB6FR.dll : à placer dans le même dossier que le fichier EXE

Code source

La feuille :

Code source : Form1.frm

Langage : VB
Taille : 529 caractï¿½res

Option Explicit



Private Sub Chercher_Click()

'Lancer la recherche des solutions

LancerRecherche

End Sub



Private Sub ChiffreSudoku_Change(Index As Integer)

'Quand on rentre un nouveau nombre, donner le focus au chap suivant.

If Not (IsNumeric(ChiffreSudoku(Index).Text)) Then

    ChiffreSudoku(Index).Text = vbNullString

ElseIf Index <> 80 Then

    ChiffreSudoku(Index + 1).SetFocus

End If

End Sub





Private Sub Form_Resize()

If Me.WindowState <> vbMinimized Then Solution.Height = Me.Height - 700

End Sub

Les modules :

Code source : Solver.bas

Langage : VB
Taille : 5690 caractï¿½res

Option Explicit



Private NBIterations As Long, Termine As Boolean, AfficherToutesSoluces As Boolean, Debut As Long, NBSolutions As Long, EnregistrerDansFichier As Boolean





Private Sub AfficherSolution(Texte As String, Grille_A_Afficher() As Long)

'Affiche une grille passé en paramètre, avec le Texte.

Dim i As Long, j As Long, Texte_A_Afficher As String

Texte_A_Afficher = vbCrLf



'Faire une boucle sur toute la grille, rajouter des éléments permettants une lecture plus intuitive

For i = 1 To 10

    If (i - 1) Mod 3 = 0 Then Texte_A_Afficher = Texte_A_Afficher & "|---|---|---|" & vbCrLf

    If i = 10 Then Exit For

    For j = 1 To 9

        If (j - 1) Mod 3 = 0 Then Texte_A_Afficher = Texte_A_Afficher & "|"

        Texte_A_Afficher = Texte_A_Afficher & Grille_A_Afficher(i, j)

    Next

    Texte_A_Afficher = Texte_A_Afficher & "|" & vbCrLf

Next



'L'ajouter à la suite des calculs préexistants

Form1.Solution.Text = Texte & vbCrLf & Texte_A_Afficher & vbCrLf & Form1.Solution.Text

'L'enregistrer dans le fichier si nécessaire:

If EnregistrerDansFichier Then Print #1, Texte & vbCrLf & Texte_A_Afficher & vbCrLf

End Sub



Public Function LancerRecherche()

    'Lance la recherche en fonction des paramètres passés à l'interface graphique.

    Debut = Timer

    NBSolutions = 0

    'Transformer les textbox en données utilisables

    Dim GrilleDepart(1 To 9, 1 To 9) As Long

    Dim i As Long

    For i = 0 To 80

        GrilleDepart(1 + i \ 9, 1 + i Mod 9) = IIf(Form1.ChiffreSudoku(i).Text = vbNullString, 0, Form1.ChiffreSudoku(i).Text)

    Next

    

    'Puis initialiser les variables de Statistiques, qui garderont en méoire le nombre de grilles trouvées, testées...

    NBIterations = 0

    Termine = False

    AfficherToutesSoluces = Form1.AfficherTous.Value

    Form1.Solution = vbNullString

    EnregistrerDansFichier = Form1.SaveInFile.Value

    If EnregistrerDansFichier Then Open App.Path & "\Sudoku_Soluces.txt" For Output As #1

    AfficherSolution "Grille de départ :", GrilleDepart()

    Solver GrilleDepart

    

End Function





Private Sub Solver(Grille_A_Solver() As Long)

    'Fonction récursive principale : elle prend en paramètre une grille et cherche à la remplir.

    'L'idée de base est d eprocéder par petits pas :

    'Cette fonction cherche UN emplacement vide.

    'Si elle n'en trouve pas, la grille passé en paramètre est déjà complète : parfaite.

    'Si elle en trouve un, elle essaie successivement d'y placer les nombres de 1 à 9. Si elle peut placer par exemple un 1, elle s'auto appelle alors avec une grille un peu moins vide.

    'De proche en proche, on obtien finalement une grille parfaitement remplie..et seules les combinaisons qui ont une probabilité d'être vraies sont testées.

    

    'Pour un très bon tutorial sur la récursivité : (sous formes d'algorithmes)

    'http://www.siteduzero.com/tuto-3-23774-1-la-recursivite.html

    

    

    Dim i As Long, j As Long, k As Long, Case_Etait_Vide As Boolean

    

    'Si on a une solution et que l'on en a demandé une seule, c'est terminé !

    If Termine And Not (AfficherToutesSoluces) Then Exit Sub

    NBIterations = NBIterations + 1

    

    'i,j => parcourent le tableau

    'k parcourt les nombres de 1 à 9

    'Case_Etait_Vide indique si on a effectué une opération sur le tableau

    Case_Etait_Vide = False

    For i = 1 To 9

        For j = 1 To 9

            If Grille_A_Solver(i, j) = 0 Then

                'C'est une case vide, on va tenter de la remplir

                For k = 1 To 9

                    If Try_To_Add(Grille_A_Solver, k, i, j) Then 'Si on a le droit d eplace k à l'emplacement i,j

                        'Remplir la grille avec ce nombre, et la passer en paramètre à Grille_A_Solver.

                        Grille_A_Solver(i, j) = k

                        Solver Grille_A_Solver()

                        'Puis la remettre à zéro pour la suite.

                        Grille_A_Solver(i, j) = 0

                    End If

                Next

                Case_Etait_Vide = True: Exit For

            End If

        Next

        If Case_Etait_Vide Then Exit For

    Next

    

    'Si on a jamais trouvé de case vide, c'est fini !

    If Case_Etait_Vide = False Then

        NBSolutions = NBSolutions + 1

        AfficherSolution "TERMINE !!!! (Delta T = " & Int((Timer - Debut) * 100) / 100 & "s - Solution n°" & NBSolutions & ", cas traités : " & NBIterations & ")", Grille_A_Solver

        Termine = True

        DoEvents

    End If

    'Debug.Print NBIterations

    

End Sub





Private Function Try_To_Add(Grille() As Long, Nombre As Long, coord_x As Long, coord_y As Long) As Boolean

'Cette fonction renvoie un boolean :

'TRUE si Nombre peut être inséré dans Grille() a l'emplacement (coord_x,coord_y), selon les régles classiques du sudoku : une seule fois le même

'nombre par ligne, par colonne et par carré.

'FALSE si les règles du sudoku interdisent la présence de ce nombre à cet emplacement.



Dim i As Long, Invalide As Boolean, CarreStartX As Long, CarreStartY As Long

'Trouver les coordonnées d ebase du carré dans lequel l'emplacement se situe.

CarreStartX = 1 + 3 * Int((coord_x - 1) / 3)

CarreStartY = 1 + 3 * Int((coord_y - 1) / 3)

Invalide = False

'Tester les 9 nombres : si un seul n'est pas possible, sortir d ela boucle en mettant Invalide à True.

For i = 1 To 9

    If Grille(i, coord_y) = Nombre Or Grille(coord_x, i) = Nombre Or Grille(CarreStartX + (i - 1) \ 3, CarreStartY + (i Mod 3)) = Nombre Then

        Invalide = True

        Exit For

    End If

Next

Try_To_Add = Not (Invalide)

End Function