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

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.IO;
using System.Linq;
using System.Text;

#r "nuget: Plotly.NET, 5.1.0"

The below script needs to be able to find the current output cell; this is an easy method to get it.

Installed Packages

• Plotly.NET, 5.1.0

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.

using System.Collections.ObjectModel;
using System.IO;
public class SudokuGrid : ICloneable
{
    // Méthodes utilitaires

    // Méthode pour convertir un tableau 1D en tableau de tableaux 1D (jagged array)
    public static T[][] ToJaggedArray<T>(IList<T> source, int columnLength)
    {
        return source
            .Select((value, index) => new { value, index })
            .GroupBy(x => x.index / columnLength)
            .Select(g => g.Select(x => x.value).ToArray())
            .ToArray();
    }

    // Méthode pour aplatir un tableau 2D en un tableau 1D
    public static T[] Flatten<T>(T[][] source) => source.SelectMany(x => x).ToArray();

    // Méthode pour convertir un tableau de tableaux 1D (jagged array) en un tableau 2D
    public static T[,] To2D<T>(T[][] source)
    {
        int rowLength = source.Length;
        int colLength = source[0].Length;
        var result = new T[rowLength, colLength];

        for (int row = 0; row < rowLength; row++)
            for (int col = 0; col < colLength; col++)
                result[row, col] = source[row][col];

        return result;
    }

    // Méthode pour convertir un tableau 2D en un tableau de tableaux 1D (jagged array)
    public static T[][] ToJaggedArray<T>(T[,] source)
    {
        int rows = source.GetLength(0);
        int cols = source.GetLength(1);
        var result = new T[rows][];

        for (int i = 0; i < rows; i++)
        {
            result[i] = new T[cols];
            for (int j = 0; j < cols; j++)
                result[i][j] = source[i, j];
        }

        return result;
    }

    // Collection d'indices pour itérer sur les voisins
    public static readonly ReadOnlyCollection<int> NeighbourIndices = new(Enumerable.Range(0, 9).ToList());

    // Définition des voisins par ligne, colonne et boîte
    private static readonly (int row, int column)[][] LineNeighbours = NeighbourIndices.Select(r => NeighbourIndices.Select(c => (r, c)).ToArray()).ToArray();
    private static readonly (int row, int column)[][] ColumnNeighbours = NeighbourIndices.Select(c => NeighbourIndices.Select(r => (r, c)).ToArray()).ToArray();
    private static readonly (int row, int column)[][] BoxNeighbours = GetBoxNeighbours();
    public static readonly (int row, int column)[][] AllNeighbours = LineNeighbours.Concat(ColumnNeighbours).Concat(BoxNeighbours).ToArray();

    // Calcul des voisins par boîte
    private static (int row, int column)[][] GetBoxNeighbours()
    {
        var result = new (int row, int column)[9][];

        for (int box = 0; box < 9; box++)
        {
            var cells = new List<(int, int)>();
            int startRow = (box / 3) * 3;
            int startCol = (box % 3) * 3;

            for (int row = startRow; row < startRow + 3; row++)
                for (int col = startCol; col < startCol + 3; col++)
                    cells.Add((row, col));

            result[box] = cells.ToArray();
        }

        return result;
    }

    // Tableau des voisins pour chaque cellule
    public static readonly (int row, int column)[][][] CellNeighbours = NeighbourIndices
        .Select(row => NeighbourIndices
            .Select(col => AllNeighbours
                .Where(neighbourhood => neighbourhood.Contains((row, col)))
                .SelectMany(n => n)
                .Where(pos => pos != (row, col))
                .Distinct()
                .ToArray())
            .ToArray())
        .ToArray();

    // Constructeur par défaut
    public SudokuGrid() { }

    // Grille de Sudoku
    public int[,] Cells { get; set; } = new int[9, 9];

    // Représentation de la grille sous forme de chaîne de caractères
    public override string ToString()
    {
        var output = new StringBuilder();
        var lineSep = new string('-', 31);
        var blankSep = new string(' ', 8);

        for (int row = 0; row < 9; row++)
        {
            output.Append(row % 3 == 0 ? lineSep + "\n" : "");
            output.Append("| ");
            for (int col = 0; col < 9; col++)
            {
                output.Append(Cells[row, col] > 0 ? Cells[row, col].ToString() : " ");
                output.Append((col + 1) % 3 == 0 ? " | " : "  ");
            }
            output.Append("\n");
        }
        output.Append(lineSep);

        return output.ToString();
    }

    // Méthode pour obtenir les numéros disponibles pour une cellule donnée
    public int[] GetAvailableNumbers(int x, int y)
    {
        if (x < 0 || x >= 9 || y < 0 || y >= 9)
            throw new ApplicationException("Invalid Coordinates");

        bool[] used = new bool[9];
        foreach (var (row, col) in CellNeighbours[x][y])
        {
            int value = Cells[row, col];
            if (value > 0) used[value - 1] = true;
        }

        return Enumerable.Range(1, 9).Where(n => !used[n - 1]).ToArray();
    }

