Navigation : Index | << Sudoku-08 C# | Sudoku-09 Python >>

Notebook 9: Résolution de Sudoku par Coloration de Graphe

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : - Modéliser un Sudoku comme un problème de coloration de graphe - Comprendre la théorie des graphes sous-jacente (81 sommets, degré 20) - Implémenter les algorithmes de coloration (Backtracking, DSATUR) - Comparer l’efficacite de différentes stratégies de coloration

Durée estimee : 30-40 minutes Prérequis : Notebook 0 (Environment), bases de théorie des graphes

Introduction : Sudoku et Théorie des Graphes

Le Sudoku peut être modélisé comme un problème de coloration de graphe :

Modélisation

Sommets : 81 cellules de la grille (9x9)
Arêtes : deux cellules sont reliées si elles ne peuvent pas avoir la même valeur
- Même ligne (8 voisins par ligne)
- Même colonne (8 voisins par colonne)
- Même bloc 3x3 (4 voisins supplémentaires, car 8-4 sont déjà comptés)
Couleurs : valeurs 1 à 9

Proprietes du graphe

Nombre de sommets : 81
Degré de chaque sommet : 20 (8 + 8 + 4)
Nombre d’arêtes : 81 * 20 / 2 = 810
Clique maximale : 9 (ligne, colonne ou bloc complet)

Cette formulation permet d’appliquer des algorithmes classiques de coloration !

// Import des classes de base
#!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.

Construction du Graphe Sudoku

Nous définissons une classe SudokuGraph qui représente le graphe d’un Sudoku : - Chaque sommet correspond a une cellule (index 0-80) - Les arêtes représentent les contraintes d’exclusion - La coloration (assignation de valeurs) doit respecter les arêtes

using System;

using System.Collections.Generic;

using System.Linq;



/// <summary>

/// Represente le graphe de contraintes d'un Sudoku.

/// 81 sommets (cellules), aretes entre cellules en conflit.

/// </summary>

public class SudokuGraph

{

    // Nombre de sommets (81 cellules)

    public const int VertexCount = 81;

    

    // Nombre de couleurs (valeurs 1-9)

    public const int ColorCount = 9;

    

    // Liste d'adjacence : adjacency[v] = liste des voisins du sommet v

    private readonly List<int>[] _adjacency;

    

    // Degre de chaque sommet

    private readonly int[] _degrees;

    

    // Grille Sudoku associee

    private readonly SudokuGrid _grid;

    

    // Cellules pre-coloriees (indices fixes)

    private readonly HashSet<int> _fixedVertices;

    

    /// <summary>

    /// Construit le graphe a partir d'une grille Sudoku.

    /// </summary>

    public SudokuGraph(SudokuGrid grid)

    {

        _grid = grid;

        _adjacency = new List<int>[VertexCount];

        _degrees = new int[VertexCount];

        _fixedVertices = new HashSet<int>();

        

        // Initialiser les listes d'adjacence

        for (int i = 0; i < VertexCount; i++)

        {

            _adjacency[i] = new List<int>();

        }

        

        // Construire les aretes a partir des contraintes Sudoku

        BuildEdges();

        

        // Identifier les cellules pre-coloriees

        IdentifyFixedVertices();

    }

    

    /// <summary>

    /// Construit les aretes du graphe.

    /// Chaque cellule est reliee a ses voisins de ligne, colonne et bloc.

    /// </summary>

    private void BuildEdges()

    {

        for (int row = 0; row < 9; row++)

        {

            for (int col = 0; col < 9; col++)

            {

                int vertex = ToVertexIndex(row, col);

                var neighbors = GetNeighborVertices(row, col);

                

                foreach (var neighbor in neighbors)

                {

                    if (!_adjacency[vertex].Contains(neighbor))

                    {

                        _adjacency[vertex].Add(neighbor);

                        _degrees[vertex]++;

                    }

                }

            }

        }

    }

    

    /// <summary>

    /// Obtient tous les sommets voisins d'une cellule.

    /// </summary>

    private HashSet<int> GetNeighborVertices(int row, int col)

    {

        var neighbors = new HashSet<int>();

        

        // Voisins de ligne

        for (int c = 0; c < 9; c++)

            if (c != col)

                neighbors.Add(ToVertexIndex(row, c));

        

        // Voisins de colonne

        for (int r = 0; r < 9; r++)

            if (r != row)

                neighbors.Add(ToVertexIndex(r, col));

        

        // Voisins de bloc 3x3

        int blockRow = (row / 3) * 3;

        int blockCol = (col / 3) * 3;

        for (int r = blockRow; r < blockRow + 3; r++)

        {

            for (int c = blockCol; c < blockCol + 3; c++)

            {

                if (r != row || c != col)

                    neighbors.Add(ToVertexIndex(r, c));

            }

        }

        

        return neighbors;

    }

    

    /// <summary>

    /// Identifie les cellules pre-coloriees (valeurs fixees).

    /// </summary>

    private void IdentifyFixedVertices()

    {

        for (int row = 0; row < 9; row++)

        {

            for (int col = 0; col < 9; col++)

            {

                if (_grid.Cells[row, col] > 0)

                {

                    _fixedVertices.Add(ToVertexIndex(row, col));

                }

            }

        }

    }

    

    // Conversion coordonnees <-> index de sommet

    public static int ToVertexIndex(int row, int col) => row * 9 + col;

    public static (int row, int col) ToCoordinates(int vertex) => (vertex / 9, vertex % 9);

    

    // Acces aux proprietes du graphe

    public IReadOnlyList<int> GetNeighbors(int vertex) => _adjacency[vertex];

    public int GetDegree(int vertex) => _degrees[vertex];

    public bool IsFixed(int vertex) => _fixedVertices.Contains(vertex);

