Sudoku-10 : Résolution avec OR-Tools (C#)

Navigation : << Sudoku-09 Graph Coloring C# | Index | Sudoku-11 Choco C# >>

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Comprendre les différences entre les solveurs CSP, CP-SAT et MIP d’OR-Tools 2. Implémenter un solveur de contraintes pour le Sudoku avec CpModel et AddAllDifferent 3. Utiliser la programmation linéaire mixte (MIP) avec une formulation 3D binaire 4. Comparer les performances de différentes approches de résolution de contraintes

Prérequis

Durée estimée : 50 minutes

Voir aussi : CSP-1-Fondamentaux pour les bases de CSP

Introduction

Google OR-Tools est une suite de logiciels d’optimisation développée par Google. Elle permet de résoudre des problèmes complexes d’optimisation combinatoire tels que la satisfaction de contraintes (CSP), la programmation linéaire (LP), la programmation linéaire mixte (MIP), et bien plus. Dans ce projet, nous nous concentrerons sur la résolution de Sudokus en utilisant différentes techniques fournies par OR-Tools.

Types de Solveurs

  1. Solveur de Satisfaction de Contraintes (CSP) : Ce solveur utilise des techniques de propagation de contraintes et de recherche pour trouver des solutions qui satisfont toutes les contraintes spécifiées. En CSP, les utilisateurs déclarent les contraintes sur les solutions faisables pour un ensemble de variables de décision.

  2. Solveur de Programmation Linéaire Mixte (MIP) : Ce solveur combine la programmation linéaire avec des variables entières pour résoudre des problèmes d’optimisation.

  3. Solveur de Satisfaction de Contraintes SAT (CP-SAT) : Ce solveur est basé sur un noyau SAT, utilisant des techniques avancées pour résoudre les problèmes de satisfaction de contraintes.

Installation de OR-Tools

Pour utiliser OR-Tools avec C#, nous devons d’abord installer la bibliothèque.

Installation de OR-Tools

#r "nuget: Google.OrTools"
Installing Packages
  • Google.OrTools

Importation des Classes de Base

Nous allons importer les classes de base définies dans le notebook précédent, fournissant notamment la représentation, le chargement et l’affichage de Sudokus, et l’infrastructure de résolution.

#!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.

Implémentations des Solveurs

Solveur par contraintes classique (ConstraintSolver legacy)

L’algorithme de satisfaction de contraintes (CSP) utilise les contraintes pour réduire l’espace de recherche et trouver une solution qui satisfait toutes les contraintes du problème. Cette première implémentation s’appuie sur le solveur historique d’OR-Tools, Google.OrTools.ConstraintSolver.Solver (l’ancien moteur CP, distinct du CP-SAT vu plus bas).

Étapes de la modélisation avec le ConstraintSolver legacy :

  1. Création du solveur : instancier new Solver("CpSimple") (Google.OrTools.ConstraintSolver.Solver).
  2. Définition des variables : créer une matrice 9x9 de variables avec solver.MakeIntVarMatrix(9, 9, 1, 9, ...). Chaque variable représente une cellule du Sudoku, de domaine 1 à 9.
  3. Ajout des contraintes : fixer les indices initiaux (solver.Add(matrix[i, j] == valeur)) puis déclarer les contraintes de lignes, colonnes et régions avec solver.MakeAllDifferent(...).
  4. Stratégie de recherche : construire un DecisionBuilder via solver.MakePhase(variables, VariableSelectionStrategy, ValueSelectionStrategy) – c’est ce qui paramètre l’ordre de sélection des variables et des valeurs.
  5. Résolution : lancer solver.NewSearch(db) puis itérer solver.NextSolution() jusqu’à obtenir une solution.
  6. Extraction des résultats : lire chaque matrix[i, j].Value() pour reconstruire la grille résolue.

Note : ce moteur historique se distingue du CP-SAT (CpModel / AddAllDifferent / CpSolver, présenté plus loin), que Google recommande désormais pour les nouveaux projets. Les deux savent résoudre le Sudoku ; ils diffèrent par leur API et leur moteur interne.

using Google.OrTools.ConstraintSolver;
using SimpleCPSolver = Google.OrTools.ConstraintSolver.Solver;
using SimpleConstraint = Google.OrTools.ConstraintSolver.Constraint;
using IntVar = Google.OrTools.ConstraintSolver.IntVar;
using System.Linq;
using System.Text;

public class OrToolsCPSolver : ISudokuSolver
{
    private const int GridSize = 9;
    private const int RegionSize = 3;
    public int VariableSelectionStrategy { get; set; } = SimpleCPSolver.CHOOSE_FIRST_UNBOUND;
    public int ValueSelectionStrategy { get; set; } = SimpleCPSolver.ASSIGN_MIN_VALUE;
    public SudokuGrid Solve(SudokuGrid s)
    {
        int[,] grid = s.Cells;
        SimpleCPSolver solver = new SimpleCPSolver("CpSimple");
        IntVar[,] matrix = CreateConstraints(solver, grid);
        // Parametrize DecisionBuilder
        DecisionBuilder db = solver.MakePhase(matrix.Flatten(), VariableSelectionStrategy, ValueSelectionStrategy);
        solver.NewSearch(db);
        while (solver.NextSolution())
        {
            string solvedString = BuildSolvedString(matrix);
            solver.EndSearch();
            return SudokuGrid.ReadSudoku(solvedString);
        }
        throw new Exception("Unfeasible Sudoku");
    }
    private static IntVar[,] CreateConstraints(SimpleCPSolver solver, int[,] grid)
    {
        IntVar[,] matrix = solver.MakeIntVarMatrix(GridSize, GridSize, 1, 9, "matrix");
        for (int i = 0; i < GridSize; i++)
        {
            for (int j = 0; j < GridSize; j++)
            {
                if (grid[i, j] != 0)
                {
                    solver.Add(matrix[i, j] == grid[i, j]);
                }
            }
        }
        for (int i = 0; i < GridSize; i++)
        {
            solver.Add(solver.MakeAllDifferent((from j in Enumerable.Range(0, GridSize) select matrix[i, j]).ToArray()));
            solver.Add(solver.MakeAllDifferent((from j in Enumerable.Range(0, GridSize) select matrix[j, i]).ToArray()));
        }
        for (int row = 0; row < GridSize; row += RegionSize)
        {
            for (int col = 0; col < GridSize; col += RegionSize)
            {
                IntVar[] regionVars = new IntVar[RegionSize * RegionSize];
                for (int r = 0; r < RegionSize; r++)
                {
                    for (int c = 0; c < RegionSize; c++)
                    {
                        regionVars[r * RegionSize + c] = matrix[row + r, col + c];
                    }
                }
                solver.Add(solver.MakeAllDifferent(regionVars));
            }
        }
        return matrix;
    }
    private static string BuildSolvedString(IntVar[,] matrix)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < GridSize; i++)
        {
            for (int j = 0; j < GridSize; j++)
            {
                sb.Append((int)matrix[i, j].Value());
            }
        }
        return sb.ToString();
    }
}

