Résolution de Sudoku par Recuit Simulé

Navigation : Index | << Sudoku-03-Genetic | Sudoku-08-HumanStrategies >>

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Formuler la résolution de Sudoku comme un problème d’optimisation (minimisation d’une fonction d’énergie) 2. Définir une fonction d’énergie comptant les violations de contraintes 3. Construire un voisinage par échange de cellules dans une même ligne 4. Implémenter un solveur par recuit simulé (Simulated Annealing) en C# 5. Analyser les forces et limites du recuit simulé pour le Sudoku

Prérequis

Notebook Sudoku-0-Environment : classes de base (SudokuGrid, ISudokuSolver, SudokuHelper)
Notions de base en optimisation et recherche locale

Voir aussi

Théorie : Search-04-LocalSearch - Hill Climbing, Recuit Simulé, Tabu Search
Version Python : Sudoku-Python-SimulatedAnnealing

Durée estimée : ~40 minutes

1. Introduction (~3 min)

Le Sudoku comme problème d’optimisation

Contrairement aux solveurs par backtracking ou par satisfaction de contraintes (OR-Tools, Z3) qui construisent progressivement une solution partielle, le recuit simulé (Simulated Annealing, SA) adopte une approche radicalement différente :

Approche	Espace de recherche	Principe
Backtracking	États partiels (cellules vides)	Construction incrémentale
CSP (OR-Tools, Z3)	États partiels avec propagation	Réduction de domaine
Algorithme génétique	Population d’états complets	Evolution par sélection
Recuit simulé	Un seul état complet	Perturbation locale avec acceptation probabiliste

Le recuit simulé s’inspire du processus metallurgique de recuit : un metal est chauffe puis refroidi lentement pour atteindre un état cristallin optimal. Transpose a l’optimisation :

L’état est une grille entierement remplie (potentiellement avec des erreurs)
L’énergie mesure le nombre de violations de contraintes
La température contrôle l’acceptation de mouvements dégradants
Le refroidissement reduit progressivement la température, passant de l’exploration a l’exploitation

Formulation

On cherche a minimiser la fonction d’énergie :

\[E(\text{grille}) = \sum_{\text{colonnes}} \text{doublons} + \sum_{\text{blocs}} \text{doublons}\]

La solution est trouvee quand \(E = 0\).

Critere d’acceptation de Metropolis

A chaque itération, on génère un voisin et on decide de l’accepter selon :

\[P(\text{accepter}) = \begin{cases} 1 & \text{si } \Delta E \leq 0 \text{ (amélioration)} \\ e^{-\Delta E / T} & \text{si } \Delta E > 0 \text{ (dégradation)} \end{cases}\]

ou \(\Delta E = E(\text{voisin}) - E(\text{courant})\) et \(T\) est la température courante.

Sources primaires. Le critere d’acceptation de Metropolis – accepter une dégradation avec probabilité \(e^{-\Delta E/T}\) – a ete introduit dans l’étude des equations d’état par simulation de Monte-Carlo (Metropolis, Rosenbluth, Rosenbluth, Teller & Teller, Journal of Chemical Physics 21(6):1087-1092, 1953). Son transfert a l’optimisation combinatoire sous le nom de recuit simulé est l’apport fondateur de Kirkpatrick, Gelatt & Vecchi, Science 220(4598):671-680, 1983.

2. Importation de l’environnement

Nous importons les classes de base définies dans le notebook d’environnement : SudokuGrid, ISudokuSolver, SudokuHelper.

#!import Sudoku-00-Environment-CSharp.ipynb

