Sudoku-11-Choco-CSharp : Solveur Choco via IKVM

Navigation : << OR-Tools | Index | Z3 >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Utiliser Choco-solver depuis C# via le bridge IKVM 2. Modéliser un Sudoku comme un CSP avec Choco (variables, domaines, contraintes) 3. Configurer différentes stratégies de recherche (FirstFail, DomOverWDeg) 4. Comparer Choco avec d’autrès solveurs de contraintes

Durée estimée : ~30 min | Prérequis : Sudoku-00 Environment

Ce notebook implémente un solveur Sudoku utilisant Choco-solver, une librairie Java de Programmation par Contraintes, appelée depuis C# via IKVM (Java/.NET bridge).

Introduction : Choco-solver

Choco-solver est une librairie open-source Java de résolution de problèmes de Programmation par Contraintes (CP), développée par l’équipe TASC de l’Université de Nantes.

Pourquoi utiliser Choco depuis C# ?

  • Accès à un solveur CP mature : Choco existe depuis 1999, très documenté
  • Contraintes globales optimisées : allDifferent, cumulative, circuit, etc.
  • Stratégies de recherche avancées : DomOverWDeg, Impact-based search
  • Pédagogie : Excellent pour comprendre la programmation par contraintes

Configuration IKVM

IKVM est un bridge qui permet d’utiliser des librairies Java depuis .NET.

Approche : DLL pre-compilée + runtime IKVM NuGet

Le JAR Choco-solver a été pre-compilé en DLL .NET avec IKVM 8.15.0 : - org.chocosolver.solver.dll : Choco-solver compilé (12 Mo)

Le runtime IKVM lui-même est charge via NuGet (paquets IKVM et IKVM.Image en 8.15.0, ce dernier tirant l’image native de chaque plateforme), ce qui évite d’epingler une version précise de System.Text.Json.

Compilation de la DLL Choco

# Le JAR a été compilé avec <IkvmReference> dans un projet .NET temporaire
dotnet build ChocoIkvm.csproj

Cette approche (DLL pre-compilée consommee par un runtime IKVM NuGet) permet une exécution réelle de Choco-solver dans le notebook : la cellule de configuration ci-dessous assemble le “home” IKVM et le déclarer via AppContext, après quoi tous les solveurs Choco s’exécutent.

// Configuration du repertoire de travail
// Recherche le repertoire Sudoku depuis le repertoire courant
using System;
using System.IO;
using System.Net.Http;

string FindSudokuDir()
{
    var dir = new DirectoryInfo(Directory.GetCurrentDirectory());
    while (dir != null)
    {
        // Check if we're in the Sudoku directory
        if (File.Exists(Path.Combine(dir.FullName, "Sudoku-00-Environment-CSharp.ipynb")))
            return dir.FullName;
        // Check if Sudoku is a subdirectory
        var candidate = Path.Combine(dir.FullName, "MyIA.AI.Notebooks", "Sudoku");
        if (Directory.Exists(candidate) && File.Exists(Path.Combine(candidate, "Sudoku-00-Environment-CSharp.ipynb")))
            return candidate;
        dir = dir.Parent;
    }
    return Directory.GetCurrentDirectory();
}

var sudokuDir = FindSudokuDir();
Directory.SetCurrentDirectory(sudokuDir);

const string ChocoVersion = "4.10.17";
const string ChocoJar = $"choco-solver-{ChocoVersion}-jar-with-dependencies.jar";
const string ChocoUrl = $"https://repo1.maven.org/maven2/org/choco-solver/choco-solver/{ChocoVersion}/{ChocoJar}";

// Le JAR n'est pas requis pour l'exécution (Choco est consommé via la DLL pre-compilée),
// il n'est conservé que pour documenter la provenance Maven. Téléchargement best-effort.
if (!File.Exists(ChocoJar))
{
    try
    {
        Console.WriteLine($"Telechargement (optionnel) de {ChocoJar} depuis Maven...");
        using var client = new HttpClient();
        var data = client.GetByteArrayAsync(ChocoUrl).Result;
        File.WriteAllBytes(ChocoJar, data);
        Console.WriteLine($"Telecharge: {ChocoJar} ({data.Length} bytes)");
    }
    catch (Exception ex)
    {
        Console.WriteLine($"JAR non telecharge (optionnel, non requis) : {ex.GetType().Name}");
    }
}
else
{
    Console.WriteLine($"Choco-solver JAR deja present: {ChocoJar}");
}