    public int GetInitialColor(int vertex)

    {

        var (row, col) = ToCoordinates(vertex);

        return _grid.Cells[row, col];

    }

    

    /// <summary>

    /// Obtient les couleurs disponibles pour un sommet.

    /// </summary>

    public HashSet<int> GetAvailableColors(int vertex, int[] coloring)

    {

        var usedColors = new HashSet<int>();

        

        foreach (var neighbor in _adjacency[vertex])

        {

            if (coloring[neighbor] > 0)

                usedColors.Add(coloring[neighbor]);

        }

        

        var available = new HashSet<int>();

        for (int color = 1; color <= ColorCount; color++)

        {

            if (!usedColors.Contains(color))

                available.Add(color);

        }

        

        return available;

    }

    

    /// <summary>

    /// Verifie si une coloration est valide.

    /// </summary>

    public bool IsValidColoring(int[] coloring)

    {

        for (int v = 0; v < VertexCount; v++)

        {

            if (coloring[v] == 0) continue;

            

            foreach (var neighbor in _adjacency[v])

            {

                if (coloring[neighbor] == coloring[v])

                    return false;

            }

        }

        return true;

    }

    

    /// <summary>

    /// Affiche les statistiques du graphe.

    /// </summary>

    public void PrintStatistics()

    {

        int totalEdges = _degrees.Sum() / 2;

        int maxDegree = _degrees.Max();

        int minDegree = _degrees.Min();

        

        Console.WriteLine("=== Statistiques du Graphe Sudoku ===");

        Console.WriteLine($"Sommets: {VertexCount}");

        Console.WriteLine($"Aretes: {totalEdges}");

        Console.WriteLine($"Degre min: {minDegree}, max: {maxDegree}");

        Console.WriteLine($"Cellules fixees: {_fixedVertices.Count}");

        Console.WriteLine($"Cellules a colorier: {VertexCount - _fixedVertices.Count}");

    }

}

Console.WriteLine("Classe SudokuGraph definie (graphe de contraintes 81 sommets)");

Classe SudokuGraph definie (graphe de contraintes 81 sommets)

Lecture : reformuler le Sudoku en coloration

SudokuGraph change la nature du problème sans en changer une donnée : chaque cellule devient un sommet, chaque contrainte d’exclusion (deux cellules alignées ne peuvent porter le même chiffre) devient une arête, et résoudre la grille devient colorer le graphe avec 9 couleurs de façon propre — un chiffre = une couleur. Le vocabulaire change, et la difficulté aussi : là où le backtracking de Sudoku-01 choisissait des valeurs de cellules, la coloration raisonne sur des conflits entre sommets voisins. C’est ce déplacement qui rend les heuristiques de degré et de saturation (DSATUR) pensables — elles n’existent pas dans le vocabulaire grille par grille.

Exercice : Compter les contraintes par cellule

Objectif : Pour chaque cellule de la grille Sudoku, comptez le nombre de cellules contraintes (cellules dans la même ligne, colonne ou bloc).

Indice : Utilisez le graphe construit et comptez le degré de chaque noeud.

// EXERCICE : Compter les contraintes par cellule
public Dictionary<(int, int), int> CountConstraintsPerCell()
{
    // TODO: Pour chaque cellule (i,j), comptez le nombre de voisins dans le graphe
    // Retournez un dictionnaire (cellule -> nombre de contraintes)
    return null; // TODO etudiant
}

Interprétation

La classe SudokuGraph encapsule la structure du problème : - 81 sommets représentent les 81 cellules - 810 arêtes (sans doublons) représentent les contraintes - Chaque sommet a un degré 20 (8 ligne + 8 colonne + 4 bloc supplémentaires) - Les couleurs disponibles sont calculees dynamiquement selon l’etat actuel

Algorithme 1 : Coloration par Backtracking Simple

L’approche naive colorié les sommets séquentiellement : 1. Choisir le premier sommet non colorié 2. Essayer chaque couleur disponible 3. Si conflit, revenir en arrière (backtrack) 4. Répéter jusqu’a coloration complète

/// <summary>

/// Solveur par coloration de graphe avec backtracking simple.

/// </summary>

public class GraphColoringBacktracking : ISudokuSolver

{

    private int _nodesExplored;

    private int _backtracks;

    

    public int NodesExplored => _nodesExplored;

    public int Backtracks => _backtracks;

    

    public SudokuGrid Solve(SudokuGrid grid)

    {

        _nodesExplored = 0;

        _backtracks = 0;

        

        var graph = new SudokuGraph(grid);

        var coloring = new int[SudokuGraph.VertexCount];

        

        // Initialiser avec les valeurs pre-existantes

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            coloring[v] = graph.GetInitialColor(v);

        }

        

        // Lancer le backtracking

        if (BacktrackColor(graph, coloring, 0))

        {

            return ColoringToGrid(coloring, grid);

        }

        

        return grid; // Echec

    }

    

    /// <summary>

    /// Backtracking recursif pour la coloration.

    /// </summary>

    private bool BacktrackColor(SudokuGraph graph, int[] coloring, int vertex)

    {

        _nodesExplored++;

        

        // Trouver le prochain sommet a colorier

        while (vertex < SudokuGraph.VertexCount)

        {

            if (coloring[vertex] == 0) break; // Sommet non colorie

            vertex++;

        }

        

        // Tous les sommets sont colories

        if (vertex >= SudokuGraph.VertexCount)

            return true;

        

        // Obtenir les couleurs disponibles

        var availableColors = graph.GetAvailableColors(vertex, coloring);

        

        // Essayer chaque couleur

        foreach (var color in availableColors)

        {

            coloring[vertex] = color;

            

            if (BacktrackColor(graph, coloring, vertex + 1))

                return true;

            

            // Backtrack

            coloring[vertex] = 0;

            _backtracks++;

        }

        

        return false; // Aucune couleur possible

    }

    

    /// <summary>

    /// Convertit une coloration en grille Sudoku.

    /// </summary>

    private SudokuGrid ColoringToGrid(int[] coloring, SudokuGrid original)

    {

        var result = (SudokuGrid)original.Clone();

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            var (row, col) = SudokuGraph.ToCoordinates(v);

            result.Cells[row, col] = coloring[v];

        }

        return result;

    }

}