    // Lecture d'un Sudoku à partir d'une chaîne de caractères
    public static SudokuGrid ReadSudoku(string sudokuAsString) => ReadMultiSudoku(new[] { sudokuAsString })[0];

    // Lecture de plusieurs grilles de Sudoku à partir d'un fichier
    public static List<SudokuGrid> ReadSudokuFile(string fileName) => ReadMultiSudoku(File.ReadAllLines(fileName));

    // Lecture de plusieurs grilles de Sudoku à partir d'un tableau de chaînes de caractères
    public static List<SudokuGrid> ReadMultiSudoku(string[] lines)
    {
        var grids = new List<SudokuGrid>();
        var rows = new List<int[]>();
        var rowCells = new List<int>();

        foreach (var line in lines.Where(l => !string.IsNullOrWhiteSpace(l)))
        {
            foreach (char c in line)
            {
                if (IsSudokuChar(c))
                {
                    rowCells.Add(char.IsDigit(c) ? (int)char.GetNumericValue(c) : 0);
                }

                if (rowCells.Count == 9)
                {
                    rows.Add(rowCells.ToArray());
                    rowCells.Clear();
                }

                if (rows.Count == 9)
                {
                    grids.Add(new SudokuGrid { Cells = To2D(rows.ToArray()) });
                    rows.Clear();
                }
            }
        }

        return grids;
    }

    // Vérification si un caractère est valide pour un Sudoku
    private static bool IsSudokuChar(char c) => char.IsDigit(c) || c == '.' || c == 'X' || c == '-';

    // Clone de la grille de Sudoku
    public object Clone() => new SudokuGrid { Cells = (int[,])Cells.Clone() };

    // Calcul du nombre d'erreurs par rapport à une grille originale
    public int NbErrors(SudokuGrid originalPuzzle)
    {
        int errors = AllNeighbours.Select(n => n.Select(pos => Cells[pos.row, pos.column])
                                                 .GroupBy(val => val)
                                                 .Sum(g => g.Count() - 1))
                                   .Sum();

        foreach (var row in NeighbourIndices)
            foreach (var col in NeighbourIndices)
                if (originalPuzzle.Cells[row, col] > 0 && originalPuzzle.Cells[row, col] != Cells[row, col])
                    errors++;

        return errors;
    }

    // Vérification de la validité de la grille par rapport à une grille originale
    public bool IsValid(SudokuGrid originalPuzzle) => NbErrors(originalPuzzle) == 0;

    // Calcul du nombre de cellules vides
    public int NbEmptyCells() => Cells.Cast<int>().Count(c => c == 0);
}

Console.WriteLine("SudokuGrid defini.");

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.

public interface ISudokuSolver
{
    SudokuGrid Solve(SudokuGrid s);
}

Console.WriteLine("ISudokuSolver defini.");

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.

#load "../Probas/Infer/SvgChartHelper.cs"

using System.IO;
using System.Diagnostics;
using System.Threading;
using System.Threading.Tasks;
using Microsoft.DotNet.Interactive;

public enum SudokuDifficulty
{
    Easy,
    Medium,
    Hard
}

public static class SudokuHelper
{
    private const string PUZZLES_FOLDER_NAME = "Puzzles";

    // Charge les sudokus à partir des fichiers
    public static List<SudokuGrid> GetSudokus(SudokuDifficulty difficulty)
    {
        string fileName = difficulty switch
        {
            SudokuDifficulty.Easy => "Sudoku_Easy51.txt",
            SudokuDifficulty.Medium => "Sudoku_hardest.txt",
            _ => "Sudoku_top95.txt"
        };

        var currentDirectory = new DirectoryInfo(Environment.CurrentDirectory);
        DirectoryInfo puzzlesDirectory = null;

        while (puzzlesDirectory == null)
        {
            puzzlesDirectory = currentDirectory.GetDirectories()
                                               .FirstOrDefault(d => d.Name == PUZZLES_FOLDER_NAME);
            currentDirectory = currentDirectory.Parent;
            if (currentDirectory == null)
                throw new ApplicationException("Couldn't find puzzles directory");
        }

        string filePath = Path.Combine(puzzlesDirectory.ToString(), fileName);
        return SudokuGrid.ReadSudokuFile(filePath);
    }