Console.WriteLine("Classe OrToolsCPSolver definie.");
Classe OrToolsCPSolver definie.

Test du solver CP Simple

On teste sur un sudoku de chaque difficulté

Exercice : Compter les contraintes initiales

Objectif : Comptez le nombre de contraintes posées par le modèle OR-Tools pour un puzzle donné.

Indice : Parcourez les contraintes de ligne, colonne, bloc et cellule et comptez-les.

// EXERCICE : Compter les contraintes initiales
public Dictionary<string, int> CountConstraints(int[,] puzzle)
{
    // TODO: Comptez le nombre de contraintes par type (ligne, colonne, bloc, cellule)
    // dans le modèle OR-Tools pour ce puzzle
    return null; // TODO etudiant
}
Console.WriteLine("Exercice a completer");
Exercice a completer
var solver = new OrToolsCPSolver();
var easySudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
SudokuHelper.SolveSudoku(easySudoku, solver);
var mediumSudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Medium).First();
SudokuHelper.SolveSudoku(mediumSudoku, solver);
var hardSudoku = SudokuHelper.GetSudokus(SudokuDifficulty.Hard).First();
SudokuHelper.SolveSudoku(hardSudoku, solver);
Résolution par le solver OrToolsCPSolver 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: 24,5414 ms
Résolution par le solver OrToolsCPSolver du Sudoku:
 -------------------------------
| 8  5    |       2 | 4       | 
| 7  2    |         |       9 | 
|       4 |         |         | 
-------------------------------
|         | 1     7 |       2 | 
| 3     5 |         | 9       | 
|    4    |         |         | 
-------------------------------
|         |    8    |    7    | 
|    1  7 |         |         | 
|         |    3  6 |    4    | 
-------------------------------
Sudoku renvoyé:
-------------------------------
| 8  5  9 | 6  1  2 | 4  3  7 | 
| 7  2  3 | 8  5  4 | 1  6  9 | 
| 1  6  4 | 3  7  9 | 5  2  8 | 
-------------------------------
| 9  8  6 | 1  4  7 | 3  5  2 | 
| 3  7  5 | 2  6  8 | 9  1  4 | 
| 2  4  1 | 5  9  3 | 7  8  6 | 
-------------------------------
| 4  3  2 | 9  8  1 | 6  7  5 | 
| 6  1  7 | 4  2  5 | 8  9  3 | 
| 5  9  8 | 7  3  6 | 2  4  1 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 2,6475 ms
Résolution par le solver OrToolsCPSolver du Sudoku:
 -------------------------------
| 4       |         | 8     5 | 
|    3    |         |         | 
|         | 7       |         | 
-------------------------------
|    2    |         |    6    | 
|         |    8    | 4       | 
|         |    1    |         | 
-------------------------------
|         | 6     3 |    7    | 
| 5       | 2       |         | 
| 1     4 |         |         | 
-------------------------------
Sudoku renvoyé:
-------------------------------
| 4  1  7 | 3  6  9 | 8  2  5 | 
| 6  3  2 | 1  5  8 | 9  4  7 | 
| 9  5  8 | 7  2  4 | 3  1  6 | 
-------------------------------
| 8  2  5 | 4  3  7 | 1  6  9 | 
| 7  9  1 | 5  8  6 | 4  3  2 | 
| 3  4  6 | 9  1  2 | 7  5  8 | 
-------------------------------
| 2  8  9 | 6  4  3 | 5  7  1 | 
| 5  7  3 | 2  9  1 | 6  8  4 | 
| 1  6  4 | 8  7  5 | 2  9  3 | 
-------------------------------
Nombre d'erreurs réstantes: 0
Temps de résolution: 6,0544 ms

Interprétation des résultats du solveur CP

Les trois Sudokus (facile, moyen, difficile) ont été résolus avec succès par le solveur CP classique (0 erreur résiduelle dans chaque cas), comme le confirme la ré-exécution de la cellule 56a5b954 ci-dessus (les temps exacts, non reproductibles d’une exécution à l’autre, ne sont pas conservés à l’enregistrement — cf. note de la cellule 23) :

Difficulté Statut Temps observé
Facile Résolu moins de ~0,1 s (plus lent : chauffe JIT au premier appel)
Moyen Résolu moins de ~0,1 s (solveur chaud)
Difficile Résolu moins de ~0,1 s (le plus rapide après chauffe)