Console.WriteLine("Classe GraphColoringBacktracking definie (coloration par backtracking)");

Classe GraphColoringBacktracking definie (coloration par backtracking)

Test du Backtracking Simple

Exercice : Implémenter l’heuristique de degré (Degree Heuristic)

Objectif : Implémentez l’heuristique de degré qui, en cas d’égalité entre plusieurs variables MRV, choisit celle qui a le plus de contraintes avec les variables non assignees.

Indice : Triez les variables candidats par nombre de voisins non assignes en cas d’égalité MRV.

// EXERCICE : Implementer l'heuristique de degre
public (int Row, int Col) SelectVariableWithDegreeHeuristic(int[,] grid, bool[,] isFixed)
{
    // TODO: Selectionnez la cellule non assignee avec le plus petit domaine (MRV)
    // En cas d'egalite, choisissez celle avec le plus de voisins non assignes
    return (-1, -1); // TODO etudiant
}

// Test avec un Sudoku facile
var easySudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
Console.WriteLine($"Sudoku original:\n{easySudoku}");

var solver = new GraphColoringBacktracking();
var stopwatch = System.Diagnostics.Stopwatch.StartNew();
var solved = solver.Solve(easySudoku);
stopwatch.Stop();

Console.WriteLine($"\nSudoku resolu:\n{solved}");
Console.WriteLine($"\nStatistiques:");
Console.WriteLine($"  Noeuds explores: {solver.NodesExplored}");
Console.WriteLine($"  Backtracks: {solver.Backtracks}");
Console.WriteLine($"  Temps: {stopwatch.Elapsed.TotalMilliseconds:F2} ms");
Console.WriteLine($"  Valide: {solved.IsValid(easySudoku)}");

Sudoku original:
-------------------------------
| 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 resolu:
-------------------------------
| 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 | 
-------------------------------

Statistiques:
  Noeuds explores: 49
  Backtracks: 12
  Temps: 4,43 ms
  Valide: True

Interprétation : Test Backtracking Simple

Sortie obtenue : Le backtracking simple résout un Sudoku facile avec 49 noeuds explorés et 12 backtracks (temps de résolution mesuré par Stopwatch : voir la sortie de la cellule ci-dessus).

Aspect	Valeur	Signification
Noeuds explorés	49	Arbre de recherche limite (sur 81 cellules)
Backtracks	12	Taux de succès de 75% (37 assignations correctes du premier coup)
Validité	True	Solution correcte

Points clés : 1. Le backtracking simple fonctionne bien sur les Sudokus faciles grace aux nombreuses valeurs initiales 2. Le taux de backtrack (12/49 = 24%) reste raisonnable pour cette instance 3. La solution est valide et complète 4. Cette approche servira de baseline pour comparer les heuristiques plus avancees

Note technique : Le nombre de noeuds explorés (49) est nettement inferieur au nombre total de cellules (81), car les valeurs initiales reduisent l’espace de recherche. Chaque backtrack représente un essai de couleur qui a mene a une impasse, necessitant de revenir en arrière pour essayer une autre couleur. Sur des Sudokus plus difficiles, ce nombre augmente exponentiellement.

Algorithme 2 : Coloration avec Heuristique MRV

L’heuristique MRV (Minimum Remaining Values) choisit le sommet avec le moins de couleurs disponibles. Cela réduit l’arbre de recherche en detectant les échecs plus tot.

/// <summary>

/// Solveur par coloration avec heuristique MRV.

/// Choisit le sommet avec le moins de couleurs disponibles.

/// </summary>

public class GraphColoringMRV : ISudokuSolver

{

    private int _nodesExplored;

    private int _backtracks;

    

    public int NodesExplored => _nodesExplored;

    public int Backtracks => _backtracks;

    

    public SudokuGrid Solve(SudokuGrid grid)

    {

        _nodesExplored = 0;

        _backtracks = 0;

        

        var graph = new SudokuGraph(grid);

        var coloring = new int[SudokuGraph.VertexCount];

        

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            coloring[v] = graph.GetInitialColor(v);

        }

        

        if (BacktrackMRV(graph, coloring))

        {

            return ColoringToGrid(coloring, grid);

        }

        

        return grid;

    }

    

    /// <summary>

    /// Selectionne le sommet avec le moins de couleurs disponibles (MRV).

    /// </summary>

    private int SelectVertexMRV(SudokuGraph graph, int[] coloring)

    {

        int bestVertex = -1;

        int minColors = int.MaxValue;

        

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            if (coloring[v] != 0) continue; // Deja colorie

            

            var available = graph.GetAvailableColors(v, coloring);

            if (available.Count < minColors)

            {

                minColors = available.Count;

                bestVertex = v;

            }

        }

        

        return bestVertex;

    }

    

    private bool BacktrackMRV(SudokuGraph graph, int[] coloring)

    {

        _nodesExplored++;

        

        // Choisir le sommet avec MRV

        int vertex = SelectVertexMRV(graph, coloring);

        

        // Tous les sommets sont colories

        if (vertex == -1)

            return true;

        

        var availableColors = graph.GetAvailableColors(vertex, coloring);

        

        // Echec si aucune couleur disponible

        if (availableColors.Count == 0)

            return false;

        

        foreach (var color in availableColors)

        {

            coloring[vertex] = color;

            

            if (BacktrackMRV(graph, coloring))

                return true;

            

            coloring[vertex] = 0;

            _backtracks++;

        }

        

        return false;

    }

    

    private SudokuGrid ColoringToGrid(int[] coloring, SudokuGrid original)

    {

        var result = (SudokuGrid)original.Clone();

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            var (row, col) = SudokuGraph.ToCoordinates(v);

            result.Cells[row, col] = coloring[v];

        }

        return result;

    }

}

