Créer un solveur de Sudoku, Excel VBA

Créer un solveur de Sudoku, Excel VBA

Voici un guide détaillé pour créer un solveur de Sudoku en utilisant Excel VBA. Le solveur résout le puzzle en utilisant l’algorithme de backtracking (retour arrière), qui essaie différents nombres dans les cases vides et revient en arrière si un état invalide est atteint.
Aperçu :
Le Sudoku est un puzzle de 9×9 cases où certaines cellules sont déjà remplies avec des chiffres, et d’autres sont vides (représentées par des zéros ou des cases vides). Le solveur essaie de remplir les cases vides en respectant les règles suivantes :
1. Chaque ligne doit contenir les chiffres de 1 à 9 sans répétition.
2. Chaque colonne doit contenir les chiffres de 1 à 9 sans répétition.
3. Chaque sous-grille 3×3 doit contenir les chiffres de 1 à 9 sans répétition.
Le code VBA utilise un algorithme de backtracking pour résoudre le puzzle.
Étapes pour implémenter le Solveur de Sudoku en VBA :
1. Préparer la feuille de calcul
Dans votre feuille Excel, créez une grille 9×9 où le puzzle Sudoku sera affiché. Vous pouvez représenter le puzzle à l’aide d’une plage comme A1:I9, où chaque cellule correspond à un chiffre du puzzle.
2. Ouvrir l’éditeur VBA
Appuyez sur Alt + F11 pour ouvrir l’éditeur Visual Basic for Applications (VBA). Dans l’éditeur, allez dans Insertion → Module pour créer un nouveau module dans lequel vous allez coller le code VBA.
3. Code VBA pour le solveur de Sudoku
Voici le code détaillé en VBA pour le Solveur de Sudoku utilisant un algorithme de backtracking :

Sub SolveSudoku()
    ' Définir les variables
    Dim sudoku(1 To 9, 1 To 9) As Integer
    Dim row As Integer, col As Integer
    Dim i As Integer, j As Integer
    ' Lire le puzzle Sudoku depuis la feuille de calcul dans le tableau sudoku
    For row = 1 To 9
        For col = 1 To 9
            sudoku(row, col) = Cells(row, col).Value
        Next col
    Next row
    ' Appeler la fonction de résolution récursive
    If Solve(sudoku) Then
        ' Écrire le puzzle résolu dans la feuille de calcul
        For row = 1 To 9
            For col = 1 To 9
                Cells(row, col).Value = sudoku(row, col)
            Next col
        Next row
        MsgBox "Sudoku Résolu !"
    Else
        MsgBox "Aucune solution n'existe."
    End If
End Sub
Function Solve(ByRef sudoku() As Integer) As Boolean
    ' Cette fonction tente de résoudre le Sudoku en utilisant l'algorithme de backtracking
    Dim row As Integer, col As Integer
    Dim num As Integer
    ' Trouver la prochaine case vide (0 représente une case vide)
    If Not FindEmptyCell(sudoku, row, col) Then
        ' Aucune case vide trouvée, puzzle résolu
        Solve = True
        Exit Function
    End If
    ' Essayer tous les chiffres de 1 à 9
    For num = 1 To 9
        ' Vérifier si le chiffre est valide pour cette case
        If IsValid(sudoku, row, col, num) Then
            ' Assigner le chiffre à la case
            sudoku(row, col) = num
            ' Tenter de résoudre récursivement le reste du puzzle
            If Solve(sudoku) Then
                Solve = True
                Exit Function
            End If
            ' Faire marche arrière si aucune solution n'a été trouvée
            sudoku(row, col) = 0
        End If
    Next num
    ' Aucune solution valide trouvée, faire marche arrière
    Solve = False
End Function
Function FindEmptyCell(ByRef sudoku() As Integer, ByRef row As Integer, ByRef col As Integer) As Boolean
    ' Cette fonction trouve la prochaine case vide dans le puzzle Sudoku (représentée par 0)
    For row = 1 To 9
        For col = 1 To 9
            If sudoku(row, col) = 0 Then
                FindEmptyCell = True
                Exit Function
            End If
        Next col
    Next row
    FindEmptyCell = False
End Function
Function IsValid(ByRef sudoku() As Integer, row As Integer, col As Integer, num As Integer) As Boolean
    ' Cette fonction vérifie si un chiffre est valide pour une case donnée (ligne, colonne) dans le puzzle Sudoku
    ' Vérifier si le chiffre existe déjà dans la ligne
    Dim i As Integer
    For i = 1 To 9
        If sudoku(row, i) = num Then
            IsValid = False
            Exit Function
        End If
    Next i
    ' Vérifier si le chiffre existe déjà dans la colonne
    For i = 1 To 9
        If sudoku(i, col) = num Then
            IsValid = False
            Exit Function
        End If
    Next i
    ' Vérifier si le chiffre existe déjà dans la sous-grille 3x3
    Dim startRow As Integer, startCol As Integer
    startRow = Int((row - 1) / 3) * 3 + 1
    startCol = Int((col - 1) / 3) * 3 + 1
    For i = startRow To startRow + 2
        For j = startCol To startCol + 2
            If sudoku(i, j) = num Then
                IsValid = False
                Exit Function
            End If
        Next j
    Next i
    ' Le chiffre est valide s'il n'est pas dans la ligne, la colonne ou la sous-grille
    IsValid = True
End Function

4. Explication du code :
1. Sub SolveSudoku : C’est la principale macro qui lit le puzzle Sudoku depuis la feuille Excel, appelle la fonction récursive Solve, puis écrit le puzzle résolu dans la feuille de calcul.
2. Function Solve : Cette fonction utilise l’algorithme de backtracking pour résoudre le puzzle. Elle essaie de remplir les cases vides une par une en plaçant les chiffres de 1 à 9 et vérifie si chaque chiffre est valide. Si un chiffre mène à un état invalide, la fonction revient en arrière et essaie un autre chiffre.
3. Function FindEmptyCell : Cette fonction recherche la prochaine case vide (représentée par 0) dans le puzzle. Elle retourne True si une case vide est trouvée et False si le puzzle est complet.
4. Function IsValid : Cette fonction vérifie si un chiffre donné est valide pour une cellule particulière (ligne, colonne) dans le puzzle Sudoku. Elle vérifie les trois contraintes du Sudoku : pas de répétition dans la ligne, la colonne, et la sous-grille 3×3.
5. Utilisation du Solveur :

• Entrez votre puzzle Sudoku dans la plage A1:I9 (grille 9×9). Utilisez 0 ou laissez les cellules vides pour les cases vides du puzzle.
• Exécutez la macro en appuyant sur Alt + F8, sélectionnez SolveSudoku et cliquez sur Exécuter.
• Le solveur remplira la grille et affichera un message indiquant si le puzzle est résolu ou si aucune solution n’existe.

6. Gestion des cas particuliers :

• Si le puzzle n’a pas de solution (par exemple, en raison d’une configuration initiale invalide), le solveur affichera un message indiquant « Aucune solution n’existe. »
• Assurez-vous que le puzzle d’entrée respecte les règles de base du Sudoku pour éviter les incohérences ou les états invalides.

Conclusion :
Ce code utilise l’algorithme de backtracking, une méthode courante pour résoudre les problèmes de satisfaction de contraintes comme le Sudoku. Il tente systématiquement des solutions possibles, revient en arrière lorsqu’il rencontre un état invalide, et continue jusqu’à ce qu’il trouve une solution valide ou conclut qu’il n’y a pas de solution.