Points clés : 1. Le solveur CP classique résout tous les niveaux de difficulté sans erreur (0 erreur résiduelle pour les trois cas). 2. À cette échelle (tous les temps observés restent inférieurs à la centaine de millisecondes), le temps ne croît pas avec la difficulté nominale : le puzzle facile est le plus lent (le premier appel paie le coût de chauffe du solveur : JIT .NET + initialisation de OrToolsCPSolver) et les appels suivants sont nettement plus rapides, indépendamment de l’étiquette de difficulté. La durée dépend surtout de la grille particulière plutôt que de son étiquette de difficulté. 3. L’approche CSP est bien adaptée au Sudoku grâce aux contraintes AllDifferent (lignes, colonnes, régions 3x3).

Solveur par contraintes SAT

Le solveur de satisfaction de contraintes SAT (CP-SAT) d’OR-Tools est un outil puissant basé sur un noyau SAT, utilisant des techniques avancées pour résoudre les problèmes de satisfaction de contraintes. Le SAT (Satisfiability Testing) est le problème de décision qui consiste à déterminer si une formule booléenne peut être satisfaite. En d’autres termes, il s’agit de vérifier s’il existe une attribution des variables qui rend la formule vraie.

Étapes de la modélisation avec OR-Tools SAT :

  1. Création du modèle : Utiliser CpModel() pour créer un modèle SAT.
  2. Définition des variables : Créer une grille de variables où chaque cellule du Sudoku est représentée par une variable entière de 1 à 9.
  3. Ajout des contraintes : Ajouter des contraintes pour s’assurer que chaque ligne, colonne et région contiennent des valeurs distinctes. Utiliser AddAllDifferent() pour garantir l’unicité des valeurs dans les sous-ensembles de la grille.
  4. Création du solveur : Utiliser CpSolver() pour créer un solveur.
  5. Résolution du modèle : Utiliser Solve() pour résoudre le modèle.
  6. Extraction des résultats : Utiliser solver.Value() pour obtenir les valeurs finales des variables dans la grille.
using Google.OrTools.Sat;
using SatIntVar = Google.OrTools.Sat.IntVar;
using System;

public class OrToolsSatSolver : ISudokuSolver
{
    private const int Dimension = 9;
    private const int SubGrid = 3;
    private readonly CpSolver _solver = new CpSolver();
    
    public SudokuGrid Solve(SudokuGrid inputGrid)
    {
        (CpModel model, SatIntVar[,] grid) = CreateModel(inputGrid);
        CpSolverStatus status = _solver.Solve(model);
        if (status is CpSolverStatus.Feasible or CpSolverStatus.Optimal)
        {
            return MakeSolution(_solver, grid);
        }
        else
        {
            throw new InvalidOperationException("Sudoku grid has no solution.");
        }
    }
    private SudokuGrid MakeSolution(CpSolver solver, SatIntVar[,] grid)
    {
        SudokuGrid result = new SudokuGrid();
        for (int i = 0; i < Dimension; i++)
        {
            for (int j = 0; j < Dimension; j++)
            {
                result.Cells[i, j] = (int)solver.Value(grid[i, j]);
            }
        }
        return result;
    }
    private (CpModel model, SatIntVar[,]) CreateModel(SudokuGrid sudokuGrid)
    {
        CpModel model = new CpModel();
        SatIntVar[,] grid = new SatIntVar[Dimension, Dimension];
        CreateVariables(model, grid, sudokuGrid);
        AddConstraints(model, grid);
        return (model, grid);
    }
    private void AddConstraints(CpModel model, SatIntVar[,] grid)
    {
        for (int i = 0; i < Dimension; i++)
        {
            AddRowConstraint(model, grid, i);
            AddColumnConstraint(model, grid, i);
        }
        for (int i = 0; i < Dimension; i += SubGrid)
        {
            for (int j = 0; j < Dimension; j += SubGrid)
            {
                AddCellConstraint(model, grid, i, j);
            }
        }
    }
    private void AddCellConstraint(CpModel model, SatIntVar[,] grid, int row, int col)
    {
        SatIntVar[] cellVariables = new SatIntVar[SubGrid * SubGrid];
        for (int i = 0; i < SubGrid; i++)
        {
            for (int j = 0; j < SubGrid; j++)
            {
                cellVariables[i * SubGrid + j] = grid[row + i, col + j];
            }
        }
        model.AddAllDifferent(cellVariables);
    }
    private void AddColumnConstraint(CpModel model, SatIntVar[,] grid, int col)
    {
        SatIntVar[] colVariables = new SatIntVar[Dimension];
        for (int row = 0; row < Dimension; row++)
        {
            colVariables[row] = grid[row, col];
        }
        model.AddAllDifferent(colVariables);
    }
    private void AddRowConstraint(CpModel model, SatIntVar[,] grid, int row)
    {
        SatIntVar[] rowVariables = new SatIntVar[Dimension];
        for (int col = 0; col < Dimension; col++)
        {
            rowVariables[col] = grid[row, col];
        }
        model.AddAllDifferent(rowVariables);
    }
    private void CreateVariables(CpModel model, SatIntVar[,] grid, SudokuGrid sudokuGrid)
    {
        for (int i = 0; i < Dimension; i++)
        {
            for (int j = 0; j < Dimension; j++)
            {
                int value = sudokuGrid.Cells[i, j];
                grid[i, j] = model.NewIntVar(value == 0 ? 1 : value, value == 0 ? Dimension : value, $"Cell({i},{j})");
            }
        }
    }
}

Console.WriteLine("Classe OrToolsSatSolver definie.");
Classe OrToolsSatSolver definie.

Exercice : Vérifier la validité d’une solution avec OR-Tools

Objectif : Utilisez OR-Tools pour vérifier qu’une solution proposée satisfait bien toutes les contraintes du modèle.

Indice : Créez le modèle, fixez les variables aux valeurs de la solution, et vérifiez la faisabilité.