Console.WriteLine("Classe GraphColoringMRV definie (coloration avec heuristique MRV)");

Classe GraphColoringMRV definie (coloration avec heuristique MRV)

Lecture : MRV — commencer par la cellule la plus contrainte

L’heuristique MRV (Minimum Remaining Values) réordonne une seule chose : le choix du prochain sommet à colorer. Au lieu de parcourir les cellules dans un ordre fixe, elle traite d’abord celle dont le domaine de couleurs encore possibles est le plus petit. L’intuition : une cellule presque forcée — une seule couleur possible — est une décision gratuite à prendre maintenant, et chaque décision prise réduit les domaines des voisins, révélant plus tôt les impasses. Le benchmark mesurera l’effet exactement : moins de nœuds, et surtout beaucoup moins de backtracks, car les branches stériles sont démasquées quand elles sont encore courtes.

Algorithme 3 : DSATUR (Degree of Saturation)

DSATUR est une heuristique de coloration efficace et largement utilisée. Il utilisé : - Degré de saturation : nombre de couleurs différentes dans le voisinage - Tie-breaker : choisir le sommet avec le plus haut degré en cas d’égalité

Cette heuristique est particulièrement efficace pour les graphes réguliers comme le Sudoku.

/// <summary>

/// Solveur DSATUR (Degree of Saturation).

/// Heuristique optimale pour la coloration de graphes.

/// </summary>

public class GraphColoringDSATUR : ISudokuSolver

{

    private int _nodesExplored;

    private int _backtracks;

    

    public int NodesExplored => _nodesExplored;

    public int Backtracks => _backtracks;

    

    public SudokuGrid Solve(SudokuGrid grid)

    {

        _nodesExplored = 0;

        _backtracks = 0;

        

        var graph = new SudokuGraph(grid);

        var coloring = new int[SudokuGraph.VertexCount];

        

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

            coloring[v] = graph.GetInitialColor(v);

        

        if (BacktrackDSATUR(graph, coloring))

            return ColoringToGrid(coloring, grid);

        

        return grid;

    }

    

    /// <summary>

    /// Calcule le degre de saturation d'un sommet.

    /// Saturation = nombre de couleurs differentes dans le voisinage.

    /// </summary>

    private int CalculateSaturation(SudokuGraph graph, int vertex, int[] coloring)

    {

        var neighborColors = new HashSet<int>();

        

        foreach (var neighbor in graph.GetNeighbors(vertex))

        {

            if (coloring[neighbor] > 0)

                neighborColors.Add(coloring[neighbor]);

        }

        

        return neighborColors.Count;

    }

    

    /// <summary>

    /// Selectionne le sommet avec la plus haute saturation.

    /// Tie-breaker : plus haut degre.

    /// </summary>

    private int SelectVertexDSATUR(SudokuGraph graph, int[] coloring)

    {

        int bestVertex = -1;

        int maxSaturation = -1;

        int maxDegree = -1;

        

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            if (coloring[v] != 0) continue;

            

            int saturation = CalculateSaturation(graph, v, coloring);

            int degree = graph.GetDegree(v);

            

            // Comparaison : maximiser saturation, puis degre

            if (saturation > maxSaturation || 

                (saturation == maxSaturation && degree > maxDegree))

            {

                maxSaturation = saturation;

                maxDegree = degree;

                bestVertex = v;

            }

        }

        

        return bestVertex;

    }

    

    private bool BacktrackDSATUR(SudokuGraph graph, int[] coloring)

    {

        _nodesExplored++;

        

        int vertex = SelectVertexDSATUR(graph, coloring);

        

        if (vertex == -1)

            return true;

        

        var availableColors = graph.GetAvailableColors(vertex, coloring);

        

        if (availableColors.Count == 0)

            return false;

        

        // Trier les couleurs par frequence decroissante (heuristique LCV)

        var sortedColors = availableColors

            .OrderByDescending(c => CountColorUsage(c, graph, coloring))

            .ToList();

        

        foreach (var color in sortedColors)

        {

            coloring[vertex] = color;

            

            if (BacktrackDSATUR(graph, coloring))

                return true;

            

            coloring[vertex] = 0;

            _backtracks++;

        }

        

        return false;

    }

    

    /// <summary>

    /// Compte l'utilisation d'une couleur dans le voisinage.

    /// </summary>

    private int CountColorUsage(int color, SudokuGraph graph, int[] coloring)

    {

        int count = 0;

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            if (coloring[v] == color)

                count++;

        }

        return count;

    }

    

    private SudokuGrid ColoringToGrid(int[] coloring, SudokuGrid original)

    {

        var result = (SudokuGrid)original.Clone();

        for (int v = 0; v < SudokuGraph.VertexCount; v++)

        {

            var (row, col) = SudokuGraph.ToCoordinates(v);

            result.Cells[row, col] = coloring[v];

        }

        return result;

    }

}

Console.WriteLine("Classe GraphColoringDSATUR definie (coloration DSATUR)");

Classe GraphColoringDSATUR definie (coloration DSATUR)

Lecture : DSATUR — suivre la saturation, pas seulement le domaine