Console.WriteLine($"Repertoire de travail: {Path.GetFileName(sudokuDir.TrimEnd(Path.DirectorySeparatorChar, Path.AltDirectorySeparatorChar))}");
Telechargement (optionnel) de choco-solver-4.10.17-jar-with-dependencies.jar depuis Maven...
Telecharge: choco-solver-4.10.17-jar-with-dependencies.jar (11043898 bytes)
Repertoire de travail: Sudoku

Lecture du téléchargement : version épinglée, taille réelle

La sortie donne les trois faits qui comptent : le jar récupéré est choco-solver-4.10.17-jar-with-dependencies.jar — la version est épinglée (4.10.17, pas « dernière »), condition de reproductibilité ; il pèse 11 043 898 octets (~11 Mo) précisément parce qu’il embarque toutes ses dépendances (pas de résolution Maven au runtime) ; et le téléchargement est marqué optionnel — la cellule vérifie d’abord la présence du jar dans le répertoire de travail Sudoku et ne re-télécharge que s’il manque. Un second run de ce notebook ne consomme aucun octet réseau sur cette étape.

Chargement des références au solveur Choco (directives #r en premier).

// Configuration IKVM 8.15.0 pour Choco-solver -- exécution réelle en-kernel (See #4667, See #3801)
//
// Deux verrous documentes precedemment sont leves ici :
//   1. Conflit System.Text.Json 8.0.0.5 : on charge IKVM via NuGet (et non des DLL IKVM locales
//      qui epinglaient 8.0.0.5), ce qui laisse le kernel resoudre une version compatible.
//   2. "Could not locate ikvm home path" : IKVM 8.15 ne consulte PAS la variable d'env IKVM_HOME ;
//      il lit AppContext["IKVM.Home"]. On assemble le home complet (fusion de l'image arch-independante
//      any/any -- classes + tzdb.dat -- et de l'image native de la plateforme) puis on le déclare via AppContext,
//      AVANT tout premier appel Java (l'init de la JVM se declenche au premier type java.*, en cellule suivante).
#r "nuget: IKVM, 8.15.0"
#r "nuget: IKVM.Image, 8.15.0"

using System.IO;
using System.Runtime.InteropServices;

// RID de la machine courante (win-x64, linux-x64, osx-arm64, ...) : le paquet IKVM.Image
// tire deja l'image native de chaque plateforme, il suffit de choisir la bonne.
string ikvmOs  = OperatingSystem.IsWindows() ? "win" : OperatingSystem.IsMacOS() ? "osx" : "linux";
string ikvmRid = ikvmOs + "-" + RuntimeInformation.ProcessArchitecture.ToString().ToLowerInvariant();
string ikvmVer = "8.15.0";
string nugetRoot = Environment.GetEnvironmentVariable("NUGET_PACKAGES")
    ?? Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.UserProfile), ".nuget", "packages");
string ikvmBaseAny = Path.Combine(nugetRoot, "ikvm.image", ikvmVer, "ikvm", "any", "any");
string ikvmArchDir = Path.Combine(nugetRoot, "ikvm.image.runtime." + ikvmRid, ikvmVer, "ikvm", "any", ikvmRid);
string ikvmHome    = Path.Combine(Path.GetTempPath(), "ikvm-home-" + ikvmVer + "-" + ikvmRid);

void IkvmCopyMerge(string src, string dst)
{
    foreach (var d in Directory.GetDirectories(src, "*", SearchOption.AllDirectories))
        Directory.CreateDirectory(d.Replace(src, dst));
    foreach (var f in Directory.GetFiles(src, "*", SearchOption.AllDirectories))
    {
        var t = f.Replace(src, dst);
        Directory.CreateDirectory(Path.GetDirectoryName(t));
        File.Copy(f, t, overwrite: true);
    }
}

if (Directory.Exists(ikvmBaseAny) && Directory.Exists(ikvmArchDir))
{
    Directory.CreateDirectory(ikvmHome);
    IkvmCopyMerge(ikvmBaseAny, ikvmHome);   // classes Java + tzdb.dat (arch-independant)
    IkvmCopyMerge(ikvmArchDir, ikvmHome);   // bibliotheques natives de la plateforme (bin/ + lib/)
}
AppContext.SetData("IKVM.Home", ikvmHome);

