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). Utilisez0
ou laissez les cellules vides pour les cases vides du puzzle. - Exécutez la macro en appuyant sur
Alt + F8
, sélectionnezSolveSudoku
et cliquez surExé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.