DSATUR raffine MRV d’un cran : le prochain sommet est celui de plus forte saturation — le plus grand nombre de couleurs différentes déjà portées par ses voisins — à égalité, le plus haut degré. La nuance est réelle : deux cellules peuvent avoir autant de couleurs disponibles l’une que l’autre, mais si les voisins de la première n’utilisent qu’une couleur alors que ceux de la seconde en étalent six, c’est la seconde qu’il est dangereux de différer. DSATUR regarde la diversité de la pression, pas seulement son intensité. C’est aussi une heuristique classique de coloration de graphes en général — le Sudoku n’est ici qu’un terrain d’application.

Benchmark : Comparaison des Algorithmes

using System.Collections.Generic;



/// <summary>

/// Resultat d'un test de solveur.

/// </summary>

public record SolverResult(

    string Name,

    bool Success,

    double TimeMs,

    int NodesExplored,

    int Backtracks

);



/// <summary>

/// Teste plusieurs solveurs de coloration.

/// </summary>

public List<SolverResult> BenchmarkSolvers(List<SudokuGrid> sudokus, int limit = 5)

{

    var results = new List<SolverResult>();

    

    var solvers = new List<(string Name, Func<ISudokuSolver> Factory, Func<ISudokuSolver, int> GetNodes, Func<ISudokuSolver, int> GetBacktracks)>

    {

        ("Backtracking Simple", () => new GraphColoringBacktracking(), s => ((GraphColoringBacktracking)s).NodesExplored, s => ((GraphColoringBacktracking)s).Backtracks),

        ("MRV Heuristic", () => new GraphColoringMRV(), s => ((GraphColoringMRV)s).NodesExplored, s => ((GraphColoringMRV)s).Backtracks),

        ("DSATUR", () => new GraphColoringDSATUR(), s => ((GraphColoringDSATUR)s).NodesExplored, s => ((GraphColoringDSATUR)s).Backtracks)

    };

    

    foreach (var (name, factory, getNodes, getBacktracks) in solvers)

    {

        int successCount = 0;

        long totalTime = 0;

        int totalNodes = 0;

        int totalBacktracks = 0;

        

        foreach (var sudoku in sudokus.Take(limit))

        {

            var solver = factory();

            var sw = System.Diagnostics.Stopwatch.StartNew();

            var solved = solver.Solve(sudoku);

            sw.Stop();

            

            if (solved.IsValid(sudoku))

            {

                successCount++;

                totalTime += sw.ElapsedMilliseconds;

                totalNodes += getNodes(solver);

                totalBacktracks += getBacktracks(solver);

            }

        }

        

        results.Add(new SolverResult(

            name,

            successCount == limit,

            successCount > 0 ? (double)totalTime / successCount : -1,

            totalNodes / Math.Max(1, successCount),

            totalBacktracks / Math.Max(1, successCount)

        ));

    }

    

    return results;

}

Console.WriteLine("Classes SolverResult + BenchmarkSolvers definies (framework de benchmark)");

Classes SolverResult + BenchmarkSolvers definies (framework de benchmark)

Lecture : un benchmark, quatre colonnes

Le framework de benchmark fixe le protocole avant de produire un chiffre : mêmes grilles pour tous, succès compté, temps moyen, nœuds et backtracks cumulés. Cette discipline est ce qui rend les tableaux suivants interprétables : un temps seul ne dit rien (machine, charge), un temps relié à son nombre de nœuds dit si l’algorithme visite moins ou traverse plus vite. Retenez aussi la limite du protocole : « temps moyen » sur 5 grilles faciles puis 3 difficiles — la difficulté Sudoku n’est pas une échelle linéaire, et les moyennes cachent les écarts par grille.

Exécution du benchmark de coloration de graphe.

Exercice : Verifier qu’une coloration est valide

Objectif : Implémentez une fonction qui vérifie si une grille complètement remplie est une solution valide du Sudoku en utilisant le graphe.

Indice : Pour chaque arête du graphe, verifiez que les deux noeuds ont des couleurs différentes.

// EXERCICE : Verifier qu'une coloration est valide
public bool IsColoringValid(int[,] solution)
{
    // TODO: Verifiez que pour chaque paire de cellules contraintes,
    // les valeurs sont differentes
    return false; // TODO etudiant
}

// Execution du benchmark
Console.WriteLine("=== Benchmark : Coloration de Graphe pour Sudoku ===\n");

// Test sur Sudokus faciles
var easySudokus = SudokuHelper.GetSudokus(SudokuDifficulty.Easy);
Console.WriteLine($"Test sur {Math.Min(5, easySudokus.Count)} Sudokus faciles...\n");

var easyResults = BenchmarkSolvers(easySudokus, 5);

Console.WriteLine("| Algorithme | Succes | Temps Moy (ms) | Noeuds | Backtracks |");
Console.WriteLine("|------------|--------|----------------|--------|------------|");
foreach (var r in easyResults)
{
    Console.WriteLine($"| {r.Name,-20} | {(r.Success ? "OK" : "ECHEC")} | {r.TimeMs,14:F2} | {r.NodesExplored,6} | {r.Backtracks,10} |");
}

=== Benchmark : Coloration de Graphe pour Sudoku ===

Test sur 5 Sudokus faciles...

| Algorithme | Succes | Temps Moy (ms) | Noeuds | Backtracks |
|------------|--------|----------------|--------|------------|
| Backtracking Simple  | OK |           3,60 |   4250 |       4201 |
| MRV Heuristic        | OK |           1,40 |     63 |         14 |
| DSATUR               | OK |           4,00 |     74 |         25 |

Interprétation : Benchmark Sudokus Faciles

Sortie obtenue : Les trois algorithmes resolvent les Sudokus faciles avec succès, mais avec des performances notablement différentes (temps moyens mesurés : voir la sortie de la cellule ci-dessus).

Algorithme	Noeuds explorés	Backtracks	Noeuds vs baseline
Backtracking Simple	4 250	4 201	1x (reference)
MRV Heuristic	63	14	~67x moins de noeuds
DSATUR	74	25	~57x moins de noeuds