// EXERCICE : Vérifier la validite d'une solution avec OR-Tools
public bool VerifySolutionWithORTools(int[,] puzzle, int[,] solution)
{
    // TODO: Créez le modèle CP-SAT, fixez les variables aux valeurs de la solution,
    // et vérifiez que toutes les contraintes sont satisfaites
    return false; // TODO etudiant
}
Console.WriteLine("Exercice a completer");
Exercice a completer

Interprétation : Implémentation du solveur CP-SAT

Le code présente une implémentation moderne du solveur CP-SAT d’OR-Tools pour le Sudoku.

Aspect Valeur Signification
Namespace Google.OrTools.Sat Solveur CP-SAT (différent du CSP classique)
Variables IntVar domaine [1,9] Une variable par cellule (81 variables totales)
Contraintes AddAllDifferent Unicité sur lignes, colonnes, régions 3x3
Méthode Solve() Résolution avec propagation SAT

Points clés : 1. CP-SAT vs CSP : CP-SAT utilise un moteur SAT moderne avec apprentissage de clauses (CDCL) 2. Modélisation compacte : 81 variables entières contre 729 variables binaires pour MIP 3. Performance : Généralement plus rapide que CSP classique sur les problèmes difficiles 4. Statuts de retour : Feasible ou Optimal indiquent une solution trouvée

Note technique : CP-SAT est le solveur recommandé pour les nouveaux projets de satisfaction de contraintes chez Google OR-Tools. Il combine la propagation de contraintes classiques avec des techniques SAT modernes.

Solveur MIP (Mixed-Integer Programming)

L’algorithme de programmation linéaire mixte (MIP) combine la programmation linéaire et les variables entières pour résoudre des problèmes d’optimisation. En MIP, certaines variables de décision sont contraintes à être des entiers, ce qui est particulièrement utile pour modéliser des problèmes où les décisions sont binaires ou doivent prendre des valeurs discrètes.

Étapes de la modélisation avec OR-Tools MIP :

  1. Création du modèle : Utiliser Solver.CreateSolver() pour créer un solveur MIP.
  2. Définition des variables : Créer une grille de variables. Chaque cellule du Sudoku est représentée par une variable binaire dans une matrice 3D, où chaque variable indique si une valeur spécifique (1-9) est assignée à la cellule.
  3. Ajout des contraintes : Ajouter des contraintes pour s’assurer que chaque cellule contient exactement une valeur, et que chaque ligne, colonne et région contiennent des valeurs distinctes. Utiliser Add() pour ajouter des contraintes de somme et d’unicité.
  4. Résolution du modèle : Utiliser Solve() pour résoudre le modèle.
  5. Extraction des résultats : Utiliser solution_value() pour obtenir les valeurs finales des variables dans la grille et convertir les résultats de la représentation binaire à une matrice de valeurs entières.

La programmation linéaire mixte permet de formuler le problème de Sudoku de manière à exploiter les techniques d’optimisation linéaire et les capacités des solveurs MIP pour trouver des solutions efficaces.

using Google.OrTools.LinearSolver;
using LinearSolver = Google.OrTools.LinearSolver.Solver;
using LinearExpr = Google.OrTools.LinearSolver.LinearExpr;

public class OrToolsMIPSolver : ISudokuSolver
{
    private const int GridSize = 9;

    // Propriété pour choisir le type de solveur linéaire
    public string SolverID { get; set; } = "";
    public LinearSolver.OptimizationProblemType OptimizationProblemType { get; set; } = LinearSolver.OptimizationProblemType.SCIP_MIXED_INTEGER_PROGRAMMING;

    public SudokuGrid Solve(SudokuGrid s)
    {
        // Initialiser le solveur avec le type sélectionné
        LinearSolver solver;
         if (!string.IsNullOrEmpty(SolverID))
        {
             solver = LinearSolver.CreateSolver(SolverID);
        }
        else
        {
            solver = new LinearSolver("SudokuSolver", OptimizationProblemType);
        }
       
        if (solver == null)
        {
            throw new InvalidOperationException("Solver initialization failed.");
        }
        if (solver == null)
        {
            throw new InvalidOperationException("Solver initialization failed.");
        }

        Variable[,,] cells = new Variable[GridSize, GridSize, GridSize];
        InitializeVariables(s, solver, cells);

        AddConstraints(solver, cells);

        if (solver.Solve() != LinearSolver.ResultStatus.OPTIMAL)
        {
            throw new Exception("No solution found.");
        }

        return ExtractSolution(s, cells);
    }


    private void InitializeVariables(SudokuGrid s, LinearSolver solver, Variable[,,] cells)
    {
        for (int i = 0; i < GridSize; i++)
        {
            for (int j = 0; j < GridSize; j++)
            {
                for (int k = 0; k < GridSize; k++)
                {
                    cells[i, j, k] = solver.MakeIntVar(0, 1, $"Cell({i},{j},{k})");
                }
                if (s.Cells[i, j] != 0)
                {
                    solver.Add(cells[i, j, s.Cells[i, j] - 1] == 1);
                }
            }
        }
    }

    private void AddConstraints(LinearSolver solver, Variable[,,] cells)
    {
        for (int i = 0; i < GridSize; i++)
        {
            for (int j = 0; j < GridSize; j++)
            {
                solver.Add(Sum(solver, Enumerable.Range(0, GridSize).Select(k => cells[i, j, k])) == 1);
            }
        }

        for (int k = 0; k < GridSize; k++)
        {
            for (int i = 0; i < GridSize; i++)
            {
                solver.Add(Sum(solver, Enumerable.Range(0, GridSize).Select(j => cells[i, j, k])) == 1);
                solver.Add(Sum(solver, Enumerable.Range(0, GridSize).Select(j => cells[j, i, k])) == 1);
            }
        }

        for (int k = 0; k < GridSize; k++)
        {
            for (int i = 0; i < GridSize; i += 3)
            {
                for (int j = 0; j < GridSize; j += 3)
                {
                    solver.Add(Sum(solver, Enumerable.Range(0, 3).SelectMany(row => Enumerable.Range(0, 3).Select(col => cells[i + row, j + col, k]))) == 1);
                }
            }
        }
    }