bool tzdbOk = File.Exists(Path.Combine(ikvmHome, "lib", "tzdb.dat"));
Console.WriteLine("IKVM 8.15.0 pret (home=" + Path.GetFileName(ikvmHome) + ", tzdb=" + tzdbOk + ") - Choco-solver charge");
Installing Packages
  • IKVM
  • IKVM.Image
IKVM 8.15.0 pret (home=ikvm-home-8.15.0-win-x64, tzdb=True) - Choco-solver charge

Lecture de la disponibilité IKVM : les deux verrous, levés

IKVM 8.15.0 pret (home=ikvm-home-8.15.0-<rid>, tzdb=True) condense la résolution des deux blocages historiques documentés plus bas (note technique de la section 3). tzdb=True : la base des fuseaux horaires Java (tzdb.dat) est chargée — sans elle, toute initialisation de la machine virtuelle Java échoue silencieusement ou avec une erreur cryptique. home=ikvm-home-8.15.0-<rid> (<rid> : win-x64, linux-x64 ou osx-arm64 selon la machine) : IKVM 8.15 ne lit pas la variable d’environnement IKVM_HOME mais AppContext["IKVM.Home"] ; la cellule de configuration a assemblé ce home complet (fusion de l’image arch-indépendante et de l’image native de la plateforme) et l’a déclaré avant tout premier appel Java — l’ordre est obligatoire, car la JVM s’initialise une seule fois.

Import des espaces de noms Java Choco via IKVM.

// DLL Choco-solver pre-compilée : référencée ici (après la config IKVM), avant les imports de namespaces.
// Copie partagee dedupliquee : la DLL vit dans Search/Part2-CSP/ (les deux copies etaient
// byte-identiques, blob 02ef8ac5c4 -- See #13742).
#r "../Search/Part2-CSP/org.chocosolver.solver.dll"

// Imports Choco via IKVM (espaces de noms Java mappes vers .NET)
using org.chocosolver.solver;
using org.chocosolver.solver.variables;
using org.chocosolver.solver.constraints;
using org.chocosolver.solver.search.strategy.selectors.variables;
using org.chocosolver.solver.search.strategy.selectors.values;
using System;
using System.Linq;
using System.Collections.Generic;

// Desambiguation : org.chocosolver.solver.variables.Task vs System.Threading.Tasks.Task
using Task = System.Threading.Tasks.Task;

Console.WriteLine("Choco-solver via IKVM 8.15.0 - Pret pour resolution Sudoku");
Choco-solver via IKVM 8.15.0 - Pret pour resolution Sudoku

Ce que « prêt pour résolution » signifie

À ce point, les espaces de noms Java de Choco sont importés dans le kernel .NET : la suite du notebook peut instancier Model, IntVar, Constraint comme s’ils étaient des classes C#. C’est le pont IKVM : chaque objet Java est manipulé via un proxy .NET, les appels traversent la frontière à chaque méthode — le coût de ce marshaling fera partie du temps de résolution mesuré en section 3, et il est indissociable de la résolution elle-même sur cette architecture. Ce pont est aussi ce qui distingue ce notebook de ses cousins Python de la série : ici, le solveur n’est ni réimplémenté ni appelé par script — il vit dans le kernel, inspectable au point d’arrêt comme toute classe .NET.

Import des classes de base depuis le notebook d’environnement.

// Importer les classes de base depuis le notebook d'environnement
#!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.

1. Implémentation Simple : ChocoSimpleSolver

La première implémentation utilise Choco de manière directe sans optimisations particulières.

Exercice : Comparer les stratégies de recherche Choco

Objectif : Comparez au moins 2 stratégies de recherche Choco (InputOrder, DomOverWDeg) et mesurez leur impact sur le temps de résolution.

Indice : Configurez le solver avec différentes stratégies et lancez les benchmarks.