Sudoku-00 : Environnement et Classes de Base (C#)

Navigation : Index | Sudoku-01 Backtracking C# >>

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Comprendre la structure de données SudokuGrid et ses méthodes principales 2. Utiliser ISudokuSolver pour implémenter un solveur de Sudoku 3. Exploiter SudokuHelper pour charger des grilles et tester des solveurs 4. Comparer les performances de plusieurs solveurs sur différentes difficultés

Prérequis : Notions de base en C# (.NET Interactive)
Durée estimée : ~15 min

Installing Packages

Plotly.NET

Définition de la classe SudokuGrid

Nous définissons ici la classe SudokuGrid qui représente une grille de Sudoku et fournit des méthodes pour manipuler et afficher les grilles.

SudokuGrid defini.

Interprétation : Structure de données pour la grille Sudoku

Sortie obtenue : La classe SudokuGrid encapsule toutes les opérations de manipulation, validation et affichage d’une grille de Sudoku 9x9.

Aspect	Valeur	Signification
`Cells[9,9]`	int[,]	Stockage interne des valeurs (0 = vide)
`AllNeighbours`	27 x 9 positions	Pré-calcul des voisins ligne/colonne/bloc
`CellNeighbours[9][9]`	~20 positions chacune	Voisins directs de chaque cellule
`GetAvailableNumbers()`	int[]	Candidats valides pour une cellule
`NbErrors()`	int	Nombre de conflits + modifications erronées

Points clés : 1. Pré-calcul des voisins : AllNeighbours et CellNeighbours sont calculés une seule fois à l’initialisation, évitant les recalculs coûteux 2. Conversion flexible : Méthodes pour convertir entre tableaux 1D, 2D et jagged arrays (utile pour différents formats de fichiers) 3. Validation robuste : NbErrors compte à la fois les doublons (ligne/colonne/bloc) et les modifications de indices pré-remplis 4. Parsing tolerant : ReadMultiSudoku accepte plusieurs formats (., X, -, espaces)

Note technique : La structure CellNeighbours[i][j] contient environ 20 positions (8 ligne + 8 colonne + 4 bloc, moins les doublons). Ce pré-calcul est crucial pour les performances des algorithmes de backtracking et de propagation de contraintes.

Définition de l’interface ISudokuSolver

Nous définissons ici l’interface ISudokuSolver qui sera implémentée par les différentes stratégies de résolution de Sudoku.

ISudokuSolver defini.

Interprétation : Interface de stratégie

Sortie obtenue : L’interface ISudokuSolver définit le contrat que tous les solveurs doivent respecter.

Aspect	Valeur	Signification
`Solve(SudokuGrid)`	SudokuGrid	Méthode unique de résolution
Pattern	Stratégie	Permuter les algorithmes sans modifier le code client

Points clés : 1. Simplicité : Une seule méthode Solve prenant une grille et retournant une grille résolue 2. Flexibilité : N’importe quel algorithme (backtracking, CSP, métaheuristique) peut implémenter cette interface 3. Composabilité : Les solveurs peuvent être passés en paramètre, stockés dans des listes, testés unitairement 4. Extensibilité : Ajouter un nouveau solver ne nécessite que d’implémenter l’interface

Note technique : Ce design pattern permet à SudokuHelper.TestSolvers d’accepter une liste de (string, ISudokuSolver) pour comparer tous les algorithmes avec le même code de test.

Définition de la classe SudokuHelper

Nous ajoutons ici la classe SudokuHelper qui contient des méthodes utilitaires pour charger des grilles de Sudoku et tester des solvers.

GetSudokus : Renvoie des listes de Sudoku issues de fichiers de 3 difficultés différentes.
SolveSudoku : effectue un test simple d’un solver sur un sudoku donné.
TestSolvers : exécute les tests de performance sur plusieurs solveurs.
DisplayResults : affiche les résultats des tests sous forme de graphiques.

SudokuHelper defini.

Interprétation : Infrastructure de test et benchmark

Sortie obtenue : La classe SudokuHelper fournit une infrastructure complète pour tester et comparer les solveurs de Sudoku.

Aspect	Valeur	Signification
`GetSudokus()`	51/95/100 grilles	Trois niveaux de difficulté (Easy/Medium/Hard)
`TestSolvers()`	Performance multi-solveurs	Exécution parallèle avec timeout
`DisplayResults()`	Graphiques SVG inline (SvgChartHelper)	Comparaison des temps par difficulté, sérialisée dans le notebook
`SolveSudoku()`	Test unitaire	Résolution individuelle avec affichage

Points clés : 1. Chargement intelligent : Recherche récursive du dossier Puzzles dans l’arborescence 2. Robustesse : Gestion des timeouts (3 000 ms par défaut — paramètre de configuration du solveur, valeur fixée dans le code) et exceptions 3. Mesures : Temps d’exécution total + nombre de grilles resolues 4. Disqualification : Un solver échouant sur une grille est disqualifié pour la difficulté

Note technique : La méthode TestSolvers utilise Interlocked.Increment pour un thread-safe incrément du compteur de solutions. Le CancellationToken permet d’interrompre proprement les solveurs trop lents.

Exercice : Validation d’une grille Sudoku

Énoncé

Implémentez une méthode IsValidSolution qui vérifie qu’une grille est une solution valide de Sudoku, c’est-à-dire que chaque ligne, chaque colonne et chaque bloc 3x3 contient exactement une fois chaque chiffre de 1 à 9.

Utilisez cette méthode pour valider les résultats de SudokuHelper.SolveSudoku.

Indices :

Parcourez les 9 lignes, 9 colonnes et 9 blocs
Pour chaque unité, verifiez que les 9 chiffres sont tous présents sans doublon
SudokuGrid.AllNeighbours contient déjà les indices des unités

Exercice a completer

Résumé et perspectives

Ce notebook a posé les fondations de toute la série Sudoku en définissant trois composants essentiels. La classe SudokuGrid encapsule la représentation d’une grille 9x9 avec le pré-calcul des voisins (AllNeighbours, CellNeighbours), ce qui évite les recalculs coûteux lors de la résolution. L’interface ISudokuSolver implante le pattern Stratégie, permettant de permuter les algorithmes de résolution sans modifier le code client. Enfin, la classe SudokuHelper fournit une infrastructure de benchmark complète avec chargement de puzzles, mesures de performance et visualisation SVG inline (SvgChartHelper, zéro dépendance).

L’infrastructure de test (TestSolvers, DisplayResults) permet de comparer objectivement les solveurs sur trois niveaux de difficulté (Easy, Medium, Hard) avec gestion des timeouts et des disqualifications. Ce cadre de benchmark sera utilisé dans tous les notebooks suivants pour mesurer les performances de chaque algorithme.

Le notebook suivant, Sudoku-01-Backtracking, utilise ces classes pour implémenter le premier algorithme de résolution : le backtracking récursif avec ses heuristiques d’amélioration.

Import du solver de backtracking pour comparaison de performance.

#!import Sudoku-01-Backtracking-CSharp.ipynb

Sudoku-01 : Résolution par Backtracking

Navigation : << Sudoku-00 Environment | Index | Sudoku-03 Genetic >>

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Implémenter un algorithme de backtracking pour résoudre le Sudoku 2. Comprendre l’exploration en profondeur et le retour arrière 3. Analyser les performances du backtracking selon la difficulté des puzzles

Durée estimée : ~7 min | Prérequis : Sudoku-00 Environment | Lien : Voir CSP-1-Fondamentaux pour la théorie du backtracking

Introduction Théorique

L’algorithme de backtracking est une méthode de recherche en profondeur utilisée pour résoudre les problèmes de satisfaction de contraintes (CSP), comme le Sudoku. L’algorithme explore toutes les configurations possibles pour trouver une solution qui respecte les contraintes :

Exploration en profondeur : L’algorithme explore chaque possibilité de manière exhaustive avant de revenir en arrière (backtrack) lorsque aucune solution n’est trouvée dans une branche particulière.
Contraintes : Dans le cas du Sudoku, les contraintes sont les règles du jeu : chaque chiffre de 1 à 9 doit apparaître une seule fois par ligne, colonne et sous-grille de 3x3.

Implémentation de l’Algorithme de Backtracking

L’algorithme suit ces étapes : 1. Trouver une case vide dans la grille. 2. Tenter de placer un chiffre (1-9) dans la case vide. 3. Vérifier si ce chiffre respecte les contraintes. 4. Si oui, passer a la case suivante et répéter le processus. 5. Si non, essayer le chiffre suivant. 6. Si aucun chiffre ne convient, revenir en arrière (backtrack).

Importation des Classes de Base

Sudoku-00 : Environnement et Classes de Base (C#)

Navigation : Index | Sudoku-01 Backtracking C# >>

Objectifs d’apprentissage

Prérequis : Notions de base en C# (.NET Interactive)
Durée estimée : ~15 min

Installing Packages

Plotly.NET

Définition de la classe SudokuGrid

Nous définissons ici la classe SudokuGrid qui représente une grille de Sudoku et fournit des méthodes pour manipuler et afficher les grilles.

SudokuGrid defini.

Interprétation : Structure de données pour la grille Sudoku

Sortie obtenue : La classe SudokuGrid encapsule toutes les opérations de manipulation, validation et affichage d’une grille de Sudoku 9x9.

Aspect	Valeur	Signification
`Cells[9,9]`	int[,]	Stockage interne des valeurs (0 = vide)
`AllNeighbours`	27 x 9 positions	Pré-calcul des voisins ligne/colonne/bloc
`CellNeighbours[9][9]`	~20 positions chacune	Voisins directs de chaque cellule
`GetAvailableNumbers()`	int[]	Candidats valides pour une cellule
`NbErrors()`	int	Nombre de conflits + modifications erronées

Note technique : La structure CellNeighbours[i][j] contient environ 20 positions (8 ligne + 8 colonne + 4 bloc, moins les doublons). Ce pré-calcul est crucial pour les performances des algorithmes de backtracking et de propagation de contraintes.

Définition de l’interface ISudokuSolver

Nous définissons ici l’interface ISudokuSolver qui sera implémentée par les différentes stratégies de résolution de Sudoku.

ISudokuSolver defini.

Interprétation : Interface de stratégie

Sortie obtenue : L’interface ISudokuSolver définit le contrat que tous les solveurs doivent respecter.

Aspect	Valeur	Signification
`Solve(SudokuGrid)`	SudokuGrid	Méthode unique de résolution
Pattern	Stratégie	Permuter les algorithmes sans modifier le code client

Note technique : Ce design pattern permet à SudokuHelper.TestSolvers d’accepter une liste de (string, ISudokuSolver) pour comparer tous les algorithmes avec le même code de test.

Définition de la classe SudokuHelper

Nous ajoutons ici la classe SudokuHelper qui contient des méthodes utilitaires pour charger des grilles de Sudoku et tester des solvers.

GetSudokus : Renvoie des listes de Sudoku issues de fichiers de 3 difficultés différentes.
SolveSudoku : effectue un test simple d’un solver sur un sudoku donné.
TestSolvers : exécute les tests de performance sur plusieurs solveurs.
DisplayResults : affiche les résultats des tests sous forme de graphiques.

SudokuHelper defini.

Interprétation : Infrastructure de test et benchmark

Sortie obtenue : La classe SudokuHelper fournit une infrastructure complète pour tester et comparer les solveurs de Sudoku.

Aspect	Valeur	Signification
`GetSudokus()`	51/95/100 grilles	Trois niveaux de difficulté (Easy/Medium/Hard)
`TestSolvers()`	Performance multi-solveurs	Exécution parallèle avec timeout
`DisplayResults()`	Graphiques SVG inline (SvgChartHelper)	Comparaison des temps par difficulté, sérialisée dans le notebook
`SolveSudoku()`	Test unitaire	Résolution individuelle avec affichage

Note technique : La méthode TestSolvers utilise Interlocked.Increment pour un thread-safe incrément du compteur de solutions. Le CancellationToken permet d’interrompre proprement les solveurs trop lents.

Exercice : Validation d’une grille Sudoku

Énoncé

Utilisez cette méthode pour valider les résultats de SudokuHelper.SolveSudoku.

Indices :

Parcourez les 9 lignes, 9 colonnes et 9 blocs
Pour chaque unité, verifiez que les 9 chiffres sont tous présents sans doublon
SudokuGrid.AllNeighbours contient déjà les indices des unités

Exercice a completer

Résumé et perspectives

Le notebook suivant, Sudoku-01-Backtracking, utilise ces classes pour implémenter le premier algorithme de résolution : le backtracking récursif avec ses heuristiques d’amélioration.

Affichage des Puzzles de chaque Difficulté

Nous allons charger et afficher un puzzle de chaque niveau de difficulté : Facile, Moyen et Difficile.

Puzzle Facile:
-------------------------------
| 9     2 |       5 | 4     3 | 
| 1       |    6  3 |    2  5 | 
| 5     8 | 4     7 |    6    | 
-------------------------------
|    2  6 | 3     9 |       1 | 
|    5  7 |    1    | 2  9    | 
|    9    | 6  7    | 5  3    | 
-------------------------------
| 2  4    | 5  3    | 6       | 
| 7     5 | 2       | 3     4 | 
|    8    |    4  1 | 9  5    | 
-------------------------------

Puzzle Moyen:
-------------------------------
| 8  5    |       2 | 4       | 
| 7  2    |         |       9 | 
|       4 |         |         | 
-------------------------------
|         | 1     7 |       2 | 
| 3     5 |         | 9       | 
|    4    |         |         | 
-------------------------------
|         |    8    |    7    | 
|    1  7 |         |         | 
|         |    3  6 |    4    | 
-------------------------------

Puzzle Difficile:
-------------------------------
| 4       |         | 8     5 | 
|    3    |         |         | 
|         | 7       |         | 
-------------------------------
|    2    |         |    6    | 
|         |    8    | 4       | 
|         |    1    |         | 
-------------------------------
|         | 6     3 |    7    | 
| 5       | 2       |         | 
| 1     4 |         |         | 
-------------------------------

Interprétation : Structure des Puzzles Sudoku

Sortie obtenue : Trois puzzles de difficulté croissante ont été chargés et affichés. La différence de complexité se voit visuellement par le nombre de cases pré-remplies.

Difficulté	Cases vides (estimation)	Observation visuelle
Facile	~30-35	Plus de 50% des cases sont déjà remplies, beaucoup de contraintes visibles
Moyen	~45-50	Environ 50% de cases vides, structure moins évidente
Difficile	~55-60	Très peu de cases pré-remplies (environ 40%), contraintes minimales

Points clés : 1. Échantillonnage représentatif : La méthode GetSudokus().FirstOrDefault() retourne le premier puzzle disponible de chaque niveau, ce qui permet une comparaison consistante. 2. Corrélation difficulté/densité : Plus le puzzle a de cases vides, plus l’espace de recherche est grand et plus le backtracking devra explorer de combinaisons. 3. Règles du jeu respectees : Chaque puzzle respecte les contraintes du Sudoku (uniques chiffres 1-9 par ligne, colonne, bloc 3x3). 4. Preparation aux tests : Ces trois puzzles serviront de base pour évaluer les performances du solveur de backtracking.

Note technique : Les puzzles sont générés algorithmiquement pour garantir qu’ils ont exactement une solution unique. Cette propriété est cruciale pour évaluer la complétude de l’algorithme de backtracking.

Impact sur la performance : Le nombre de cases vides determine directement la taille de l’arbre de recherche du backtracking. Avec 60 cases vides, le pire cas théorique est 9^60 possibilités, mais les contraintes reduisent drastiquement ce nombre en pratique.

Code du solver en C

Nous allons maintenant implémenter ce solveur en C#.

Classe `BacktrackingDotNetSolver`

BacktrackingDotNetSolver class defined

Test du Solveur

Nous allons maintenant tester notre solveur de Sudoku par backtracking en utilisant une grille de Sudoku.

Exercice : Vérifier qu’une grille est valide

Objectif : Implémentez une méthode qui vérifie si une grille complètement remplie respecte toutes les contraintes du Sudoku (lignes, colonnes, blocs uniques).

Indice : Parcourez chaque ligne, colonne et bloc 3x3 et vérifiez que chaque ensemble contient exactement les chiffres 1 à 9 sans doublon.

Exercice a completer
Puzzle Sudoku Facile Initial:

Résolution par le solver BacktrackingDotNetSolver du Sudoku:
 -------------------------------
| 9     2 |       5 | 4     3 | 
| 1       |    6  3 |    2  5 | 
| 5     8 | 4     7 |    6    | 
-------------------------------
|    2  6 | 3     9 |       1 | 
|    5  7 |    1    | 2  9    | 
|    9    | 6  7    | 5  3    | 
-------------------------------
| 2  4    | 5  3    | 6       | 
| 7     5 | 2       | 3     4 | 
|    8    |    4  1 | 9  5    | 
-------------------------------

BacktrackingDotNetSolver: 122 search calls

Sudoku renvoyé:
-------------------------------
| 9  6  2 | 1  8  5 | 4  7  3 | 
| 1  7  4 | 9  6  3 | 8  2  5 | 
| 5  3  8 | 4  2  7 | 1  6  9 | 
-------------------------------
| 8  2  6 | 3  5  9 | 7  4  1 | 
| 3  5  7 | 8  1  4 | 2  9  6 | 
| 4  9  1 | 6  7  2 | 5  3  8 | 
-------------------------------
| 2  4  9 | 5  3  8 | 6  1  7 | 
| 7  1  5 | 2  9  6 | 3  8  4 | 
| 6  8  3 | 7  4  1 | 9  5  2 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 0,6231 ms

Puzzle Sudoku Moyen Initial:

Résolution par le solver BacktrackingDotNetSolver du Sudoku:
 -------------------------------
| 8  5    |       2 | 4       | 
| 7  2    |         |       9 | 
|       4 |         |         | 
-------------------------------
|         | 1     7 |       2 | 
| 3     5 |         | 9       | 
|    4    |         |         | 
-------------------------------
|         |    8    |    7    | 
|    1  7 |         |         | 
|         |    3  6 |    4    | 
-------------------------------

BacktrackingDotNetSolver: 490304 search calls

Sudoku renvoyé:
-------------------------------
| 8  5  9 | 6  1  2 | 4  3  7 | 
| 7  2  3 | 8  5  4 | 1  6  9 | 
| 1  6  4 | 3  7  9 | 5  2  8 | 
-------------------------------
| 9  8  6 | 1  4  7 | 3  5  2 | 
| 3  7  5 | 2  6  8 | 9  1  4 | 
| 2  4  1 | 5  9  3 | 7  8  6 | 
-------------------------------
| 4  3  2 | 9  8  1 | 6  7  5 | 
| 6  1  7 | 4  2  5 | 8  9  3 | 
| 5  9  8 | 7  3  6 | 2  4  1 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 192,6311 ms

Puzzle Sudoku Difficile Initial:

Résolution par le solver BacktrackingDotNetSolver du Sudoku:
 -------------------------------
| 4       |         | 8     5 | 
|    3    |         |         | 
|         | 7       |         | 
-------------------------------
|    2    |         |    6    | 
|         |    8    | 4       | 
|         |    1    |         | 
-------------------------------
|         | 6     3 |    7    | 
| 5       | 2       |         | 
| 1     4 |         |         | 
-------------------------------

BacktrackingDotNetSolver: 12625368 search calls

Sudoku renvoyé:
-------------------------------
| 4  1  7 | 3  6  9 | 8  2  5 | 
| 6  3  2 | 1  5  8 | 9  4  7 | 
| 9  5  8 | 7  2  4 | 3  1  6 | 
-------------------------------
| 8  2  5 | 4  3  7 | 1  6  9 | 
| 7  9  1 | 5  8  6 | 4  3  2 | 
| 3  4  6 | 9  1  2 | 7  5  8 | 
-------------------------------
| 2  8  9 | 6  4  3 | 5  7  1 | 
| 5  7  3 | 2  9  1 | 6  8  4 | 
| 1  6  4 | 8  7  5 | 2  9  3 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 6213,7329 ms

Interprétation : Performance du Backtracking

Sortie obtenue : Trois puzzles de difficulté croissante ont été résolus avec succès. Le nombre d’appels récursifs et le temps de résolution augmentent exponentiellement avec la difficulté.

Difficulté	Appels récursifs	Facteur d’augmentation
Facile	122	1x (reference)
Moyen	490 304	4 019x
Difficile	12 625 368	103 489x

Points clés : 1. Complexité exponentielle : Le nombre d’appels récursifs explose littéralement entre le puzzle facile (122 appels) et le puzzle difficile (12,6 millions d’appels). 2. Efficacité sur les puzzles simples : Le backtracking naïve est quasi instantané pour les puzzles faciles (122 appels seulement). 3. Limites sur les puzzles difficiles : Plus de 12 millions d’appels pour un puzzle difficile, peu compatible avec une application interactive. 4. Tous les puzzles résolus : L’algorithme trouve toujours une solution (complétude), mais le coût en temps varie énormément.

Note technique : Le temps de résolution n’est pas linéaire par rapport au nombre d’appels récursifs. Le puzzle difficile nécessite 25 fois plus d’appels que le puzzle moyen, et le surcoût temporel (non mesuré ici, machine-dépendant) s’explique par la gestion de la pile d’appels et des opérations de validation. Les temps d’horloge dérivent d’une machine à l’autre ; seuls les comptes d’appels sont reproductibles.

Comparaison avec la théorie : L’analyse des résultats confirme les propriétés théoriques du backtracking : - Complétude : Tous les puzzles sont résolus avec 0 erreurs restantes - Cout : Exponentiel dans le pire cas, mais acceptable pour les instances simples - Amélioration nécessaire : Les heuristiques (MRV, Forward Checking) sont indispensables pour les puzzles difficiles

Exercice : Comparer backtracking simple et MRV

Objectif : Comparez les performances du solveur simple et du solveur MRV sur des puzzles de différentes difficultés.

Indice : Utilisez un Stopwatch pour mesurer le temps et comptez les appels récursifs.

Exercice a completer

Exercice (guidé) : Backtracking avec Heuristique MRV (Minimum Remaining Values)

Énoncé

L’implémentation actuelle de BacktrackingDotNetSolver choisit les cellules à remplir dans l’ordre de parcours (de gauche à droite, de haut en bas). Implémentez une version améliorée avec l’heuristique MRV (Minimum Remaining Values) :

L’heuristique MRV choisit en priorité la cellule qui a le moins de valeurs possibles (le domaine le plus petit). Intuitivement, on commence par les cellules les plus contraintes pour détecter les échecs plus tôt et réduire l’espace de recherche.

Implémentez BacktrackingMRVSolver : 1. Pour chaque cellule vide, calculez son domaine (valeurs 1-9 compatibles avec les contraintes) 2. Choisissez la cellule avec le plus petit domaine non vide 3. Si un domaine est vide, retournez false immédiatement (échec précoce) 4. Comparez le nombre d’appels récursifs avec BacktrackingDotNetSolver

Indice :

Le calcul du domaine consiste à retirer de {1..9} toutes les valeurs déjà présentes dans la même ligne, colonne ou bloc. L’heuristique MRV réduit drastiquement les appels récursifs sur les puzzles difficiles.

TODO: Implementez BacktrackingMRVSolver pour comparer les performances

Exercice : Compter le nombre de solutions

Objectif : Modifiez le solveur backtracking pour compter le nombre total de solutions d’un puzzle donne (en arrêtant après un maximum pour eviter les boucles infinies).

Indice : Ajoutez un compteur global et arrêtez la recherche après maxCount solutions trouvées.

Exercice a completer

Conclusion et Analyse des Performances

L’algorithme de backtracking est une méthode efficace pour résoudre des puzzles de Sudoku simples a modérés. Pour des puzzles plus complexes, il peut devenir lent en raison du grand nombre de combinaisons possibles.

Aspect	Observation
Complétude	Oui - trouve toujours une solution si elle existe
Optimalité	N/A (il n’y a qu’une solution par grille valide)
Complexité	O(9^81) dans le pire cas, beaucoup mieux en pratique
Forces	Simple a implémenter, garanti de trouver une solution
Faiblesses	Lent sur les puzzles difficiles sans heuristiques

Pistes d’amélioration :

MRV (Minimum Remaining Values) : choisir la cellule la plus contrainte en premier
Forward Checking : éliminer les valeurs impossibles après chaque assignation
Propagation de contraintes : voir Sudoku-07 Norvig pour une approche plus sophistiquée

Prochaines étapes

Dans les notebooks suivants, nous explorerons des techniques plus avancées : - Sudoku-03 Genetic : approche métaheuristique - Sudoku-10 OR-Tools : programmation par contraintes industrielle

Navigation : << Sudoku-00 Environment | Index | Sudoku-03 Genetic >>

Chargeons un puzzle facile pour illustrer les concepts au fil du notebook.

var easySudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
display($"Puzzle de demonstration :\n{easySudoku}");
display($"Nombre de cellules vides : {easySudoku.NbEmptyCells()}");

Puzzle de demonstration :
-------------------------------
| 9     2 |       5 | 4     3 | 
| 1       |    6  3 |    2  5 | 
| 5     8 | 4     7 |    6    | 
-------------------------------
|    2  6 | 3     9 |       1 | 
|    5  7 |    1    | 2  9    | 
|    9    | 6  7    | 5  3    | 
-------------------------------
| 2  4    | 5  3    | 6       | 
| 7     5 | 2       | 3     4 | 
|    8    |    4  1 | 9  5    | 
-------------------------------

Nombre de cellules vides : 36

3. Fonction d’énergie (~3 min)

Principe

L’astuce fondamentale du recuit simulé pour le Sudoku est de travailler dans un espace d’états complets :

On initialisé chaque ligne comme une permutation de 1 à 9, en respectant les cellules fixes (indices données)
Par construction, les lignes ne contiennent jamais de doublons
L’énergie ne compte donc que les doublons dans les colonnes et les blocs 3x3

Contrainte	Respect	Vérification
Lignes	Garanti par construction (permutations)	Jamais viole
Colonnes	Non garanti	Compte dans l’énergie
Blocs 3x3	Non garanti	Compte dans l’énergie

Implémentation

La fonction ComputeEnergy compte le nombre de valeurs dupliquees dans chaque colonne et chaque bloc. Pour une colonne contenant \(k\) occurrences d’une même valeur, on ajoute \(k - 1\) a l’énergie.

Exercice : Calculer l’énergie d’une grille partielle

Objectif : Implémentez une variante de la fonction d’énergie qui ne compte les conflits que dans les lignes/colonnes/blocs contenant au moins une valeur non nulle.

Indice : Parcourez chaque unite et ignorez celles ou toutes les valeurs sont a 0.

// EXERCICE : Calculer l'energie d'une grille partielle
public int ComputePartialEnergy(int[,] grid)
{
    // TODO: Compter les conflits uniquement dans les unites non vides
    return 0; // TODO etudiant
}

/// <summary>
/// Calcule l'energie d'une grille de Sudoku.
/// L'energie correspond au nombre de violations de contraintes
/// dans les colonnes et les blocs 3x3.
/// Les lignes sont supposees correctes (permutations de 1-9).
/// </summary>
public static int ComputeEnergy(SudokuGrid grid)
{
    int energy = 0;

    // Doublons dans les colonnes
    for (int col = 0; col < 9; col++)
    {
        var counts = new int[10]; // indices 1-9
        for (int row = 0; row < 9; row++)
        {
            counts[grid.Cells[row, col]]++;
        }
        for (int val = 1; val <= 9; val++)
        {
            if (counts[val] > 1)
                energy += counts[val] - 1;
        }
    }

    // Doublons dans les blocs 3x3
    for (int boxRow = 0; boxRow < 3; boxRow++)
    {
        for (int boxCol = 0; boxCol < 3; boxCol++)
        {
            var counts = new int[10];
            for (int r = 0; r < 3; r++)
            {
                for (int c = 0; c < 3; c++)
                {
                    counts[grid.Cells[boxRow * 3 + r, boxCol * 3 + c]]++;
                }
            }
            for (int val = 1; val <= 9; val++)
            {
                if (counts[val] > 1)
                    energy += counts[val] - 1;
            }
        }
    }

    return energy;
}

display("Fonction ComputeEnergy definie.");

Fonction ComputeEnergy definie.

Initialisation de la grille

Pour initialiser l’état, on remplit chaque ligne avec les valeurs manquantes (celles qui ne figurent pas dans les indices) en les placant aleatoirement dans les cellules vides. Cela garantit que chaque ligne est une permutation de 1 à 9.

On conservé également un tableau isFixed pour identifier les cellules dont la valeur est donnee par l’énoncé et qui ne doivent pas etre modifiées.

/// <summary>
/// Initialise une grille en remplissant chaque ligne avec une permutation
/// de 1-9, en respectant les cellules fixes.
/// </summary>
public static (SudokuGrid grid, bool[,] isFixed) InitializeGrid(SudokuGrid puzzle, Random rng)
{
    var grid = (SudokuGrid)puzzle.Clone();
    var isFixed = new bool[9, 9];

    for (int row = 0; row < 9; row++)
    {
        // Identifier les valeurs fixes et les valeurs manquantes
        var fixedValues = new HashSet<int>();
        var emptyCells = new List<int>();

        for (int col = 0; col < 9; col++)
        {
            if (puzzle.Cells[row, col] > 0)
            {
                isFixed[row, col] = true;
                fixedValues.Add(puzzle.Cells[row, col]);
            }
            else
            {
                emptyCells.Add(col);
            }
        }

        // Valeurs manquantes pour completer la permutation
        var missingValues = Enumerable.Range(1, 9)
            .Where(v => !fixedValues.Contains(v))
            .OrderBy(_ => rng.Next())
            .ToList();

        // Remplir les cellules vides
        for (int i = 0; i < emptyCells.Count; i++)
        {
            grid.Cells[row, emptyCells[i]] = missingValues[i];
        }
    }

    return (grid, isFixed);
}

// Demonstration : initialiser la grille et calculer l'energie
var rng = new Random(42);
var (demoGrid, demoFixed) = InitializeGrid(easySudoku, rng);

display($"Grille initialisee (chaque ligne est une permutation de 1-9) :\n{demoGrid}");
display($"Energie initiale : {ComputeEnergy(demoGrid)}");
display($"Objectif : energie = 0");

Grille initialisee (chaque ligne est une permutation de 1-9) :
-------------------------------
| 9  7  2 | 6  8  5 | 4  1  3 | 
| 1  4  7 | 9  6  3 | 8  2  5 | 
| 5  1  8 | 4  3  7 | 9  6  2 | 
-------------------------------
| 8  2  6 | 3  5  9 | 7  4  1 | 
| 4  5  7 | 3  1  8 | 2  9  6 | 
| 4  9  2 | 6  7  1 | 5  3  8 | 
-------------------------------
| 2  4  8 | 5  3  7 | 6  9  1 | 
| 7  1  5 | 2  9  8 | 3  6  4 | 
| 3  8  2 | 6  4  1 | 9  5  7 | 
-------------------------------

Energie initiale : 31

Objectif : energie = 0

Interprétation : initialisation

La grille initialisee est complètement remplie : chaque cellule contient une valeur entre 1 et 9. Les lignes respectent la contrainte d’unicite par construction, mais les colonnes et les blocs contiennent probablement des doublons.

Aspect	Valeur	Signification
Cellules fixes	Préservées	Les indices de l’énoncé sont intouchables
Lignes	Toutes valides	Chaque ligne est une permutation de 1-9
Énergie > 0	Normale	Des doublons existent dans les colonnes et blocs
Objectif	Énergie = 0	Aucune violation de contrainte

Note technique : l’initialisation aleatoire des lignes donne une énergie de départ généralement comprise entre 30 et 60. Le recuit simulé devra reduire cette énergie a zero.

4. Voisinage : échange de cellules (~3 min)

Principe

Le voisinage définit les mouvements elementaires que l’algorithme peut effectuer. Pour le Sudoku avec permutations par ligne, le mouvement naturel est l’échange (swap) de deux cellules non fixes dans une même ligne :

On choisit une ligne au hasard
On choisit deux cellules non fixes dans cette ligne
On échange leurs valeurs

Ce mouvement préservé la propriete de permutation de la ligne : puisqu’on ne fait que permuter deux éléments, la ligne reste une permutation de 1 à 9.

Implémentation

Exercice : Générer un voisin par échange dans un bloc

Objectif : Implémentez un opérateur de voisinage qui échange deux valeurs non fixees dans le même bloc 3x3 au lieu de la même ligne.

Indice : Choisissez un bloc aleatoire, puis deux cellules non fixees dans ce bloc.

// EXERCICE : Generer un voisin par echange dans un bloc
public (int[,] Grid, (int, int) Pos1, (int, int) Pos2) GenerateBlockNeighbor(int[,] grid, bool[,] isFixed, Random rng)
{
    // TODO: Echangez deux valeurs non fixees dans un meme bloc 3x3
    return (null, (0, 0), (0, 0)); // TODO etudiant
}

/// <summary>
/// Genere un voisin en echangeant deux cellules non fixes dans une meme ligne.
/// Retourne la ligne et les deux colonnes echangees pour pouvoir annuler le mouvement.
/// </summary>
public static (int row, int col1, int col2) GenerateNeighbor(
    SudokuGrid grid, bool[,] isFixed, Random rng)
{
    // Choisir une ligne au hasard qui a au moins deux cellules non fixes
    int row;
    List<int> freeCols;
    do
    {
        row = rng.Next(9);
        freeCols = new List<int>();
        for (int col = 0; col < 9; col++)
        {
            if (!isFixed[row, col])
                freeCols.Add(col);
        }
    } while (freeCols.Count < 2);

    // Choisir deux cellules distinctes
    int idx1 = rng.Next(freeCols.Count);
    int idx2;
    do { idx2 = rng.Next(freeCols.Count); } while (idx2 == idx1);

    int col1 = freeCols[idx1];
    int col2 = freeCols[idx2];

    // Effectuer l'echange
    int temp = grid.Cells[row, col1];
    grid.Cells[row, col1] = grid.Cells[row, col2];
    grid.Cells[row, col2] = temp;

    return (row, col1, col2);
}

/// <summary>
/// Annule un echange precedemment effectue.
/// </summary>
public static void UndoSwap(SudokuGrid grid, int row, int col1, int col2)
{
    int temp = grid.Cells[row, col1];
    grid.Cells[row, col1] = grid.Cells[row, col2];
    grid.Cells[row, col2] = temp;
}

// Demonstration
var (testGrid, testFixed) = InitializeGrid(easySudoku, new Random(42));
int energyBefore = ComputeEnergy(testGrid);

var (swapRow, swapCol1, swapCol2) = GenerateNeighbor(testGrid, testFixed, new Random(123));
int energyAfter = ComputeEnergy(testGrid);

display($"Echange effectue : ligne {swapRow}, colonnes {swapCol1} <-> {swapCol2}");
display($"Energie avant : {energyBefore}, Energie apres : {energyAfter}, Delta : {energyAfter - energyBefore}");

Echange effectue : ligne 8, colonnes 8 <-> 3

Energie avant : 31, Energie apres : 33, Delta : 2

Interprétation : voisinage par échange

Propriete	Description
Type de mouvement	Échange de deux cellules non fixes dans une même ligne
Preservation des lignes	Garantie (permutation conservée)
Taille du voisinage	Environ \(\sum_{i=0}^{8} \binom{f_i}{2}\) ou \(f_i\) est le nombre de cellules libres en ligne \(i\)
Reversibilite	Oui (swap inverse = même swap)

Point clé : le voisinage est suffisamment petit pour etre exploré rapidement, mais suffisamment riche pour permettre des transitions significatives.

5. Algorithme de recuit simulé (~5 min)

Paramètres

Le recuit simulé est contrôle par plusieurs hyperparamètres :

Paramètre	Notation	Valeur par defaut	Rôle
Température initiale	\(T_0\)	1.0	Contrôle l’exploration initiale
Taux de refroidissement	\(\alpha\)	0.999	Vitesse de décroissance de \(T\)
Itérations par palier	\(N_{iter}\)	100	Nombre de tentatives a chaque température
Température minimale	\(T_{min}\)	0.001	Arret du refroidissement

Le programme de refroidissement est exponentiel : \(T_{k+1} = \alpha \cdot T_k\).

Algorithme

Initialiser la grille (permutations par ligne)
T <- T0
Tant que T > Tmin et E > 0 :
    Pour i = 1 a N_iter :
        Générer un voisin (swap)
        Calculer delta_E
        Si delta_E <= 0 : accepter
        Sinon : accepter avec probabilité exp(-delta_E / T)
    T <- alpha * T

Implémentation du solveur

using System;
using System.Diagnostics;

public class SimulatedAnnealingSolver : ISudokuSolver
{
    // Hyperparametres
    public double T0 { get; set; } = 1.0;
    public double Alpha { get; set; } = 0.999;
    public int IterationsPerTemperature { get; set; } = 100;
    public double TMin { get; set; } = 0.001;
    public int MaxRestarts { get; set; } = 5;

    // Statistiques de la derniere execution
    public int LastTotalIterations { get; private set; }
    public int LastRestarts { get; private set; }
    public List<(int iteration, int energy)> EnergyHistory { get; private set; }

    public SudokuGrid Solve(SudokuGrid s)
    {
        var rng = new Random();
        SudokuGrid bestGrid = null;
        int bestEnergy = int.MaxValue;
        EnergyHistory = new List<(int, int)>();
        LastTotalIterations = 0;
        LastRestarts = 0;

        for (int restart = 0; restart <= MaxRestarts; restart++)
        {
            var (grid, isFixed) = InitializeGrid(s, rng);
            int currentEnergy = ComputeEnergy(grid);
            int iterationOffset = LastTotalIterations;

            if (currentEnergy < bestEnergy)
            {
                bestEnergy = currentEnergy;
                bestGrid = (SudokuGrid)grid.Clone();
            }

            if (currentEnergy == 0)
                return bestGrid;

            double T = T0;
            int totalIter = 0;

            while (T > TMin && currentEnergy > 0)
            {
                for (int i = 0; i < IterationsPerTemperature; i++)
                {
                    // Generer un voisin
                    var (row, col1, col2) = GenerateNeighbor(grid, isFixed, rng);
                    int newEnergy = ComputeEnergy(grid);
                    int deltaE = newEnergy - currentEnergy;

                    if (deltaE <= 0 || rng.NextDouble() < Math.Exp(-deltaE / T))
                    {
                        // Accepter le mouvement
                        currentEnergy = newEnergy;

                        if (currentEnergy < bestEnergy)
                        {
                            bestEnergy = currentEnergy;
                            bestGrid = (SudokuGrid)grid.Clone();
                        }

                        if (currentEnergy == 0)
                        {
                            LastTotalIterations += totalIter;
                            LastRestarts = restart;
                            return bestGrid;
                        }
                    }
                    else
                    {
                        // Rejeter le mouvement : annuler l'echange
                        UndoSwap(grid, row, col1, col2);
                    }

                    totalIter++;

                    // Enregistrer l'energie periodiquement
                    if (totalIter % 500 == 0)
                    {
                        EnergyHistory.Add((iterationOffset + totalIter, currentEnergy));
                    }
                }

                T *= Alpha;
            }

            LastTotalIterations += totalIter;
            LastRestarts = restart;

            // Si l'energie est a zero, on a trouve la solution
            if (bestEnergy == 0)
                return bestGrid;
        }

        // Retourner la meilleure grille trouvee (meme si imparfaite)
        return bestGrid;
    }
}

display("Classe SimulatedAnnealingSolver definie.");

Classe SimulatedAnnealingSolver definie.

Premier test : puzzle facile

Testons le solveur sur un puzzle facile pour verifier son fonctionnement.

var easySudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
var saSolver = new SimulatedAnnealingSolver
{
    T0 = 1.0,
    Alpha = 0.999,
    IterationsPerTemperature = 100,
    TMin = 0.001,
    MaxRestarts = 5
};

display("Puzzle facile :");
var solved = SudokuHelper.SolveSudoku(easySudoku, saSolver);

display($"Iterations totales : {saSolver.LastTotalIterations}");
display($"Redemarrages : {saSolver.LastRestarts}");

Puzzle facile :

Résolution par le solver SimulatedAnnealingSolver du Sudoku:
 -------------------------------
| 9     2 |       5 | 4     3 | 
| 1       |    6  3 |    2  5 | 
| 5     8 | 4     7 |    6    | 
-------------------------------
|    2  6 | 3     9 |       1 | 
|    5  7 |    1    | 2  9    | 
|    9    | 6  7    | 5  3    | 
-------------------------------
| 2  4    | 5  3    | 6       | 
| 7     5 | 2       | 3     4 | 
|    8    |    4  1 | 9  5    | 
-------------------------------

Sudoku renvoyé:
-------------------------------
| 9  6  2 | 1  8  5 | 4  7  3 | 
| 1  7  4 | 9  6  3 | 8  2  5 | 
| 5  3  8 | 4  2  7 | 1  6  9 | 
-------------------------------
| 8  2  6 | 3  5  9 | 7  4  1 | 
| 3  5  7 | 8  1  4 | 2  9  6 | 
| 4  9  1 | 6  7  2 | 5  3  8 | 
-------------------------------
| 2  4  9 | 5  3  8 | 6  1  7 | 
| 7  1  5 | 2  9  6 | 3  8  4 | 
| 6  8  3 | 7  4  1 | 9  5  2 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 20,3753 ms

Iterations totales : 1453

Redemarrages : 0

Interprétation : premier test

Aspect	Observation
Résultat	Le recuit simulé trouve généralement la solution pour les puzzles faciles
Temps	Variable ; mesure en direct (cellule precedente) — d’autres puzzles faciles demandent plusieurs secondes (cf. test suivant)
Itérations	Très variable selon le puzzle : re-mesurez en direct (cellule precedente) — de l’ordre de 1 000 a plus de 2 millions sur l’echantillon de cellules faciles
Non-determinisme	Chaque exécution peut donner un résultat différent

Point clé : contrairement au backtracking qui est déterministe et garanti, le recuit simulé est probabiliste. Il peut échouer, notamment sur les puzzles difficiles.

6. Tests et évaluation (~4 min)

Test sur plusieurs puzzles

Evaluons le solveur sur des puzzles de difficultés variées. Le recuit simulé etant non déterministe, nous mesurons le taux de succes sur plusieurs tentatives.

// Test du taux de succes sur des puzzles faciles
var easyPuzzles = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).Take(5).ToList();
int easySuccess = 0;
var easyTimes = new List<double>();

display("Test sur 5 puzzles faciles :");
foreach (var puzzle in easyPuzzles)
{
    var solver = new SimulatedAnnealingSolver
    {
        T0 = 1.0, Alpha = 0.999,
        IterationsPerTemperature = 100, TMin = 0.001,
        MaxRestarts = 5
    };

    var sw = Stopwatch.StartNew();
    var result = solver.Solve(puzzle);
    sw.Stop();

    int errors = result.NbErrors(puzzle);
    bool success = errors == 0;
    if (success) easySuccess++;
    easyTimes.Add(sw.Elapsed.TotalMilliseconds);

    display($"  Puzzle : {(success ? "Resolu" : $"Echec ({errors} erreurs)")} en {sw.Elapsed.TotalMilliseconds:F0} ms ({solver.LastTotalIterations} iterations, {solver.LastRestarts} restarts)");
}

display($"\nTaux de succes (Easy) : {easySuccess}/5");
display($"Temps moyen : {easyTimes.Average():F0} ms");

Test sur 5 puzzles faciles :

  Puzzle : Resolu en 2 ms (762 iterations, 0 restarts)

  Puzzle : Resolu en 250 ms (97523 iterations, 0 restarts)

  Puzzle : Resolu en 1475 ms (754010 iterations, 1 restarts)

  Puzzle : Resolu en 1483 ms (749180 iterations, 1 restarts)

  Puzzle : Resolu en 2853 ms (1499873 iterations, 2 restarts)


Taux de succes (Easy) : 5/5

Temps moyen : 1213 ms

Test sur des puzzles de difficulté moyenne

Augmentons les paramètres du recuit simulé (refroidissement plus lent, plus de restarts) pour tenter de résoudre des puzzles de difficulté moyenne.

// Test sur des puzzles medium
var mediumPuzzles = SudokuHelper.GetSudokus(SudokuDifficulty.Medium).Take(3).ToList();
int mediumSuccess = 0;

display("Test sur 3 puzzles medium :");
foreach (var puzzle in mediumPuzzles)
{
    var solver = new SimulatedAnnealingSolver
    {
        T0 = 1.0, Alpha = 0.9995,
        IterationsPerTemperature = 200, TMin = 0.0001,
        MaxRestarts = 10
    };

    var sw = Stopwatch.StartNew();
    var result = solver.Solve(puzzle);
    sw.Stop();

    int errors = result.NbErrors(puzzle);
    bool success = errors == 0;
    if (success) mediumSuccess++;

    display($"  Puzzle : {(success ? "Resolu" : $"Echec ({errors} erreurs)")} en {sw.Elapsed.TotalMilliseconds:F0} ms ({solver.LastTotalIterations} iterations, {solver.LastRestarts} restarts)");
}

display($"\nTaux de succes (Medium) : {mediumSuccess}/3");

Test sur 3 puzzles medium :

  Puzzle : Echec (2 erreurs) en 91689 ms (40517400 iterations, 10 restarts)

  Puzzle : Echec (2 erreurs) en 99764 ms (40517400 iterations, 10 restarts)

  Puzzle : Resolu en 809 ms (401959 iterations, 0 restarts)


Taux de succes (Medium) : 1/3

Interprétation : résultats des tests

Le tableau ci-dessous distingue le comportement général attendu du recuit simulé de ce qui a ete réellement observé dans les sorties committees de ce notebook. Les deux peuvent diverger fortement car le résultat depend du réglage des hyperparamètres (\(T_0\), \(\alpha\), \(N_{iter}\), redemarrages), qui n’est pas le même d’une cellule de test a l’autre.

Difficulté	Comportement général attendu	Observé dans les sorties committees
Easy	Souvent reussi	5/5 résolus (test dédié) ; duree variable selon le puzzle (mesuree en direct, cellules precedentes)
Medium	Résultat variable, sensible au réglage	Très sensible aux paramètres : 2/3 résolus avec un réglage agressif (\(\alpha=0{,}9995\), 200 iter/palier, 10 redemarrages) mais en plusieurs dizaines de secondes (mesurees en direct) ; 0/5 avec les paramètres du banc de comparaison
Hard	Rarement reussi sans améliorations	0 résolu (banc de comparaison), statut Disqualifie

Points clés : 1. Le recuit simulé ne garantit pas de trouver la solution, et son taux de succes varié enormement selon les hyperparamètres (de 0 % a 67 % sur Medium selon le réglage). 2. Un réglage qui augmente le taux de succes (plus d’itérations par palier, refroidissement plus lent, plus de redemarrages) augmente aussi fortement le temps : les puzzles Medium résolus le sont en plusieurs dizaines de secondes. 3. Pour les puzzles difficiles, les solveurs CSP (OR-Tools, Z3) et le backtracking restent bien plus fiables et rapides.

Comparaison avec les autres solveurs

Utilisons l’infrastructure SudokuHelper.TestSolvers pour comparer le recuit simulé avec le backtracking.

Exercice : Comparer les schemas de refroidissement

Objectif : Comparez le schema de refroidissement lineaire et exponentiel. Mesurez le taux de succes et le temps moyen pour chaque schema.

Indice : Pour le schema exponentiel: T = T_init * alpha^step.

// EXERCICE : Comparer les schemas de refroidissement
public List<double> ExponentialCooling(double T_init, double T_min, double alpha, int maxSteps)
{
    // TODO: Generez la liste de temperatures selon le schema exponentiel
    return null; // TODO etudiant
}

var solversToTest = new List<(string Name, ISudokuSolver Solver)>
{
    ("Backtracking", new BacktrackingDotNetSolver()),
    ("SimulatedAnnealing", new SimulatedAnnealingSolver
    {
        T0 = 1.0, Alpha = 0.999,
        IterationsPerTemperature = 100, TMin = 0.001,
        MaxRestarts = 3
    })
};

var results = SudokuHelper.TestSolvers(solversToTest, numberOfSudokus: 5, timeLimitMilliseconds: 10000);

// Affichage des resultats
display("Resultats de la comparaison :");
foreach (var r in results)
{
    display($"  {r.SolverName} | {r.Difficulty} | {r.Time:F0} ms | {r.SolvedCount} resolus | {r.Status}");
}

SudokuHelper.DisplayResults(results);

Running tests...

BacktrackingDotNetSolver: 122 search calls
BacktrackingDotNetSolver: 311 search calls
BacktrackingDotNetSolver: 477 search calls
BacktrackingDotNetSolver: 25565 search calls
BacktrackingDotNetSolver: 2544 search calls
BacktrackingDotNetSolver: 490304 search calls
BacktrackingDotNetSolver: 15387 search calls
BacktrackingDotNetSolver: 337036 search calls
BacktrackingDotNetSolver: 114216 search calls
BacktrackingDotNetSolver: 250684 search calls
BacktrackingDotNetSolver: 12625368 search calls
BacktrackingDotNetSolver: 4405485 search calls
BacktrackingDotNetSolver: 126417 search calls
BacktrackingDotNetSolver: 503219 search calls
BacktrackingDotNetSolver: 124635056 search calls

Resultats de la comparaison :

  Backtracking | Easy | 14 ms | 5 resolus | Success

  Backtracking | Medium | 480 ms | 5 resolus | Success

  Backtracking | Hard | 19171 ms | 4 resolus | Disqualified

  SimulatedAnnealing | Easy | 9213 ms | 4 resolus | Disqualified

  SimulatedAnnealing | Medium | 25887 ms | 0 resolus | Disqualified

  SimulatedAnnealing | Hard | 27811 ms | 0 resolus | Disqualified

Comparaison des solveurs - Hard : aucun solveur qualifie (tous disqualifies ou en timeout).

Interprétation : comparaison

Solveur	Forces	Faiblesses
Backtracking	Déterministe, garanti, rapide	Pas d’optimisation, recherche exhaustive
Recuit simulé	Élégant, applicable a tout problème d’optimisation	Non garanti, lent, necessite du réglage

Avec les paramètres du banc de comparaison ci-dessus, le recuit simulé est disqualifie aux trois niveaux (Easy : 4/5 ; Medium : 0/5 ; Hard : 0/5), faute de résoudre la totalité des puzzles dans le temps imparti – alors que le backtracking reste Success sur Easy et Medium. Cela illustre une propriete fondamentale :

Pour un problème de satisfaction de contraintes comme le Sudoku, les solveurs dédiés (backtracking, CSP) sont généralement plus efficaces que les métaheuristiques generiques. Le recuit simulé est davantage adapte aux problèmes d’optimisation ou il n’existe pas de solution parfaite. Note : avec un réglage plus agressif (cf. test Medium dédié), le recuit simulé resout une partie des puzzles Medium, mais au prix de plusieurs dizaines de secondes par grille.

7. Améliorations et analyse (~2 min)

Améliorations possibles

Plusieurs stratégies peuvent améliorer les performances du recuit simulé sur le Sudoku :

Amelioration	Principe	Benefice attendu
Réchauffement (reheating)	Remonter \(T\) quand l’énergie stagne	Échapper aux optima locaux
Refroidissement adaptatif	Ajuster \(\alpha\) en fonction du taux d’acceptation	Meilleur équilibre exploration/exploitation
Restarts multiples	Relancer depuis un nouvel état initial	Augmenter la probabilité de succes
Voisinage etendu	Permettre des échanges entre lignes ou des rotations	Explorer plus largement

Analyse théorique

Le recuit simulé possède une propriete théorique remarquable : avec un refroidissement suffisamment lent (logarithmique), il converge en probabilité vers l’optimum global. Cependant, en pratique, un refroidissement aussi lent rend l’algorithme inutilisable.

Pour le Sudoku specifiquement :

Propriete	Analyse
Taille de l’espace	Très grand (\(\prod_i f_i!\) permutations, ou \(f_i\) = cellules libres par ligne)
Paysage d’énergie	De nombreux optima locaux proches de la solution
Densite de solutions	Très faible (souvent une seule solution)
Adaptabilite	Bien adapte pour l’exploration, mal adapte pour la convergence exacte

Démonstration du réchauffement

Implémentons une version améliorée avec réchauffement : si l’énergie ne diminue pas pendant un certain nombre de paliers de température, on remonte la température pour relancer l’exploration.

public class SimulatedAnnealingWithReheatSolver : ISudokuSolver
{
    public double T0 { get; set; } = 1.0;
    public double Alpha { get; set; } = 0.999;
    public int IterationsPerTemperature { get; set; } = 100;
    public double TMin { get; set; } = 0.001;
    public int MaxRestarts { get; set; } = 5;
    public int StagnationThreshold { get; set; } = 50;
    public double ReheatFactor { get; set; } = 0.5;

    public SudokuGrid Solve(SudokuGrid s)
    {
        var rng = new Random();
        SudokuGrid bestGrid = null;
        int bestEnergy = int.MaxValue;

        for (int restart = 0; restart <= MaxRestarts; restart++)
        {
            var (grid, isFixed) = InitializeGrid(s, rng);
            int currentEnergy = ComputeEnergy(grid);
            int lastBestEnergy = currentEnergy;
            int stagnationCount = 0;

            if (currentEnergy < bestEnergy)
            {
                bestEnergy = currentEnergy;
                bestGrid = (SudokuGrid)grid.Clone();
            }

            if (currentEnergy == 0)
                return bestGrid;

            double T = T0;

            while (T > TMin && currentEnergy > 0)
            {
                int energyBeforePalier = currentEnergy;

                for (int i = 0; i < IterationsPerTemperature; i++)
                {
                    var (row, col1, col2) = GenerateNeighbor(grid, isFixed, rng);
                    int newEnergy = ComputeEnergy(grid);
                    int deltaE = newEnergy - currentEnergy;

                    if (deltaE <= 0 || rng.NextDouble() < Math.Exp(-deltaE / T))
                    {
                        currentEnergy = newEnergy;
                        if (currentEnergy < bestEnergy)
                        {
                            bestEnergy = currentEnergy;
                            bestGrid = (SudokuGrid)grid.Clone();
                        }
                        if (currentEnergy == 0)
                            return bestGrid;
                    }
                    else
                    {
                        UndoSwap(grid, row, col1, col2);
                    }
                }

                // Detection de stagnation
                if (currentEnergy >= energyBeforePalier)
                {
                    stagnationCount++;
                }
                else
                {
                    stagnationCount = 0;
                }

                // Rechauffement si stagnation
                if (stagnationCount >= StagnationThreshold)
                {
                    T = T0 * ReheatFactor;
                    stagnationCount = 0;
                }
                else
                {
                    T *= Alpha;
                }
            }

            if (bestEnergy == 0)
                return bestGrid;
        }

        return bestGrid;
    }
}

// Test de la version avec rechauffement
var easySudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
var reheatSolver = new SimulatedAnnealingWithReheatSolver
{
    T0 = 1.0, Alpha = 0.999,
    IterationsPerTemperature = 100, TMin = 0.001,
    MaxRestarts = 3, StagnationThreshold = 50,
    ReheatFactor = 0.5
};

display("Test avec rechauffement sur puzzle facile :");
SudokuHelper.SolveSudoku(easySudoku, reheatSolver);

Test avec rechauffement sur puzzle facile :

Résolution par le solver SimulatedAnnealingWithReheatSolver du Sudoku:
 -------------------------------
| 9     2 |       5 | 4     3 | 
| 1       |    6  3 |    2  5 | 
| 5     8 | 4     7 |    6    | 
-------------------------------
|    2  6 | 3     9 |       1 | 
|    5  7 |    1    | 2  9    | 
|    9    | 6  7    | 5  3    | 
-------------------------------
| 2  4    | 5  3    | 6       | 
| 7     5 | 2       | 3     4 | 
|    8    |    4  1 | 9  5    | 
-------------------------------

Sudoku renvoyé:
-------------------------------
| 9  6  2 | 1  8  5 | 4  7  3 | 
| 1  7  4 | 9  6  3 | 8  2  5 | 
| 5  3  8 | 4  2  7 | 1  6  9 | 
-------------------------------
| 8  2  6 | 3  5  9 | 7  4  1 | 
| 3  5  7 | 8  1  4 | 2  9  6 | 
| 4  9  1 | 6  7  2 | 5  3  8 | 
-------------------------------
| 2  4  9 | 5  3  8 | 6  1  7 | 
| 7  1  5 | 2  9  6 | 3  8  4 | 
| 6  8  3 | 7  4  1 | 9  5  2 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 5,7521 ms

Interprétation : version avec réchauffement

Le réchauffement permet de relancer l’exploration lorsque l’algorithme est bloqué sur un optimum local. En remontant la température a une fraction de \(T_0\), on autorise a nouveau l’acceptation de mouvements dégradants, ce qui peut permettre de s’échapper de la vallée locale.

Version	Avantage	Inconvénient
SA classique	Simple, paramétrage minimal	Bloqué sur les optima locaux
SA + réchauffement	Meilleur echappement	Un paramètre de plus (`StagnationThreshold`)
SA + restarts	Exploration maximale	Perd tout l’historique a chaque restart

8. Exemple guide

Exemple guide 1 : Expérimenter les programmes de refroidissement

Modifiez le solveur pour tester différents programmes de refroidissement et comparez les résultats :

Programme	Formule	Valeur suggérée
Exponentiel rapide	\(T \leftarrow 0.99 \cdot T\)	`Alpha = 0.99`
Exponentiel moyen	\(T \leftarrow 0.999 \cdot T\)	`Alpha = 0.999`
Exponentiel lent	\(T \leftarrow 0.9999 \cdot T\)	`Alpha = 0.9999`

Pour chaque programme, executez 10 tentatives sur un puzzle facile et mesurez le taux de succes et le temps moyen.

// Exemple guide 1 : Comparaison des programmes de refroidissement
// Completez le code ci-dessous pour tester differentes valeurs de Alpha

var puzzle = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
var alphas = new[] { 0.99, 0.999, 0.9999 };
int trials = 10;

display($"{"Alpha",-10} {"Succes",-10} {"Temps moy. (ms)",-18}");
display(new string('-', 40));

foreach (var alpha in alphas)
{
    int successes = 0;
    double totalTime = 0;

    for (int t = 0; t < trials; t++)
    {
        var solver = new SimulatedAnnealingSolver
        {
            T0 = 1.0, Alpha = alpha,
            IterationsPerTemperature = 100,
            TMin = 0.0001,
            MaxRestarts = 3
        };

        var sw = Stopwatch.StartNew();
        var result = solver.Solve(puzzle);
        sw.Stop();

        if (result.NbErrors(puzzle) == 0) successes++;
        totalTime += sw.Elapsed.TotalMilliseconds;
    }

    display($"{alpha,-10} {successes}/{trials,-7} {totalTime / trials,-18:F0}");
}

Alpha      Succes     Temps moy. (ms)

----------------------------------------

0,99       10/10      2

0,999      10/10      2

0,9999     10/10      3

Exercice 2 : Réchauffement adaptatif

Modifiez la classe SimulatedAnnealingWithReheatSolver pour implementer un réchauffement adaptatif :

Si l’énergie ne diminue pas pendant N paliers de température consécutifs, remonter la température
Le facteur de réchauffement diminue progressivement a chaque réchauffement (ex: 0.5, puis 0.3, puis 0.2…)
Afficher un message a chaque réchauffement pour observer le comportement

Testez sur un puzzle medium et observez si les rechauffements aident a converger.

// Exemple guide 2 : Rechauffement adaptatif
// A completer : modifier SimulatedAnnealingWithReheatSolver
// pour que ReheatFactor diminue a chaque rechauffement

// Indice : ajouter un compteur de rechauffements
// et calculer ReheatFactor = initialReheatFactor / (1 + reheatCount)

display("Exercice 2 : implementez le rechauffement adaptatif ci-dessus.");

Exercice 2 : implementez le rechauffement adaptatif ci-dessus.

9. Resolution via GeneticSharp (moteur metaheuristique .NET)

Parallele lib-vs-lib avec la jumelle Python

Le notebook jumeau Python (Sudoku-04-SimulatedAnnealing-Python.ipynb) resout le Sudoku par recuit simule via le framework simanneal : l’etudiant sous-classe Annealer et herite de l’infrastructure de voisinage, de decroissance de temperature et de critere d’acceptation de Metropolis. Cote C#, les sections 3 a 8 ci-dessus ont implemente le recuit simule from scratch (classe SimulatedAnnealingSolver).

Pour atteindre la parite lib-vs-lib – chaque jumeau atteignant un moteur de production de son ecosysteme – cette section branche GeneticSharp, la librairie .NET de reference pour les algorithmes evolutionnaires. A l’instar de simanneal cote Python, GeneticSharp fournit l’infrastructure (Population, GeneticAlgorithm, selection, crossover, mutation, criteres de terminaison, executeur parallele TPL) : on y branche notre Probleme Sudoku plutot que de reimplmenter le moteur. Le recuit from scratch est conserve en plus, jamais remplace.

GeneticSharp operant par algorithme genetique (population d’individus + operateurs stochastiques), le point de vue est complementaire du recuit simule (trajectoire unique avec bruit thermique) : c’est l’occasion de comparer les deux familles metaheuristiques sur le meme Sudoku. L’enjeu technique specifique a un GA de Sudoku : l’espace de recherche est gigantesque (\(9^{N}\) pour \(N\) cellules vides), et un encodage naif (un chiffre aleatoire 1-9 par cellule vide) converge tres mal. On adopte l’encodage classique par permutation de ligne : chaque ligne est toujours une permutation valide de ses chiffres manquants, donc le GA ne gere plus que les conflits de colonnes et de blocs – ce qui exige des operateurs preservant la structure de permutation (custom).

#r "nuget: GeneticSharp, 3.1.4"
using GeneticSharp;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

// --- Chromosome : encodage par permutation de ligne ---
// Une gene par cellule vide ; pour chaque ligne, les cellules vides recoivent
// une permutation (shuffle de Fisher-Yates) des chiffres manquants de cette ligne.
// Garantie : chaque ligne est toujours valide (1-9 sans doublon) --> le GA n'optimise
// que les conflits colonnes + blocs, espace de recherche drastiquement reduit.
// NB : on utilise RandomizationProvider.Current (thread-safe) car GeneticSharp parallelise
// l'evaluation via TplTaskExecutor -- un System.Random statique partagé provoquerait une
// course critique (permutations corrompues, erreurs >50 au lieu de ~0).
public class SudokuRowPermutationChromosome : ChromosomeBase
{
    public SudokuGrid Puzzle { get; }
    public List<(int row, int col)> EmptyCells { get; }
    public Dictionary<int, List<int>> MissingPerRow { get; }

    public SudokuRowPermutationChromosome(SudokuGrid puzzle) : base(CountEmpty(puzzle))
    {
        Puzzle = puzzle;
        EmptyCells = new List<(int, int)>();
        MissingPerRow = new Dictionary<int, List<int>>();
        for (int r = 0; r < 9; r++)
        {
            var present = new HashSet<int>();
            for (int c = 0; c < 9; c++) if (puzzle.Cells[r, c] != 0) present.Add(puzzle.Cells[r, c]);
            MissingPerRow[r] = Enumerable.Range(1, 9).Where(d => !present.Contains(d)).ToList();
            for (int c = 0; c < 9; c++) if (puzzle.Cells[r, c] == 0) EmptyCells.Add((r, c));
        }
        CreateGenes();
    }

    private static int CountEmpty(SudokuGrid p)
    {
        int n = 0;
        for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (p.Cells[r, c] == 0) n++;
        return n;
    }

    private List<int> BuildGenes()
    {
        var rnd = RandomizationProvider.Current;
        var res = new List<int>();
        foreach (var grp in EmptyCells.GroupBy(e => e.row))
        {
            var missing = new List<int>(MissingPerRow[grp.Key]);
            for (int i = missing.Count - 1; i > 0; i--) { int j = rnd.GetInt(0, i + 1); (missing[i], missing[j]) = (missing[j], missing[i]); }
            int k = 0; foreach (var cell in grp) res.Add(missing[k++]);
        }
        return res;
    }

    public override Gene GenerateGene(int index) => new Gene(RandomizationProvider.Current.GetInt(1, 10));
    protected override void CreateGenes() { var g = BuildGenes(); for (int i = 0; i < g.Count; i++) ReplaceGene(i, new Gene(g[i])); }
    public SudokuGrid ToSudokuGrid()
    {
        var g = (SudokuGrid)Puzzle.Clone();
        for (int i = 0; i < EmptyCells.Count; i++) { var (r, c) = EmptyCells[i]; g.Cells[r, c] = (int)GetGene(i).Value; }
        return g;
    }
    public override IChromosome CreateNew()
    {
        var ch = new SudokuRowPermutationChromosome(Puzzle);
        var g = BuildGenes(); for (int i = 0; i < g.Count; i++) ch.ReplaceGene(i, new Gene(g[i]));
        return ch;
    }
    // Indices de genes regroupes par ligne (pour les operateurs custom)
    public List<List<int>> RowGeneIndices() =>
        EmptyCells.Select((ec, i) => (ec, i)).GroupBy(x => x.ec.row).Select(g => g.Select(x => x.i).ToList()).ToList();
}

// --- Fitness : minimiser les conflits (lignes deja valides par construction) ---
public class SudokuGeneticFitness : IFitness
{
    public double Evaluate(IChromosome chromosome)
    {
        var sc = (SudokuRowPermutationChromosome)chromosome;
        return -sc.ToSudokuGrid().NbErrors(sc.Puzzle);
    }
}

// --- Mutation custom : echange de deux cellules DANS la meme ligne ---
// Prend deux cellules vides d'une meme ligne et les echange : la ligne reste
// une permutation valide (meme ensemble de chiffres, ordre different).
public class SudokuRowSwapMutation : MutationBase
{
    public SudokuRowSwapMutation() { IsOrdered = true; }
    protected override void PerformMutate(IChromosome chromosome, float probability)
    {
        var rnd = RandomizationProvider.Current;
        var sc = (SudokuRowPermutationChromosome)chromosome;
        foreach (var rowIdxs in sc.RowGeneIndices())
        {
            if (rowIdxs.Count < 2 || rnd.GetDouble() > probability) continue;
            int a = rnd.GetInt(0, rowIdxs.Count), b = rnd.GetInt(0, rowIdxs.Count);
            if (a == b) continue;
            var ga = chromosome.GetGene(rowIdxs[a]);
            chromosome.ReplaceGene(rowIdxs[a], chromosome.GetGene(rowIdxs[b]));
            chromosome.ReplaceGene(rowIdxs[b], ga);
        }
    }
}

// --- Crossover custom : Ordered Crossover (OX) applique PAR LIGNE ---
// Pour chaque ligne, on recopie un segment du parent A et on complete avec les
// chiffres du parent B dans l'ordre, en sautant les deja-utilises. La structure
// de permutation de chaque ligne est ainsi preservee chez les enfants.
public class SudokuRowOrderedCrossover : CrossoverBase
{
    public SudokuRowOrderedCrossover() : base(2, 2) { }
    protected override IChromosome[] PerformCross(IList<IChromosome> parents)
    {
        var rnd = RandomizationProvider.Current;
        var p1 = (SudokuRowPermutationChromosome)parents[0];
        var p2 = (SudokuRowPermutationChromosome)parents[1];
        var c1 = (SudokuRowPermutationChromosome)p1.CreateNew();
        var c2 = (SudokuRowPermutationChromosome)p1.CreateNew();
        var rows = p1.RowGeneIndices();
        for (int ri = 0; ri < rows.Count; ri++)
        {
            var idxs = rows[ri];
            if (idxs.Count < 2) continue;
            int cutA = rnd.GetInt(0, idxs.Count), cutB = rnd.GetInt(0, idxs.Count);
            if (cutA > cutB) (cutA, cutB) = (cutB, cutA);
            OXRow(c1, p1, p2, idxs, cutA, cutB);
            OXRow(c2, p2, p1, idxs, cutA, cutB);
        }
        return new IChromosome[] { c1, c2 };
    }
    private static void OXRow(SudokuRowPermutationChromosome child,
        SudokuRowPermutationChromosome a, SudokuRowPermutationChromosome b, List<int> idxs, int cutA, int cutB)
    {
        var used = new HashSet<int>();
        for (int i = cutA; i <= cutB; i++) { int v = (int)a.GetGene(idxs[i]).Value; child.ReplaceGene(idxs[i], new Gene(v)); used.Add(v); }
        int fill = 0;
        for (int i = 0; i < idxs.Count; i++)
        {
            if (i >= cutA && i <= cutB) continue;
            while (fill < idxs.Count)
            {
                int v = (int)b.GetGene(idxs[fill]).Value; fill++;
                if (!used.Contains(v)) { child.ReplaceGene(idxs[i], new Gene(v)); used.Add(v); break; }
            }
        }
    }
}

// --- Solver GeneticSharp exposant le contrat ISudokuSolver (meme interface que le SA from scratch) ---
// Inclut une logique de redemarrages (MaxRestarts), symetrique au SA de la Tranche 1 :
// si une population stagne sans atteindre 0 conflit, on relance avec une nouvelle population.
public class SudokuGeneticSharpSolver : ISudokuSolver
{
    public int PopulationSize { get; set; } = 500;
    public int MaxGenerations { get; set; } = 400;
    public int Stagnation { get; set; } = 80;
    public int MaxRestarts { get; set; } = 5;
    public int LastGenerations { get; private set; }
    public int LastRestarts { get; private set; }

    public SudokuGrid Solve(SudokuGrid s)
    {
        SudokuGrid best = null;
        int bestErr = int.MaxValue;
        LastRestarts = 0;
        for (int restart = 0; restart <= MaxRestarts; restart++)
        {
            var fitness = new SudokuGeneticFitness();
            var pop = new Population(PopulationSize, PopulationSize, new SudokuRowPermutationChromosome(s));
            var ga = new GeneticAlgorithm(pop, fitness, new EliteSelection(),
                new SudokuRowOrderedCrossover(), new SudokuRowSwapMutation());
            ga.OperatorsStrategy = new TplOperatorsStrategy();
            ga.TaskExecutor = new TplTaskExecutor();
            ga.CrossoverProbability = 0.75f;
            ga.MutationProbability = 0.2f;
            ga.Termination = new OrTermination(new ITermination[] {
                new FitnessThresholdTermination(0),
                new FitnessStagnationTermination(Stagnation),
                new GenerationNumberTermination(MaxGenerations)
            });
            ga.Start();
            LastGenerations = ga.GenerationsNumber;
            LastRestarts = restart;
            var cand = ((SudokuRowPermutationChromosome)ga.Population.BestChromosome).ToSudokuGrid();
            int err = cand.NbErrors(s);
            if (err < bestErr) { bestErr = err; best = cand; }
            if (err == 0) return best;
        }
        return best;
    }
}

display("Classe SudokuGeneticSharpSolver definie (GeneticSharp + chromosome permutation-ligne + operateurs custom thread-safe).");

Installing Packages

GeneticSharp

Classe SudokuGeneticSharpSolver definie (GeneticSharp + chromosome permutation-ligne + operateurs custom thread-safe).

// Demonstration : resolution du meme puzzle facile que la Tranche 1, via GeneticSharp
var easySudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
var gaSolver = new SudokuGeneticSharpSolver { PopulationSize = 500, MaxGenerations = 400, Stagnation = 80, MaxRestarts = 5 };

var sw = Stopwatch.StartNew();
var gaResult = gaSolver.Solve(easySudoku);
sw.Stop();

int gaErrors = gaResult.NbErrors(easySudoku);
display($"GeneticSharp : {(gaErrors == 0 ? "Resolu" : $"{gaErrors} erreurs")} en {sw.Elapsed.TotalMilliseconds:F0} ms ({gaSolver.LastGenerations} generations, restart {gaSolver.LastRestarts})");
display(gaResult.ToString());

GeneticSharp : Resolu en 625 ms (57 generations, restart 0)

-------------------------------
| 9  6  2 | 1  8  5 | 4  7  3 | 
| 1  7  4 | 9  6  3 | 8  2  5 | 
| 5  3  8 | 4  2  7 | 1  6  9 | 
-------------------------------
| 8  2  6 | 3  5  9 | 7  4  1 | 
| 3  5  7 | 8  1  4 | 2  9  6 | 
| 4  9  1 | 6  7  2 | 5  3  8 | 
-------------------------------
| 2  4  9 | 5  3  8 | 6  1  7 | 
| 7  1  5 | 2  9  6 | 3  8  4 | 
| 6  8  3 | 7  4  1 | 9  5  2 | 
-------------------------------

// Comparaison des deux familles metaheuristiques : recuit simule vs algorithme genetique
// Borne a 3 puzzles et 15 s par difficulte pour garder un temps de notebook raisonnable.
var solversToCompare = new List<(string Name, ISudokuSolver Solver)>
{
    ("Recuit simule (from scratch)", new SimulatedAnnealingSolver
    {
        T0 = 1.0, Alpha = 0.999,
        IterationsPerTemperature = 100, TMin = 0.001, MaxRestarts = 3
    }),
    ("GeneticSharp (moteur prod)", new SudokuGeneticSharpSolver
    {
        PopulationSize = 500, MaxGenerations = 400, Stagnation = 80, MaxRestarts = 5
    })
};

var comparison = SudokuHelper.TestSolvers(solversToCompare, numberOfSudokus: 3, timeLimitMilliseconds: 15000);
display("Comparaison SA (Tranche 1, from scratch) vs GeneticSharp (Tranche 2, moteur production) :");
foreach (var r in comparison)
    display($"  {r.SolverName} | {r.Difficulty} | {r.Time:F0} ms | {r.SolvedCount} resolus | {r.Status}");
SudokuHelper.DisplayResults(comparison);

Running tests...

Comparaison SA (Tranche 1, from scratch) vs GeneticSharp (Tranche 2, moteur production) :

  Recuit simule (from scratch) | Easy | 3187 ms | 3 resolus | Success

  Recuit simule (from scratch) | Medium | 19760 ms | 0 resolus | Disqualified

  Recuit simule (from scratch) | Hard | 17995 ms | 0 resolus | Disqualified

  GeneticSharp (moteur prod) | Easy | 12284 ms | 1 resolus | Disqualified

  GeneticSharp (moteur prod) | Medium | 18329 ms | 0 resolus | Disqualified

  GeneticSharp (moteur prod) | Hard | 18435 ms | 0 resolus | Disqualified

Comparaison des solveurs - Medium : aucun solveur qualifie (tous disqualifies ou en timeout).

Comparaison des solveurs - Hard : aucun solveur qualifie (tous disqualifies ou en timeout).

Interpretation : GeneticSharp vs recuit simule sur Sudoku

Les deux familles metaheuristiques attaquent le meme Sudoku, mais avec des dynamiques radicalement differentes – et un constat pedagogique net : sur Sudoku, le recuit simule est typiquement plus robuste qu’un algorithme genetique standard, ce qui est un resultat etabli dans la litterature (la structure de contraintes du Sudoku favorise la recherche locale stochastique).

Recuit simule (from scratch) : une trajectoire unique qui degrade le bruit thermique au fil du temps. Le voisinage local (echange intra-bloc) decrit un paysage d’energie que la descente stochastique exploite efficacement.
Algorithme genetique (GeneticSharp) : une population d’individus combinee via crossover OX par ligne + mutation par echange intra-ligne, avec redemarrages en cas de stagnation. L’encodage par permutation de ligne est crucial : sans lui (chiffres aleatoires par cellule), le GA stagne vers ~25 conflits ; avec lui, la validite de chaque ligne est garantie par construction et le GA resout regulierement les puzzles faciles (demonstration ci-dessus). Il peut cependant rester bloque a quelques conflits pres sur certains puzzles (optimum local que les echanges intra-ligne ne suffisent pas a franchir).

Lecon d’ingenierie GeneticSharp : trois points specifiques au branchement d’un probleme contraint sur un moteur de GA.

Encodage : un encodage qui respecte structurellement les contraintes (ici, permutation par ligne) reduit l’espace de recherche de \(9^{N}\) aux permutations valides et fait converger le GA la ou l’encodage naif echoue.
Operateurs preservant la structure : crossover et mutation standard (uniformes) brisent les permutations. Il faut des operateurs sur mesure (OX par ligne, echange intra-ligne) qui preservent l’invariant – c’est l’apport specifique au-dela du moteur.
Thread-safety : GeneticSharp parallelise l’evaluation (TplTaskExecutor). Un System.Random statique partage entre threads provoque une course critique qui corrompait les permutations (erreurs >50 au lieu de ~0) ; RandomizationProvider.Current (thread-safe, fourni par GeneticSharp) est obligatoire.

Lecon lib-vs-lib : comme simanneal cote Python, GeneticSharp nous a evite de reimplmenter l’infrastructure (population, selection par elitarisme, paralllisation TPL, criteres de terminaison composes, redemarrages). Notre effort s’est concentre sur ce qui est specifique au Sudoku – encodage et operateurs preservant les permutations – exactement comme le jumeau Python se concentre sur move() / energy() en heritant du reste de Annealer. Les deux cotes atteignent maintenant un moteur de production de leur ecosysteme respectif : simanneal (framework de recuit simule) cote Python, GeneticSharp (framework d’algorithme genetique) cote C#.

Conclusion

Récapitulatif

Concept	Description
Recuit simulé	Métaheuristique d’optimisation inspiree de la métallurgie
Fonction d’énergie	Nombre de doublons dans les colonnes et blocs
Voisinage	Échange de deux cellules non fixes dans une même ligne
Acceptation de Metropolis	Accepter les degradations avec probabilité \(e^{-\Delta E / T}\)
Refroidissement	Réduction progressive de \(T\) (programme exponentiel)
Réchauffement	Remonter \(T\) en cas de stagnation

Positionnement dans la série Sudoku

Solveur	Type	Garanti	Performance
Backtracking	Recherche exhaustive	Oui	Rapide (facile), lent (difficile)
Algorithme génétique	Métaheuristique evolutionnaire	Non	Variable
OR-Tools / Z3	CSP / SMT	Oui	Très rapide
Dancing Links	Couverture exacte	Oui	Optimal
Infer.NET	Inference probabiliste	Non	Experimental
Recuit simulé	Métaheuristique locale	Non	Variable, adapte aux puzzles faciles

Points a retenir

Le recuit simulé est une approche elegante et générale qui transforme le Sudoku en problème d’optimisation
Il est moins fiable que les solveurs CSP pour le Sudoku, car la densite de solutions est très faible
Son intérêt est principalement pedagogique : il illustre comment une métaheuristique peut etre appliquee a un problème combinatoire
Les techniques d’amélioration (réchauffement, restarts) montrent les enjeux généraux de la recherche locale

Pour aller plus loin

Explorer la recherche tabou (Tabu Search) sur le Sudoku : voir Search-4 LocalSearch
Combiner recuit simulé et propagation de contraintes (hybride SA + arc-consistance)
Etudier la valeur de Shapley dans les jeux cooperatifs : voir les notebooks de la série GameTheory

Navigation : Index | << Sudoku-03-Genetic | Sudoku-08-HumanStrategies >>

Voir aussi : - Search-04-LocalSearch - Théorie du recuit simulé (Hill Climbing, SA, Tabu Search) - Sudoku-Python-SimulatedAnnealing - Version Python de ce notebook

Retour au sommet

Objectifs d’apprentissage

Prérequis

Voir aussi

Durée estimée : ~40 minutes

1. Introduction (~3 min)

Le Sudoku comme problème d’optimisation

Formulation

Critere d’acceptation de Metropolis

2. Importation de l’environnement

Sudoku-00 : Environnement et Classes de Base (C#)

Objectifs d’apprentissage

Définition de la classe SudokuGrid

Interprétation : Structure de données pour la grille Sudoku

Définition de l’interface ISudokuSolver

Interprétation : Interface de stratégie

Définition de la classe SudokuHelper

Interprétation : Infrastructure de test et benchmark

Exercice : Validation d’une grille Sudoku

Énoncé

Résumé et perspectives

Sudoku-01 : Résolution par Backtracking

Objectifs d’apprentissage

Introduction Théorique

Implémentation de l’Algorithme de Backtracking

Importation des Classes de Base

Sudoku-00 : Environnement et Classes de Base (C#)

Objectifs d’apprentissage

Définition de la classe SudokuGrid

Interprétation : Structure de données pour la grille Sudoku

Définition de l’interface ISudokuSolver

Interprétation : Interface de stratégie

Définition de la classe SudokuHelper

Interprétation : Infrastructure de test et benchmark

Exercice : Validation d’une grille Sudoku

Énoncé

Résumé et perspectives

Affichage des Puzzles de chaque Difficulté

Interprétation : Structure des Puzzles Sudoku

Code du solver en C

Classe BacktrackingDotNetSolver

Test du Solveur

Exercice : Vérifier qu’une grille est valide

Interprétation : Performance du Backtracking

Exercice : Comparer backtracking simple et MRV

Exercice (guidé) : Backtracking avec Heuristique MRV (Minimum Remaining Values)

Énoncé

Exercice : Compter le nombre de solutions

Conclusion et Analyse des Performances

Prochaines étapes

3. Fonction d’énergie (~3 min)

Principe

Implémentation

Exercice : Calculer l’énergie d’une grille partielle

Initialisation de la grille

Interprétation : initialisation

4. Voisinage : échange de cellules (~3 min)

Principe

Implémentation

Exercice : Générer un voisin par échange dans un bloc

Interprétation : voisinage par échange

5. Algorithme de recuit simulé (~5 min)

Paramètres

Algorithme

Implémentation du solveur

Premier test : puzzle facile

Interprétation : premier test

6. Tests et évaluation (~4 min)

Test sur plusieurs puzzles

Test sur des puzzles de difficulté moyenne

Interprétation : résultats des tests

Comparaison avec les autres solveurs

Exercice : Comparer les schemas de refroidissement

Interprétation : comparaison

7. Améliorations et analyse (~2 min)

Améliorations possibles

Analyse théorique

Démonstration du réchauffement

Interprétation : version avec réchauffement

8. Exemple guide

Exemple guide 1 : Expérimenter les programmes de refroidissement

Classe `BacktrackingDotNetSolver`