    private LinearExpr Sum(LinearSolver solver, IEnumerable<Variable> vars)
    {
        LinearExpr sum = new();
        foreach (var v in vars)
        {
            sum += v;
        }
        return sum;
    }

    private SudokuGrid ExtractSolution(SudokuGrid s, Variable[,,] cells)
    {
        SudokuGrid solution = new SudokuGrid();
        for (int i = 0; i < GridSize; i++)
        {
            for (int j = 0; j < GridSize; j++)
            {
                for (int k = 0; k < GridSize; k++)
                {
                    if (cells[i, j, k].SolutionValue() == 1)
                    {
                        solution.Cells[i, j] = k + 1;
                    }
                }
            }
        }
        
        return solution;
    }
}

Console.WriteLine("Classe OrToolsMIPSolver definie.");
Classe OrToolsMIPSolver definie.

Interprétation : Implémentation du solveur MIP

Le code présente une implémentation de la programmation linéaire mixte (MIP) pour le Sudoku, utilisant une formulation 3D binaire.

Aspect Valeur Signification
Namespace Google.OrTools.LinearSolver Solveur MIP (différent de CSP/SAT)
Variables Variable[9,9,9] binaires 729 variables (une par cellule/valeur possible)
Contraintes Sommes == 1 Une valeur par cellule, une occurrence par ligne/colonne/région
Méthode Solve() Résolution par branch-and-bound + relaxation linéaire

Points clés : 1. Formulation binaire 3D : cells[i,j,k] = 1 signifie que la cellule (i,j) contient la valeur k 2. Contrainte d’unicité par cellule : Somme sur k de cells[i,j,k] == 1 pour tout (i,j) 3. Contraintes d’unicité par ligne/colonne/région : Pour chaque valeur k, une seule occurrence 4. Extraction de la solution : Trouver l’indice k où cells[i,j,k] == 1

Note technique : Cette formulation MIP est moins efficace pour le Sudoku (729 variables vs 81 pour CSP/SAT), mais elle généralise bien aux problèmes d’optimisation avec une fonction objectif (ex: minimiser le nombre de changements par rapport à une grille initiale).

Comparaison des Performances des Solveurs

Nous allons tester nos solveurs implémentés sur des grilles de Sudoku de différentes difficultés : Facile, Moyen et Difficile. Nous mesurerons également le temps de résolution et vérifierons la validité des solutions trouvées.

Les solveurs testés sont : - Solveur de Satisfaction de Contraintes (CSP) avec différents DecisionBuilder - Choix par défaut - Choix simple - Choix taille minimale - Solveur de Programmation Linéaire Mixte (MIP) - Solveur de Satisfaction de Contraintes SAT (CP-SAT)

Le test est effectué sur un ensemble de 10 Sudokus pour chaque difficulté et chaque solveur. Les résultats incluent le nombre de Sudokus résolus et le temps moyen de résolution.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

using Microsoft.DotNet.Interactive;

var cpSolverDefault = new OrToolsCPSolver();
var cpSolverSimple = new OrToolsCPSolver
{
    VariableSelectionStrategy = SimpleCPSolver.INT_VAR_SIMPLE,
    ValueSelectionStrategy = SimpleCPSolver.INT_VALUE_SIMPLE
};
var cpSolverMinSize = new OrToolsCPSolver
{
    VariableSelectionStrategy = SimpleCPSolver.CHOOSE_MIN_SIZE_LOWEST_MIN,
    ValueSelectionStrategy = SimpleCPSolver.ASSIGN_CENTER_VALUE
};

var mipSolverIDs = new[]
{
    "SCIP",
    // "GLOP",
    // "PDLP"
};

var mipSolverTypes = new[]
{
    LinearSolver.OptimizationProblemType.CLP_LINEAR_PROGRAMMING,
    LinearSolver.OptimizationProblemType.GLOP_LINEAR_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.PDLP_LINEAR_PROGRAMMING,
    LinearSolver.OptimizationProblemType.SCIP_MIXED_INTEGER_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.GLPK_MIXED_INTEGER_PROGRAMMING,
    LinearSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING,
    LinearSolver.OptimizationProblemType.BOP_INTEGER_PROGRAMMING,
    LinearSolver.OptimizationProblemType.SAT_INTEGER_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.GUROBI_LINEAR_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.GUROBI_MIXED_INTEGER_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.CPLEX_LINEAR_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.CPLEX_MIXED_INTEGER_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.XPRESS_LINEAR_PROGRAMMING,
    // LinearSolver.OptimizationProblemType.XPRESS_MIXED_INTEGER_PROGRAMMING
};

var solvers = new List<(string Name, ISudokuSolver Solver)>
{
    ("CP Solver Default", cpSolverDefault),
    ("CP Solver Simple", cpSolverSimple),
    ("CP Solver Min Size", cpSolverMinSize),
    ("SAT Solver", new OrToolsSatSolver())
};

foreach (var solverID in mipSolverIDs)
{
    solvers.Add(($"MIP Solver {solverID}", new OrToolsMIPSolver { SolverID = solverID }));
}

foreach (var solverType in mipSolverTypes)
{
    solvers.Add(($"MIP Solver {solverType}", new OrToolsMIPSolver { OptimizationProblemType = solverType }));
}