Points clés : 1. MRV le plus efficace : Reduction de 98,5% de l’espace de recherche (4250 -> 63 noeuds) 2. DSATUR performant : ~57x moins de noeuds explorés que le backtracking simple 3. Backtracking simple acceptable : Sur les Sudokus faciles, même l’approche naive termine ces instances sans explosion combinatoire 4. Toutes les solutions sont valides (100% de succès)

Note technique : Sur les Sudokus faciles, l’heuristique MRV est particulièrement efficace car les nombreuses valeurs initiales créent rapidement des sommets avec une seule couleur disponible (singletons). MRV detecte ces cas immediatement et les propage, reduisant drastiquement l’arbre de recherche. DSATUR a un surcout de calcul (calcul de la saturation a chaque itération) qui est moins justifie sur des instances simples : il explore moins de noeuds que le backtracking naif mais reste derriere MRV ici. Cet ordre s’inverse sur les Sudokus difficiles (voir plus bas).

Test de la coloration de graphe sur les puzzles Sudoku difficiles.

// Test sur Sudokus difficiles
var hardSudokus = SudokuHelper.GetSudokus(SudokuDifficulty.Hard);
Console.WriteLine($"\nTest sur {Math.Min(3, hardSudokus.Count)} Sudokus difficiles...\n");

var hardResults = BenchmarkSolvers(hardSudokus, 3);

Console.WriteLine("| Algorithme | Succes | Temps Moy (ms) | Noeuds | Backtracks |");
Console.WriteLine("|------------|--------|----------------|--------|------------|");
foreach (var r in hardResults)
{
    Console.WriteLine($"| {r.Name,-20} | {(r.Success ? "OK" : "ECHEC")} | {r.TimeMs,14:F2} | {r.NodesExplored,6} | {r.Backtracks,10} |");
}


Test sur 3 Sudokus difficiles...

| Algorithme | Succes | Temps Moy (ms) | Noeuds | Backtracks |
|------------|--------|----------------|--------|------------|
| Backtracking Simple  | OK |        3842,00 | 4356440 |    4356375 |
| MRV Heuristic        | OK |          33,67 |   1406 |       1341 |
| DSATUR               | OK |          25,67 |   1202 |       1137 |

Interprétation : Benchmark Sudokus Difficiles

Sortie obtenue : Les résultats montrent une différence spectaculaire entre les algorithmes sur les Sudokus difficiles (temps moyens mesurés : voir la sortie de la cellule ci-dessus).

Algorithme	Noeuds explorés	Backtracks	Noeuds vs baseline
Backtracking Simple	4 356 440	4 356 375	1x (baseline)
MRV Heuristic	1 406	1 341	~3 100x moins de noeuds
DSATUR	1 202	1 137	~3 600x moins de noeuds

Points clés : 1. Backtracking simple : Explosion combinatoire sur les instances difficiles (4,3 millions de noeuds) 2. DSATUR meilleur performer ici : le moins de noeuds explorés (1 202) ET le temps de résolution le plus court des trois (voir sortie ci-dessus) 3. MRV très proche : 1 406 noeuds, juste derriere DSATUR sur ce benchmark difficile 4. L’ecart avec le backtracking se creuse considerablement avec la difficulté (de ~3 100x a ~3 600x en nombre de noeuds explorés)

Note technique : Sur les Sudokus difficiles (peu de valeurs initiales), le degré de saturation de DSATUR devient discriminant : choisir le sommet dont le voisinage utilisé le plus de couleurs distinctes oriente la recherche vers les zones les plus contraintes, ce qui minimise le nombre de noeuds explorés (1 202, le plus bas des trois). DSATUR amortit alors son surcout de calcul de saturation et passe devant MRV – l’inverse du cas facile, ou ce surcout n’etait pas justifie. Les deux heuristiques restent plusieurs ordres de grandeur plus efficaces que le backtracking naif.

Complexité des trois approches :

Algorithme	Complexité	Avantages	Inconvénients
Backtracking Simple	O(9^81) théorique	Simple a implémenter	Très lent sans heuristique
MRV	O(9^n) avec n < 81	Detecte échecs rapidement	Ordonnancement statique
DSATUR	O(n^2) par itération	Très efficace sur graphes réguliers	Plus complexe

Intégration au Framework Sudoku

// Test d'integration avec SudokuHelper (+ mesure du temps de resolution)
Console.WriteLine("=== Test d'integration avec SudokuHelper ===\n");

var dsaturSolver = new GraphColoringDSATUR();
var sw = System.Diagnostics.Stopwatch.StartNew();
SudokuHelper.SolveSudoku(easySudokus.First(), dsaturSolver);
sw.Stop();
Console.WriteLine($"\nTemps de resolution DSATUR : {sw.Elapsed.TotalMilliseconds:F4} ms");

=== Test d'integration avec SudokuHelper ===

Résolution par le solver GraphColoringDSATUR 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: 0,6938 ms


Temps de resolution DSATUR : 7,9640 ms

Interprétation : Intégration DSATUR

Sortie obtenue : Le solveur DSATUR résout le Sudoku facile via SudokuHelper.SolveSudoku avec 0 erreurs ; la grille renvoyée est complète et respecte toutes les contraintes du Sudoku (aucun conflit). Le chronomètre Stopwatch mesure le temps réel de résolution — machine-dépendant, volontairement non épinglé en prose (source : sortie de la cellule ci-dessus).

Aspect	Valeur	Signification
Erreurs restantes	0	Solution valide et complète
Algorithme	DSATUR	Heuristique de degré de saturation

Points clés : 1. L’intégration avec SudokuHelper fonctionne correctement 2. La conversion graphe → grille Sudoku est transparente 3. DSATUR maintient ses bonnes performances dans le framework Sudoku