// EXERCICE : Comparer les stratégies de recherche Choco
public Dictionary<string, double> CompareChocoStrategies(int[,] puzzle)
{
    // TODO: Testez différentes stratégies de recherche Choco
    // et retournez les temps de résolution pour chacune
    return null; // TODO etudiant
}
public class ChocoSimpleSolver : ISudokuSolver
{
    public SudokuGrid Solve(SudokuGrid s)
    {
        var model = new Model("Sudoku Solver - Simple");
        
        // Créer les 81 variables (1-9)
        var cellVariables = model.intVarMatrix("cells", 9, 9, 1, 9);
        
        var constraints = new List<Constraint>();
        
        // Contraintes pour les lignes et les colonnes
        for (int i = 0; i < 9; i++)
        {
            // Lignes : toutes les valeurs différentes
            constraints.Add(model.allDifferent(cellVariables[i]));
            // Colonnes : toutes les valeurs différentes
            constraints.Add(model.allDifferent(GetColumn(cellVariables, i)));
        }

        // Contraintes pour les blocs 3x3
        for (int blockRow = 0; blockRow < 3; blockRow++)
        {
            for (int blockCol = 0; blockCol < 3; blockCol++)
            {
                constraints.Add(model.allDifferent(GetBlock(cellVariables, blockRow, blockCol)));
            }
        }

        // Appliquer les valeurs initiales du Sudoku
        for (int row = 0; row < 9; row++)
        {
            for (int col = 0; col < 9; col++)
            {
                if (s.Cells[row, col] != 0)
                {
                    constraints.Add(model.arithm(cellVariables[row][col], "=", s.Cells[row, col]));
                }
            }
        }

        // Poster toutes les contraintes
        foreach (var constraint in constraints)
        {
            constraint.post();
        }

        // Résolution
        var solver = model.getSolver();
        if (solver.solve())
        {
            // Remplir la grille avec la solution
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    s.Cells[row, col] = cellVariables[row][col].getValue();
                }
            }
        }
        
        return s;
    }
    
    private IntVar[] GetColumn(IntVar[][] grid, int col)
    {
        return Enumerable.Range(0, 9).Select(row => grid[row][col]).ToArray();
    }

    private IntVar[] GetBlock(IntVar[][] grid, int blockRow, int blockCol)
    {
        return Enumerable.Range(0, 3)
            .SelectMany(i => Enumerable.Range(0, 3)
                .Select(j => grid[blockRow * 3 + i][blockCol * 3 + j]))
            .ToArray();
    }
}

Console.WriteLine("ChocoSimpleSolver defini.");
ChocoSimpleSolver defini.

2. Implémentation Optimisée : ChocoSolverVariableSelector

Cette version utilise des heuristiques de recherche avancées pour améliorer les performances :

  • FirstFail : Choisir la variable avec le plus petit domaine (MRV)
  • IntDomainMin : Choisir la plus petite valeur disponible
public class ChocoSolverVariableSelector : ISudokuSolver
{
    protected const int GridSize = 9;
    protected const int BlockSize = 3;
    protected IntVar[] FlatCells { get; set; } = Array.Empty<IntVar>();

    public virtual SudokuGrid Solve(SudokuGrid grid)
    {
        ValidateInput(grid);

        var model = new Model("Solveur Sudoku - Optimise");

        // Créer les variables cellulaires
        var cellVariables = CreateCellVariables(model, grid);
        FlatCells = Flatten(cellVariables);

        // Appliquer les contraintes
        ApplyConstraints(model, cellVariables);

        // Configurer le solveur avec la stratégie de recherche
        var solver = GetSolver(model, cellVariables);

        // Résoudre
        if (solver.solve())
        {
            return ExtractSolution(grid, cellVariables);
        }
        else
        {
            throw new Exception("Aucune solution trouvee.");
        }
    }

    protected virtual void ValidateInput(SudokuGrid grid)
    {
        for (int i = 0; i < GridSize; i++)
        {
            if (HasDuplicatesInRow(grid.Cells, i) || HasDuplicatesInColumn(grid.Cells, i))
            {
                throw new ArgumentException($"Grille invalide : doublons ligne/colonne {i + 1}");
            }
        }
        for (int br = 0; br < BlockSize; br++)
        {
            for (int bc = 0; bc < BlockSize; bc++)
            {
                if (HasDuplicatesInBlock(grid.Cells, br, bc))
                {
                    throw new ArgumentException($"Grille invalide : doublons bloc ({br + 1}, {bc + 1})");
                }
            }
        }
    }

    private bool HasDuplicatesInRow(int[,] cells, int row)
    {
        var seen = new bool[GridSize + 1];
        for (int col = 0; col < GridSize; col++)
        {
            int val = cells[row, col];
            if (val != 0)
            {
                if (seen[val]) return true;
                seen[val] = true;
            }
        }
        return false;
    }