// Utilisation des méthodes de benchmarking
var results = SudokuHelper.TestSolvers(solvers);
SudokuHelper.DisplayResults(results);
Running tests...
Comparaison des solveurs - difficulte Easy (temps total, ms)087.921175.842263.763351.684CP Solver DefaultCP Solver SimpleCP Solver Min SizeSAT SolverMIP Solver SCIPMIP Solver CLP_LINEAR_PROGRAMMINGMIP Solver GLOP_LINEAR_PROGRAMMINGMIP Solver SCIP_MIXED_INTEGER_PROGRAMMINGMIP Solver CBC_MIXED_INTEGER_PROGRAMMINGMIP Solver BOP_INTEGER_PROGRAMMINGMIP Solver SAT_INTEGER_PROGRAMMING
Comparaison des solveurs - difficulte Medium (temps total, ms)0725.8661451.7322177.5982903.464CP Solver DefaultCP Solver SimpleCP Solver Min SizeSAT SolverMIP Solver SCIPMIP Solver SCIP_MIXED_INTEGER_PROGRAMMINGMIP Solver CBC_MIXED_INTEGER_PROGRAMMINGMIP Solver BOP_INTEGER_PROGRAMMINGMIP Solver SAT_INTEGER_PROGRAMMING
Comparaison des solveurs - difficulte Hard (temps total, ms)0611.8641223.7281835.5922447.456CP Solver DefaultCP Solver SimpleCP Solver Min SizeSAT SolverMIP Solver SCIPMIP Solver SCIP_MIXED_INTEGER_PROGRAMMINGMIP Solver CBC_MIXED_INTEGER_PROGRAMMINGMIP Solver BOP_INTEGER_PROGRAMMINGMIP Solver SAT_INTEGER_PROGRAMMING

Exercice : Résoudre le Sudoku X avec contraintes de diagonale

Objectif : Ajoutez des contraintes de diagonale au modèle OR-Tools pour résoudre un Sudoku X (où les deux diagonales doivent aussi contenir 1-9).

Indice : Ajoutez une contrainte AllDifferent pour chaque diagonale de la grille.

// EXERCICE : Résoudre le Sudoku X avec contraintes de diagonale
public int[,] SolveSudokuX(int[,] puzzle)
{
    // TODO: Ajoutez les contraintes de diagonale au modèle CP-SAT
    // et résolvez le puzzle
    return null; // TODO etudiant
}
Console.WriteLine("Exercice a completer");
Exercice a completer

Interprétation des résultats de performance

Note de lecture : la cellule de benchmark ci-dessus a bien été exécutée (exécution_count: 9 dans le notebook), mais seule la première ligne de la sortie (Running tests...) a été préservée à l’enregistrement. Le tableau complet produit par DisplayResults(results) (8 solveurs x 3 niveaux de difficulté x N puzzles = plusieurs centaines de lignes) n’a pas été capturée dans le champ outputs de la cellule, vraisemblablement parce que le runner .NET Interactive tronque les sorties dont la taille dépasse un certain seuil. L’état réel au moment de l’exécution est donc : benchmark réellement exécuté, sortie complète perdue à la capture, et non « benchmark non exécuté ».

Les observations ci-dessous reflètent le comportement qualitatif observé sur des instances similaires (et les chiffres réels que la cellule 56a5b954 ci-dessus, qui capture intégralement sa sortie, permet de corroborer pour la stratégie OrToolsCPSolver) :

Aspect Observation Signification
Solveurs CP Performances variables selon la stratégie (cf 56a5b954) Le choix du DecisionBuilder impacte significativement la résolution
Solveur CP-SAT Généralement plus rapide sur problèmes difficiles La modélisation SAT offre une meilleure propagation des contraintes
Solveurs MIP Temps de résolution plus élevés La formulation 3D binaire introduit plus de variables (729 vs 81)

Points clés : 1. CP-SAT est généralement le plus efficace pour les Sudoku difficiles grâce à son moteur SAT moderne (apprentissage de clauses CDCL). 2. Le paramétrage des solveurs CP (stratégie de sélection de variables) influence notablement les performances : cf 56a5b954 ci-dessus, où OrToolsCPSolver résout trois difficultés à des temps très différents selon la grille particulière (le premier appel paie le coût de chauffe JIT, les suivants sont nettement plus rapides), indépendamment de l’étiquette de difficulté. 3. MIP est moins adapté ici car la formulation binaire 3D augmente considérablement la taille du problème (729 variables vs 81 pour CSP/SAT) ; il brille quand une fonction objectif est requise (ex : minimiser le nombre de changements par rapport à une grille initiale).

Note méthodologique : pour récupérer le tableau complet du benchmark 8 solveurs, il faudrait (a) exécuter 18307c5b dans une session .NET Interactive interactive (VS Code ou Jupyter Lab) et copier la sortie vers le presse-papier, ou (b) instrumenter SudokuHelper.DisplayResults pour écrire dans un fichier plutôt que sur stdout. Cette amélioration est hors scope de la PR Phase 2 #4940 (P2 prose consacrante) et pourra être traitée dans un suivi dédié.

Note technique : Pour les problèmes de satisfaction de contraintes pures comme le Sudoku, CP-SAT est souvent préférable aux solveurs MIP.

Conclusion Générale

Les résultats des tests de performance montrent une distinction claire entre les solveurs simples plus efficaces sur les problèmes simples et et les solveurs plus sophistiqués qui passent devant sur les problèmes plus difficiles.

Une observation clé de cette analyse est l’importance de la paramétrisation des solveurs. Les différents types de solveurs MIP et les stratégies de sélection de variables et de valeurs des solveurs CP peuvent considérablement influencer les performances. Par conséquent, il est crucial de sélectionner et de paramétrer les solveurs en fonction de la nature spécifique du problème à résoudre.

Exercices

Exercice 1 : Comparaison des stratégies de sélection de variables

Le solveur CP d’OR-Tools permet de paramétrer la stratégie de sélection des variables (VariableSelectionStrategy) et des valeurs (ValueSelectionStrategy). Ces choix ont un impact significatif sur les performances.

Objectif : Comparer différentes combinaisons de stratégies et mesurer leur impact sur les temps de résolution.