Note technique : La classe GraphColoringDSATUR implémente l’interface ISudokuSolver, ce qui permet une intégration sans friction avec le framework existant. La méthode SolveSudoku de SudokuHelper encapsule la logique de validation automatique.

Exercices

Exercice 1 : Coloration Gloutonne

Implémentez un algorithme glouton qui colorie les sommets dans l’ordre sans backtracking :

public class GraphColoringGreedy : ISudokuSolver { ... }

Question : Pourquoi cette approche ne peut-elle pas résoudre un Sudoku ?

Exercice 2 : Propagation de Contraintes

Ajoutez une étape de propagation après chaque assignation : - Si un voisin n’a plus qu’une couleur disponible, l’assigner - Propager récursivement jusqu’a stabilité

Exercice 3 : Visualisation du Graphe

Utilisez Plotly.NET pour visualiser le graphe de coloration avec les couleurs assignees.

Indice : Utilisez un layout circulaire pour les 81 sommets.

// Exemple guide 1 : Coloration Gloutonne
// Implementez un solveur glouton sans backtracking.
// Question : pourquoi cette approche ne peut-elle pas resoudre un Sudoku en general ?

public class GraphColoringGreedy : ISudokuSolver
{
    public SudokuGrid Solve(SudokuGrid grid)
    {
        var graph = new SudokuGraph(grid);
        var coloring = new int[SudokuGraph.VertexCount];
        
        for (int v = 0; v < SudokuGraph.VertexCount; v++)
            coloring[v] = graph.GetInitialColor(v);
        
        // TODO : Parcourir les sommets dans l'ordre fixe (0 a 80)
        // Pour chaque sommet non colorie, choisir la premiere couleur disponible
        // Si aucune couleur disponible -> retourner la grille incomplete
        // (pas de backtracking !)
        return grid;  // TODO etudiant : implementer la coloration gloutonne
    }
}

// Exemple guide 2 : Propagation de Contraintes
// Ajoutez une propagation apres chaque assignation.

public class GraphColoringWithPropagation : ISudokuSolver
{
    public SudokuGrid Solve(SudokuGrid grid)
    {
        var graph = new SudokuGraph(grid);
        var coloring = new int[SudokuGraph.VertexCount];
        
        for (int v = 0; v < SudokuGraph.VertexCount; v++)
            coloring[v] = graph.GetInitialColor(v);
        
        // TODO : Implementer la propagation de contraintes
        // Apres chaque assignation, verifier les voisins :
        // - Si un voisin a exactement 1 couleur disponible, l'assigner
        // - Propager recursivement jusqu'a stabilite
        // Combiner avec MRV pour la selection des sommets
        return grid;  // TODO etudiant : implementer la coloration gloutonne
    }
}

Console.WriteLine("Exercices de coloration de graphe a implementer !");

Exercices de coloration de graphe a implementer !

Graphe Sudoku via QuikGraph (moteur .NET natif)

La section précédente construit le graphe de contraintes Sudoku à la main (class SudokuGraph, liste d’adjacence List<int>[]). Le jumeau Python, lui, délègue cette construction à networkx via nx.sudoku_graph() — un générateur qui produit directement le graphe 81 sommets / 810 arêtes avec les contraintes ligne / colonne / bloc.

QuikGraph est l’équivalent .NET de networkx : une bibliothèque de structures de graphe et d’algorithmes (parcours, plus courts chemins, composantes connexes, flot maximum). On refait ici la construction du graphe de contraintes en déléguant la structure à QuikGraph — UndirectedGraph<int, Edge<int>> — et on invoque un vrai algorithme de la librairie (composantes connexes) sur ce graphe. Les algorithmes de coloration (Backtracking / MRV / DSATUR) restent écrits à la main : de part et d’autre, networkx comme QuikGraph fournissent la structure, la coloration étant écrite au-dessus (le jumeau Python hand-écrit lui aussi son backtracking/MRV/DSATUR sur le graphe networkx).

Parité lib-vs-lib : Python délègue la structure à networkx ; C# délègue la structure à QuikGraph. Même graphe de contraintes (81/810), mêmes algorithmes de coloration au-dessus.

// Tranche 2 : QuikGraph 2.5.0 (moteur .NET natif) — le graphe de contraintes Sudoku delegue a une lib .NET.
// Le jumeau Python construit ce meme graphe via nx.sudoku_graph() (networkx) ; QuikGraph est
// l'equivalent .NET (structure de graphe + algorithmes de connectivite / parcours).
#r "nuget: QuikGraph, 2.5.0"
using QuikGraph;
using QuikGraph.Algorithms.ConnectedComponents;

// (1) Construction du graphe de contraintes dans QuikGraph.UndirectedGraph.
//     81 sommets (cellules) ; arete (u,v) si meme ligne, colonne ou bloc 3x3.
var g = new UndirectedGraph<int, Edge<int>>();
for (int v = 0; v < 81; v++) g.AddVertex(v);

int Idx(int r, int c) => r * 9 + c;
foreach (int v in g.Vertices)
{
    int row = v / 9, col = v % 9;
    var neigh = new HashSet<int>();
    for (int c = 0; c < 9; c++) if (c != col) neigh.Add(Idx(row, c));        // ligne
    for (int r = 0; r < 9; r++) if (r != row) neigh.Add(Idx(r, col));        // colonne
    int br = (row / 3) * 3, bc = (col / 3) * 3;                              // bloc 3x3
    for (int r = br; r < br + 3; r++)
        for (int c = bc; c < bc + 3; c++)
            if (r != row || c != col) neigh.Add(Idx(r, c));
    foreach (int n in neigh)
        if (v < n) g.AddEdge(new Edge<int>(v, n));   // v < n => chaque arete ajoutee une seule fois
}