    private bool HasDuplicatesInColumn(int[,] cells, int col)
    {
        var seen = new bool[GridSize + 1];
        for (int row = 0; row < GridSize; row++)
        {
            int val = cells[row, col];
            if (val != 0)
            {
                if (seen[val]) return true;
                seen[val] = true;
            }
        }
        return false;
    }

    private bool HasDuplicatesInBlock(int[,] cells, int blockRow, int blockCol)
    {
        var seen = new bool[GridSize + 1];
        int startRow = blockRow * BlockSize;
        int startCol = blockCol * BlockSize;
        for (int i = 0; i < BlockSize; i++)
        {
            for (int j = 0; j < BlockSize; j++)
            {
                int val = cells[startRow + i, startCol + j];
                if (val != 0)
                {
                    if (seen[val]) return true;
                    seen[val] = true;
                }
            }
        }
        return false;
    }

    protected virtual IntVar[][] CreateCellVariables(Model model, SudokuGrid grid)
    {
        var variables = new IntVar[GridSize][];

        for (int row = 0; row < GridSize; row++)
        {
            variables[row] = new IntVar[GridSize];
            for (int col = 0; col < GridSize; col++)
            {
                int val = grid.Cells[row, col];
                if (val != 0)
                {
                    // Variable fixee a la valeur initiale
                    variables[row][col] = model.intVar($"cell_{row}_{col}", val);
                }
                else
                {
                    // Variable libre (1-9)
                    variables[row][col] = model.intVar($"cell_{row}_{col}", 1, GridSize, false);
                }
            }
        }
        return variables;
    }

    protected virtual void ApplyConstraints(Model model, IntVar[][] cellVariables)
    {
        // Contraintes sur les lignes et colonnes
        for (int i = 0; i < GridSize; i++)
        {
            model.allDifferent(cellVariables[i]).post();
            model.allDifferent(GetColumn(cellVariables, i)).post();
        }

        // Contraintes sur les blocs 3x3
        for (int blockRow = 0; blockRow < BlockSize; blockRow++)
        {
            for (int blockCol = 0; blockCol < BlockSize; blockCol++)
            {
                model.allDifferent(GetBlock(cellVariables, blockRow, blockCol)).post();
            }
        }
    }

    public virtual Solver GetSolver(Model model, IntVar[][] cellVariables)
    {
        // Stratégie FirstFail + IntDomainMin
        model.getSolver().setSearch(
            org.chocosolver.solver.search.strategy.Search.intVarSearch(
                new FirstFail(model),
                new IntDomainMin(),
                FlatCells
            )
        );

        model.getSolver().setNoGoodRecordingFromRestarts();
        return model.getSolver();
    }

    protected virtual SudokuGrid ExtractSolution(SudokuGrid grid, IntVar[][] cells)
    {
        for (int row = 0; row < GridSize; row++)
        {
            for (int col = 0; col < GridSize; col++)
            {
                grid.Cells[row, col] = cells[row][col].getValue();
            }
        }
        return grid;
    }

    protected static IntVar[] Flatten(IntVar[][] matrix)
    {
        var flat = new IntVar[GridSize * GridSize];
        int index = 0;
        for (int i = 0; i < GridSize; i++)
        {
            for (int j = 0; j < GridSize; j++)
            {
                flat[index++] = matrix[i][j];
            }
        }
        return flat;
    }

    private IntVar[] GetColumn(IntVar[][] grid, int col)
    {
        var column = new IntVar[GridSize];
        for (int row = 0; row < GridSize; row++)
        {
            column[row] = grid[row][col];
        }
        return column;
    }

    private IntVar[] GetBlock(IntVar[][] grid, int blockRow, int blockCol)
    {
        var block = new IntVar[BlockSize * BlockSize];
        int index = 0;
        int startRow = blockRow * BlockSize;
        int startCol = blockCol * BlockSize;
        for (int i = 0; i < BlockSize; i++)
        {
            for (int j = 0; j < BlockSize; j++)
            {
                block[index++] = grid[startRow + i][startCol + j];
            }
        }
        return block;
    }
}

Console.WriteLine("ChocoSolverVariableSelector defini avec strategie FirstFail.");
ChocoSolverVariableSelector defini avec strategie FirstFail.

Anatomie de FirstFail : échouer tôt, échouer bon marché