    // Résout un sudoku avec un solver donné
    public static SudokuGrid SolveSudoku(SudokuGrid sudoku, ISudokuSolver solver)
    {
        display($"Résolution par le solver {solver.GetType().Name} du Sudoku:\n {sudoku}");
        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        var solvedSudoku = solver.Solve(sudoku);
        stopwatch.Stop();
        display($"Sudoku renvoyé:\n{solvedSudoku}\nNombre d'erreurs réstantes: {solvedSudoku.NbErrors(sudoku)}\nTemps de résolution: {stopwatch.Elapsed.TotalMilliseconds} ms");
        return solvedSudoku;
    }

    // Teste les solveurs sur des sudokus de difficulté croissante
    public static List<(string SolverName, string Difficulty, double Time, int SolvedCount, string Status)> TestSolvers(List<(string Name, ISudokuSolver Solver)> solvers, 
    int numberOfSudokus = 10, int timeLimitMilliseconds = 3000)
    {
        var results = new List<(string SolverName, string Difficulty, double Time, int SolvedCount, string Status)>();
        var difficulties = new[] { SudokuDifficulty.Easy, SudokuDifficulty.Medium, SudokuDifficulty.Hard };

        var displayPlaceholder = display("Running tests...");

        foreach (var (solverName, solver) in solvers)
        {
            foreach (var difficulty in difficulties)
            {
                var sudokus = GetSudokus(difficulty).Take(numberOfSudokus).ToList();
                Stopwatch stopwatch = new Stopwatch();
                int solvedCount = 0;
                string status = "Success";

                var message = $"Testing {solverName} on {difficulty} sudokus...";
                displayPlaceholder.Update(message);
                foreach (var sudoku in sudokus)
                {
                    var cts = new CancellationTokenSource();
                    cts.CancelAfter(timeLimitMilliseconds);

                    Task task = Task.Run(() =>
                    {
                        try
                        {
                            SudokuGrid solved = solver.Solve(sudoku);
                            if (solved.NbErrors(sudoku) == 0)
                            {
                                Interlocked.Increment(ref solvedCount);
                            }
                        }
                        catch (Exception)
                        {
                            // Ignore exceptions for unsolvable sudokus
                        }
                    }, cts.Token);

                    stopwatch.Start();
                    if (!task.Wait(timeLimitMilliseconds))
                    {
                        status = "Timeout";
                        break;
                    }
                    stopwatch.Stop();

                    if (cts.Token.IsCancellationRequested)
                    {
                        status = "Timeout";
                        break;
                    }
                }

                if (solvedCount < numberOfSudokus)
                {
                    status = "Disqualified";
                }

                double totalTime = stopwatch.Elapsed.TotalMilliseconds;
                results.Add((solverName, difficulty.ToString(), totalTime, solvedCount, status));
            }
        }

        return results;
    }


// Affiche les résultats sous forme de graphiques à barres (rendu SVG inline)
public static void DisplayResults(List<(string SolverName, string Difficulty, double Time, int SolvedCount, string Status)> results)
{
    var difficulties = new[] { "Easy", "Medium", "Hard" };

    foreach (var difficulty in difficulties)
    {
        // Sélection des résultats pour la difficulté donnée
        var difficultyResults = results
            .Where(r => r.Difficulty == difficulty && r.Status != "Disqualified")
            .ToList();

        if (difficultyResults.Count == 0)
        {
            display($"Comparaison des solveurs - {difficulty} : aucun solveur qualifie (tous disqualifies ou en timeout).");
            continue;
        }

        var solvers = difficultyResults.Select(r => r.SolverName).ToArray();
        var times = difficultyResults.Select(r => r.Time).ToArray();

        // Rendu SVG inline statique (SvgChartHelper, EPIC #6927) : zero dependance, s'affiche
        // sur GitHub / nbviewer / hors ligne. Un chart Plotly `Show()` ouvrait un navigateur
        // (xdg-open sous Linux sans bureau) et ne produisait AUCUNE sortie dans le notebook.
        display(SvgChartHelper.Bar(
            $"Comparaison des solveurs - difficulte {difficulty} (temps total, ms)",
            solvers,
            times));
    }
}


}

Console.WriteLine("SudokuHelper defini.");

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 : Validation d'une grille Sudoku
// TODO: Implementez la methode IsValidSolution qui retourne true si la grille est une solution valide

// Etape 1 : Verifiez que chaque ligne contient les chiffres 1-9 sans doublon
// Etape 2 : Verifiez que chaque colonne contient les chiffres 1-9 sans doublon
// Etape 3 : Verifiez que chaque bloc 3x3 contient les chiffres 1-9 sans doublon

public static bool IsValidSolution(SudokuGrid grid)
{
    // TODO: Implementer la validation
    return false;  // TODO etudiant : remplacer par la validation
}

// Test de votre implementation (decommentez apres avoir implemente IsValidSolution)
// var testSudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
// Console.WriteLine($"Test IsValidSolution : {IsValidSolution(testSudoku)}");

Console.WriteLine("Exercice a completer");

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.