Console.WriteLine("=== Tranche 2 : Graphe Sudoku via QuikGraph (moteur .NET natif) ===");
Console.WriteLine($"Sommets : {g.VertexCount}    (nx.sudoku_graph() = 81)");
Console.WriteLine($"Aretes  : {g.EdgeCount}   (nx.sudoku_graph() = 810)");
Console.WriteLine($"Degre uniforme : {g.AdjacentDegree(0)}   (chaque cellule a 20 conflits)");

// (2) Algorithme QuikGraph : composantes connexes.
//     Graphe de contraintes connexe => tout conflit se propage a l'ensemble du Sudoku.
var cc = new ConnectedComponentsAlgorithm<int, Edge<int>>(g);
cc.Compute();
Console.WriteLine($"Composantes connexes (algo QuikGraph) : {cc.ComponentCount}   (graphe connexe)");

// (3) Verification d'une coloration propre SUR la structure QuikGraph.
//     On resout un Sudoku avec le DSATUR de la tranche 1, puis on verifie via le parcours
//     des aretes QuikGraph qu'aucune arete ne relie deux sommets de meme couleur.
var puzzle = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
var solved = new GraphColoringDSATUR().Solve(puzzle);
int[] coloring = new int[81];
for (int r = 0; r < 9; r++)
    for (int c = 0; c < 9; c++)
        coloring[Idx(r, c)] = solved.Cells[r, c];

int conflicts = 0;
foreach (var e in g.Edges)
    if (coloring[e.Source] == coloring[e.Target]) conflicts++;
Console.WriteLine($"Verification coloration (parcours QuikGraph g.Edges) : {conflicts} conflit(s) / {g.EdgeCount} aretes");
Console.WriteLine($"Coloration propre : {(conflicts == 0 ? "OUI" : "NON")}   (DSATUR sur structure QuikGraph = valide)");

Installing Packages

QuikGraph

=== Tranche 2 : Graphe Sudoku via QuikGraph (moteur .NET natif) ===
Sommets : 81    (nx.sudoku_graph() = 81)
Aretes  : 810   (nx.sudoku_graph() = 810)
Degre uniforme : 20   (chaque cellule a 20 conflits)
Composantes connexes (algo QuikGraph) : 1   (graphe connexe)
Verification coloration (parcours QuikGraph g.Edges) : 0 conflit(s) / 810 aretes
Coloration propre : OUI   (DSATUR sur structure QuikGraph = valide)

Lecture : le graphe vérifié par le moteur .NET — et le degré `20` décomposé

Cette section rebâtit le graphe sur QuikGraph, la bibliothèque de graphes de référence du monde .NET, et la sortie réconcilie tout : 81 sommets et 810 arêtes — exactement les valeurs du jumeau Python nx.sudoku_graph() citées en regard. Le degré uniforme 20 se décompose proprement : chaque cellule entre en conflit avec ses 8 congénères de ligne, ses 8 de colonne, et 4 de son bloc 3x3 que ligne et colonne n’ont pas déjà couverts (20 = 8 + 8 + 4) ; et 81 x 20 / 2 = 810 arêtes, chaque arête comptée deux fois. La composante unique confirme un graphe connexe : aucune région du Sudoku n’est résoluble isolément. Enfin la vérification finale — 0 conflit sur les 810 arêtes — est la preuve par le graphe que la coloration DSATUR est propre, contrôle indépendant du solveur qui l’a produite.

Conclusion

Dans ce notebook, nous avons :

Modelise le Sudoku comme un problème de coloration de graphe (81 sommets, degré 20)
Implémenté trois algorithmes de coloration :
- Backtracking simple (baseline)
- MRV (Minimum Remaining Values)
- DSATUR (Degree of Saturation)
Compare leurs performances sur différentes difficultés

Connexions avec d’autres approches

Notebook	Lien conceptuel
Sudoku-06-AIMA-CSP	CSP = coloration avec variables/domaines/contraintes
Sudoku-07-Norvig	Propagation similaire a la réduction de domaine
CSP-1-Fondamentaux	Théorie générale des CSP

Retour au sommaire : Index Sudoku

Retour au sommet

Notebook 9: Résolution de Sudoku par Coloration de Graphe

Objectifs d’apprentissage

Introduction : Sudoku et Théorie des Graphes

Modélisation

Proprietes du graphe

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

Construction du Graphe Sudoku

Lecture : reformuler le Sudoku en coloration

Exercice : Compter les contraintes par cellule

Interprétation

Algorithme 1 : Coloration par Backtracking Simple

Test du Backtracking Simple

Exercice : Implémenter l’heuristique de degré (Degree Heuristic)

Interprétation : Test Backtracking Simple

Algorithme 2 : Coloration avec Heuristique MRV

Lecture : MRV — commencer par la cellule la plus contrainte

Algorithme 3 : DSATUR (Degree of Saturation)

Lecture : DSATUR — suivre la saturation, pas seulement le domaine

Benchmark : Comparaison des Algorithmes

Lecture : un benchmark, quatre colonnes

Exercice : Verifier qu’une coloration est valide

Interprétation : Benchmark Sudokus Faciles

Interprétation : Benchmark Sudokus Difficiles

Intégration au Framework Sudoku

Interprétation : Intégration DSATUR

Exercices

Exercice 1 : Coloration Gloutonne

Exercice 2 : Propagation de Contraintes

Exercice 3 : Visualisation du Graphe

Graphe Sudoku via QuikGraph (moteur .NET natif)

Lecture : le graphe vérifié par le moteur .NET — et le degré 20 décomposé

Conclusion

Connexions avec d’autres approches

Lecture : le graphe vérifié par le moteur .NET — et le degré `20` décomposé