La stratégie déclarée ici — FirstFail — est l’incarnation Choco de l’heuristique MRV (minimum remaining values) du cours CSP : à chaque nœud de recherche, brancher sur la variable au domaine le plus petit. La logique est contre-intuitive mais solide : une variable presque contrainte mène vite soit à une solution, soit à une contradiction — et dans les deux cas on l’apprend tachycardement et bon marché. Brancher au contraire sur une variable libre repousse la contradiction à dix coupes plus bas, où elle coûte un sous-arbre entier. C’est le principe « fail-first » : révéler les conflits le plus tôt possible dans l’arbre, quand ils sont encore peu coûteux à annuler.

Note technique – exécution réelle : le solveur Choco via IKVM 8.15.0 s’exécute désormais directement dans le kernel dotnet-interactive. Les deux verrous d’environnement qui bloquaient auparavant sont leves par la cellule de configuration IKVM (voir plus haut) :

  1. Assembly System.Text.Json 8.0.0.5 : on charge IKVM via NuGet (#r "nuget: IKVM, 8.15.0") au lieu des DLL IKVM locales qui epinglaient cette version précise ; le kernel resout alors une version compatible.
  2. Home IKVM introuvable : IKVM 8.15 ne lit pas la variable d’environnement IKVM_HOME mais AppContext["IKVM.Home"]. La cellule de configuration assemble le home complet (fusion de l’image arch-independante et de l’image native de la plateforme, incluant tzdb.dat) puis le déclarer via AppContext.SetData, avant tout premier appel Java.

Statut : la résolution ci-dessous produit une vraie solution Sudoku calculee par Choco-solver.

3. Test avec une Grille Exemple

Exercice : Résolution avec limite de temps

Objectif : Implementez une résolution Choco avec un timeout et analysez les résultats intermédiaires obtenus quand le temps est depasse.

Indice : Utilisez les paramètrès de timeout du solver et récupérez l’état partiel.

// EXERCICE : Résolution avec limite de temps
public (bool Solved, int[,] PartialSolution, double TimeMs) SolveWithTimeout(int[,] puzzle, double timeoutSeconds)
{
    // TODO: Lancez la résolution Choco avec un timeout
    // et retournez l'état (résolu ou partiel) et le temps écoulé
    return (false, null, 0); // TODO etudiant
}
// Grille de test
var testPuzzle = new SudokuGrid();
testPuzzle.Cells = new int[,] {
    {9, 0, 2, 0, 0, 5, 4, 0, 3},
    {1, 0, 0, 0, 6, 3, 0, 2, 5},
    {5, 0, 8, 4, 0, 7, 0, 6, 0},
    {0, 2, 6, 3, 0, 9, 0, 0, 1},
    {0, 5, 7, 0, 1, 0, 2, 9, 0},
    {0, 9, 0, 6, 7, 0, 5, 3, 0},
    {2, 4, 0, 5, 3, 0, 6, 0, 0},
    {7, 0, 5, 2, 0, 0, 3, 0, 4},
    {0, 8, 0, 0, 4, 1, 9, 5, 0}
};

Console.WriteLine("Puzzle initial:");
Console.WriteLine(testPuzzle);
Puzzle initial:
-------------------------------
| 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    | 
-------------------------------

Lecture de la grille de validation : 45 indices

Comptez les cases remplies : 5 indices par ligne, 45 au total — une grille très facile (le minimum connu pour une solution unique est de 17 ; ici il ne reste que 36 cellules à déduire). C’est la grille de validation du notebook, volontairement douce : elle teste le câblage Choco, pas la puissance du solveur. On la retrouve à l’identique dans Sudoku-06 (test MAC) — les notebooks de la série partagent ce témoin commun, ce qui rend leurs temps comparables entre eux.

Un repère de culture générale : le minimum prouvé pour un Sudoku à solution unique est de 17 indices, et l’inexistence de toute grille à 16 indices a été établie par énumération exhaustive sur grappe (McGuire, Tugemann et Civario, 2012). Notre grille de validation, à 45 indices, vit donc très au-dessus du minimum — l’espace entre 17 et 45 est précisément celui où la difficulté humaine s’installe, alors même que la difficulté pour un solveur à propagation y devient marginale.

Test du solveur Choco optimisé sur la grille de validation.

// Test avec le solveur optimisé : exécution réelle de Choco via IKVM 8.15.0.
var solver = new ChocoSolverVariableSelector();
var stopwatch = System.Diagnostics.Stopwatch.StartNew();

var solution = solver.Solve(testPuzzle);
stopwatch.Stop();

Console.WriteLine($"\nSolution trouvee en {stopwatch.ElapsedMilliseconds} ms:");
Console.WriteLine(solution);

Solution trouvee en 727 ms:
-------------------------------
| 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 | 
-------------------------------

Lecture de la solution : quelques centaines de millisecondes, toutes contraintes honorées

La grille complétée respecte chacun des 45 indices (vérifiez la première ligne : 9 et 2 en place, le 5 central, 4 et 3 en fin — rien n’a bougé), et chaque ligne, colonne et bloc contient 1-9 exactement une fois : c’est la définition même de la solution, et Choco la certifie par construction (le modèle déclare ces contraintes, il ne les vérifie pas a posteriori).

Que mesure ce temps (quelques centaines de millisecondes, valeur qui dépend de la machine : voir la sortie ci-dessus) ? Sur l’architecture IKVM, bien plus que la recherche pure : cette première résolution inclut le chargement des classes Java du solveur, la compilation JIT du code Choco et le marshaling .NET-à-Java de chaque appel. Un second appel dans la même session serait sensiblement plus rapide — c’est le coût d’amorçage typique d’un solveur hébergé. Le solveur utilisé ici est l’optimisé (ChocoSolverVariableSelector, stratégie FirstFail déclarée en section 2) : il choisit à chaque nœud la variable au domaine le plus petit, ce qui réduit le facteur de branchement bien avant que la recherche ne s’enlise.

Mettez ce chiffre en perspective série : Sudoku-06 résout la même grille (le témoin commun à 45 indices) en quelques dizaines de millisecondes avec MAC en C# natif. Cet écart ne dit pas « Choco est lent » — il mesure l’architecture d’hébergement : solveur Java re-compilé à la volée derrière un pont .NET, contre code C# déjà JIT-é par le kernel. C’est une donnée précieuse pour l’ingénierie : le choix d’un solveur industriel se paie en coût d’intégration, et ce coût se voit — ici, près d’un ordre de grandeur sur la grille témoin, l’essentiel étant de l’amorçage.

4. Comparaison des Stratégies

Heuristiques de Choix de Variables

Stratégie Description Complexité
InputOrder Ordre de déclaration O(1)
FirstFail Domaine minimum (MRV) O(n)
DomOverWDeg Domaine / Degré pondere O(n * d)
ConflictHistory Historique des conflits O(n * log n)

Heuristiques de Choix de Valeurs

Stratégie Description
IntDomainMin Plus petite valeur
IntDomainMax Plus grande valeur
IntDomainRandom Valeur aleatoire
IntDomainMiddle Valeur mediane

Exercice : Comptage de solutions avec Choco

Objectif : Utilisez Choco pour compter le nombre total de solutions d’un puzzle Sudoku donne.

Indice : Configurez le solver pour chercher toutes les solutions et comptez-les.

// EXERCICE : Comptage de solutions avec Choco
public int CountSolutionsWithChoco(int[,] puzzle, int maxCount = 100)
{
    // TODO: Utilisez Choco pour compter les solutions du puzzle
    // en s'arretant après maxCount solutions
    return 0; // TODO etudiant
}

Exercice : Résoudre le problème des N-Reines avec Choco

Enonce

Adaptez le solveur Choco pour resoudre le problème des N-Reines. Ce problème classique demande de placer N reines sur un échiquier N×N de sorte qu’aucune ne soit en prise avec une autre.

Implementez NQueensChocoSolver qui : 1. Créé N variables queen[i] representant la colonne de la reine de la ligne i (domaine 0..N-1) 2. Ajoute la contrainte allDifferent sur les colonnes 3. Ajoute les contraintes de diagonales avec des variables temporaires 4. Compte et affiche le nombre de solutions pour N=8

Indice :

Pour les diagonales, deux reines aux positions (i, queen[i]) et (j, queen[j]) sont en conflit si queen[i] - queen[j] == i - j. En Choco, vous pouvez utiliser model.arithm() pour chaque paire, ou introduire des variables auxiliaires diagDiff[i][j] = queen[i] - queen[j] et ajouter allDifferent sur les diagonales.

// Exemple guide : Problème des N-Reines avec Choco-solver
// TODO: Implementez un solveur pour compter les solutions du problème des N-Reines

public class NQueensChocoSolver
{
    public int N { get; set; }
    
    public NQueensChocoSolver(int n)
    {
        N = n;
    }
    
    public int CountSolutions()
    {
        var model = new Model($"N-Queens N={N}");
        
        // TODO: Créer les variables queen[i] pour chaque ligne i (domaine 0..N-1)
        // var queens = model.intVarArray("queens", N, 0, N - 1);
        
        // TODO: Contrainte de colonnes : toutes les reines dans des colonnes différentes
        // model.allDifferent(queens).post();
        
        // TODO: Contraintes de diagonales
        // Pour chaque paire (i, j) avec i < j :
        //   model.arithm(queens[i], "!=", queens[j], "+", i - j).post();  // diagonale principale
        //   model.arithm(queens[i], "!=", queens[j], "+", b - i).post();  // diagonale secondaire
        
        // TODO: Compter les solutions avec solver.findAllSolutions()
        // var solver = model.getSolver();
        // solver.findAllSolutions();
        // return (int)solver.getSolutionCount();
        
        return -1;  // TODO étudiant : implémenter le comptage des solutions
    }
}

// Test
int N = 8;
var nQueens = new NQueensChocoSolver(N);
// int count = nQueens.CountSolutions();
// Console.WriteLine($"Nombre de solutions pour {N}-Reines : {count}");
// Console.WriteLine($"Attendu : 92");
Console.WriteLine($"TODO: Implementez NQueensChocoSolver.CountSolutions() pour le problème des {N}-Reines");
TODO: Implementez NQueensChocoSolver.CountSolutions() pour le problème des 8-Reines

Résumé et perspectives

Ce notebook a exploré la résolution de Sudoku par programmation par contraintes avec Choco-solver, une librairie Java mature appelée depuis C# via le bridge IKVM. L’implémentation a couvert deux niveaux de sophistication : un solveur simple (ChocoSimpleSolver) posant directement les 27 contraintes allDifferent (9 lignes, 9 colonnes, 9 blocs), puis un solveur optimisé (ChocoSolverVariableSelector) integrant des heuristiques de recherche avancées comme FirstFail (équivalent MRV, choisissant la variable au plus petit domaine) et le noGood recording pour éviter de revisiter des branches déjà ecartees. L’exercice sur les N-Reines propose de transposer le modèle CSP vers un autre problème classique, en réutilisant les mêmes primitives Choco (allDifferent, arithm, comptage de solutions).

La comparaison théorique avec OR-Tools, Z3 et python-constraint montre que Choco se situe dans une niche intermédiaire : moins performant qu’OR-Tools CP-SAT sur les instances difficiles, mais offrant un accès natif à des contraintes globales optimisées et des stratégies de recherche fines (DomOverWDeg, Impact-based search). La limitation technique rencontrée avec IKVM dans dotnet-interactive illustre les défis d’interopérabilité Java/.NET en environnement notebook, et confirme l’intérêt de approaches natives comme OR-Tools pour un usage pédagogique fluide.

Le prochain notebook, Sudoku-12-Z3-CSharp, aborde une approche complementaire avec le solveur SMT Z3, qui représente le Sudoku non pas comme un CSP mais comme un système de contraintes logiques, offrant des garanties de completude et des techniques de raisonnement différentes (théorie des tableaux, résolution SAT).

5. Résumé

Points cles

  1. IKVM permet d’utiliser Choco (Java) depuis C#
  2. Contrainte allDifferent : 27 contraintes pour Sudoku (9 lignes + 9 colonnes + 9 blocs)
  3. Stratégie FirstFail : Choisir la variable avec le plus petit domaine (MRV)
  4. Performance : une fraction de seconde au premier appel (demarrage JVM IKVM inclus, cf. cellule de mesure ci-dessus), puis de l’ordre de quelques dizaines de ms en regime etabli selon la difficulte

Comparaison avec autrès solveurs

Solveur Langage Performance Facilite
Choco Java/C# (IKVM) Moyenne Moyenne
OR-Tools C++/C# Haute Moyenne
Z3 C++/C# Haute Complexe
python-constraint Python Basse Simple

Navigation : << OR-Tools | Index | Z3 >>

Code inspire du projet jsboigeECE/2025-ECE-Ing4-Fin-Sudoku-Gr01

Retour au sommet