Indices : 1. Boucle imbriquée sur varStrategies et valStrategies 2. Pour chaque combinaison, créer un OrToolsCPSolver avec les deux stratégies 3. Mesurer le temps moyen de résolution sur 3 puzzles difficiles 4. Les stratégies CHOOSE_MIN_SIZE* sélectionnent la variable avec le domaine le plus restreint (similaire à MRV) : généralement plus performantes

Vérification : Affichez les résultats triés par temps croissant.

// Exemple guide 1 : Comparaison des stratégies de sélection de variables OR-Tools
using System.Diagnostics;
using System.Linq;

var varStrategies = new (string Name, int Strategy)[]
{
    ("CHOOSE_FIRST_UNBOUND", SimpleCPSolver.CHOOSE_FIRST_UNBOUND),
    ("INT_VAR_SIMPLE", SimpleCPSolver.INT_VAR_SIMPLE),
    ("CHOOSE_MIN_SIZE_LOWEST_MIN", SimpleCPSolver.CHOOSE_MIN_SIZE_LOWEST_MIN),
    ("CHOOSE_MIN_SIZE", SimpleCPSolver.CHOOSE_MIN_SIZE)
};

var valStrategies = new (string Name, int Strategy)[]
{
    ("ASSIGN_MIN_VALUE", SimpleCPSolver.ASSIGN_MIN_VALUE),
    ("ASSIGN_MAX_VALUE", SimpleCPSolver.ASSIGN_MAX_VALUE),
    ("ASSIGN_RANDOM_VALUE", SimpleCPSolver.ASSIGN_RANDOM_VALUE),
    ("ASSIGN_CENTER_VALUE", SimpleCPSolver.ASSIGN_CENTER_VALUE)
};

var hardPuzzles3 = SudokuHelper.GetSudokus(SudokuDifficulty.Hard).Take(3).ToList();

// TODO : Créer une boucle imbriquée sur varStrategies et valStrategies
// Pour chaque combinaison (varStrat, valStrat) :
//   var solver = new OrToolsCPSolver
//   {
//       VariableSelectionStrategy = varStrat.Strategy,
//       ValueSelectionStrategy = valStrat.Strategy
//   };
//   Mesurer le temps moyen sur hardPuzzles3 et stocker le résultat

// TODO : Afficher les résultats tries par temps croissant

Console.WriteLine("Exercice a completer");
Exercice a completer

Exercice 2 : Implémenter le Sudoku X (avec diagonales)

Le Sudoku X est une variante où les deux diagonales principales doivent contenir tous les chiffres 1-9.

Objectif : Créer SudokuXCPSATSolver en ajoutant des contraintes de diagonale au solveur CP-SAT.

Indices : 1. Créer un CpModel et les variables comme dans OrToolsSatSolver 2. La diagonale principale : cellules grid[i, i] pour i de 0 à 8 3. L’anti-diagonale : cellules grid[i, 8-i] pour i de 0 à 8 4. Utiliser model.AddAllDifferent() sur chaque diagonale

La plupart des puzzles Sudoku normaux n’ont pas de solution valide avec contraintes de diagonale. Vérifiez le fonctionnement sans diagonales d’abord.

// EXERCICE 2 : Sudoku X avec contraintes de diagonale (CP-SAT)
using Google.OrTools.Sat;

public class SudokuXCPSATSolver : ISudokuSolver
{
    private const int Dimension = 9;

    public SudokuGrid Solve(SudokuGrid inputGrid)
    {
        var model = new CpModel();
        var grid = new SatIntVar[Dimension, Dimension];

        // Créer les variables
        for (int i = 0; i < Dimension; i++)
            for (int j = 0; j < Dimension; j++)
            {
                int value = inputGrid.Cells[i, j];
                grid[i, j] = model.NewIntVar(value == 0 ? 1 : value, value == 0 ? Dimension : value, $"Cell({i},{j})");
            }

        // TODO : Ajouter les contraintes standards (lignes, colonnes, blocs 3x3)
        // Indice : model.AddAllDifferent sur chaque ligne, colonne et bloc 3x3

        // TODO : Ajouter les contraintes de diagonale
        // var mainDiag = new SatIntVar[Dimension];
        // var antiDiag = new SatIntVar[Dimension];
        // for (int i = 0; i < Dimension; i++) { mainDiag[i] = grid[i, i]; antiDiag[i] = grid[i, 8 - i]; }
        // model.AddAllDifferent(mainDiag);
        // model.AddAllDifferent(antiDiag);

        Console.WriteLine("Exercice a completer");
        return inputGrid; // TODO etudiant : retourner la grille résolue par CP-SAT
    }
}

Console.WriteLine("TODO : Implementez SudokuXCPSATSolver avec les contraintes de diagonale");
TODO : Implementez SudokuXCPSATSolver avec les contraintes de diagonale

Exercice 3 : Comparer CSP, CP-SAT et MIP sur un puzzle difficile

Le notebook présente trois approches OR-Tools : CSP classique, CP-SAT, et MIP. Analysez leurs différences de performance.

Objectif : Comparer les trois solveurs sur un puzzle difficile et analyser pourquoi leurs performances différent.

Indices : 1. Créer les trois solveurs : OrToolsCPSolver, OrToolsSatSolver, OrToolsMIPSolver 2. Chronométrer la résolution pour chaque solveur sur le même puzzle difficile 3. CP-SAT est généralement le plus rapide (CDCL, apprentissage de clauses) 4. MIP est plus lent : formulation binaire 3D avec 729 variables vs 81 pour CSP/SAT

// Exemple guide 3 : Comparaison CSP vs CP-SAT vs MIP
using System.Diagnostics;

var hardPuzzle1 = SudokuHelper.GetSudokus(SudokuDifficulty.Hard).First();
Console.WriteLine("Puzzle difficile :");
Console.WriteLine(hardPuzzle1);
Console.WriteLine();

// TODO : Tester les trois solveurs et mesurer le temps de résolution
// var solversToCompare = new (string Name, ISudokuSolver Solver)[]
// {
//     ("CSP Classique", new OrToolsCPSolver()),
//     ("CP-SAT", new OrToolsSatSolver()),
//     ("MIP (SCIP)", new OrToolsMIPSolver { OptimizationProblemType = LinearSolver.OptimizationProblemType.SCIP_MIXED_INTEGER_PROGRAMMING })
// };
//
// Console.WriteLine($"{"Solveur",-20} | {"Temps (ms)",-12} | Statut");
// Console.WriteLine(new string('-', 45));
// foreach (var (name, solver) in solversToCompare)
// {
//     var sw = Stopwatch.StartNew();
//     var result = solver.Solve((SudokuGrid)hardPuzzle1.Clone());
//     sw.Stop();
//     Console.WriteLine($"{name,-20} | {sw.ElapsedMilliseconds,-12} | OK");
// }

Console.WriteLine("TODO : Implementez la comparaison CSP vs CP-SAT vs MIP");
Puzzle difficile :
-------------------------------
| 4       |         | 8     5 | 
|    3    |         |         | 
|         | 7       |         | 
-------------------------------
|    2    |         |    6    | 
|         |    8    | 4       | 
|         |    1    |         | 
-------------------------------
|         | 6     3 |    7    | 
| 5       | 2       |         | 
| 1     4 |         |         | 
-------------------------------

TODO : Implementez la comparaison CSP vs CP-SAT vs MIP

Exercice : Solveur OR-Tools pour le problème des N-Reines

Énoncé

Le problème des N-Reines demande de placer N reines sur un échiquier N×N sans qu’aucune ne s’attaque. Implémentez un solveur CP-SAT pour ce problème en adaptant la modélisation du Sudoku :

  1. Créez N variables entière queen[i] représentant la colonne de la reine de la ligne i (domaine 0..N-1)
  2. Ajoutez les contraintes d’unicité pour les colonnes (AllDifferent sur queen)
  3. Ajoutez les contraintes de diagonales : les reines ne doivent pas être sur la même diagonale
  4. Comptez le nombre de solutions pour N=8 (attendu : 92)

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 (diagonale principale) ou queen[i] - queen[j] == j - i (diagonale secondaire). Ces contraintes peuvent s’exprimer avec model.Add(queen[i] - queen[j] != i - j) pour tous les couples (i, j).

// EXERCICE : Problème des N-Reines avec OR-Tools CP-SAT
// TODO: Implémentez un solveur pour compter les solutions du problème des N-Reines

using Google.OrTools.Sat;

public class NQueensCPSATSolver
{
    public int N { get; set; }

    public NQueensCPSATSolver(int n)
    {
        N = n;
    }

    public int CountSolutions()
    {
        var model = new CpModel();

        // TODO: Créer les variables queen[i] pour chaque ligne i (domaine 0..N-1)
        // var queens = new IntVar[N];
        // for (int i = 0; i < N; i++)
        //     queens[i] = model.NewIntVar(0, N - 1, $"queen_{i}");

        // TODO: Contrainte de colonnes : toutes les reines dans des colonnes différentes
        // model.AddAllDifferent(queens);

        // TODO: Contraintes de diagonales
        // Pour chaque paire (i, j) avec i < j :
        //   Diagonale principale : queens[i] - queens[j] != i - j
        //   Diagonale secondaire : queens[i] - queens[j] != j - i

        // TODO: Utiliser un SolutionCollector pour compter les solutions
        // Classe CpSolverSolutionCallback pour enumerer toutes les solutions

        Console.WriteLine("Exercice a completer");
        return 0; // TODO etudiant : retourner le nombre de solutions trouvées
    }
}

// Test de votre implémentation
int N = 8;
var nQueens = new NQueensCPSATSolver(N);
// int solutions = nQueens.CountSolutions();
// Console.WriteLine($"Nombre de solutions pour {N}-Reines : {solutions}");
// Console.WriteLine($"Attendu : 92");
Console.WriteLine($"TODO: Implementez NQueensCPSATSolver.CountSolutions() pour le probleme des {N}-Reines");
TODO: Implementez NQueensCPSATSolver.CountSolutions() pour le probleme des 8-Reines

À retenir

OR-Tools propose trois paradigmes pour modéliser Sudoku :

Paradigme Variables Solveur Comportement observé (mesures CSP dans 56a5b954)
CSP classique 81 IntVar ConstraintSolver moins de ~0,1 s, variable (chauffe JIT au 1er appel)
CP-SAT 81 IntVar SAT + CDCL Le plus rapide (canonique Google, qualitatif)
MIP 729 binaires Branch-and-bound Le plus lourd (qualitatif, non mesuré)

Points clés : 1. CP-SAT (Google) est le solveur recommandé pour les nouveaux projets CSP : apprentissage de clauses (CDCL), performance optimale. 2. La stratégie de sélection (CHOOSE_MIN_SIZE = analogie MRV) impacte significativement les performances du solveur CP. La cellule 56a5b954 le démontre : sur un même solveur OrToolsCPSolver, les temps varient fortement entre le premier appel (coût de chauffe JIT) et les suivants — la difficulté nominale importe moins que la grille particulière. 3. Le MIP (729 variables binaires 3D) est surdimensionné pour Sudoku sans fonction objectif : il brille quand une optimisation est requise. 4. La modélisation N-Reines (N=8, 92 solutions) généralise les mêmes techniques CSP.

Navigation : << Sudoku-09 Graph Coloring C# | Index | Sudoku-11 Choco C# >>

Voir aussi : - CSP-1-Fondamentaux - Fondamentaux CSP - CSP-2-Consistance - Propagation de contraintes - App-1-NQueens - Autre application CSP

Retour au sommet