App-6 - Demineur (C#) : CSP, probabilites et NP-completude

Jumeau C# du notebook App-6-Minesweeper.ipynb. Marathon parite .NET ⇄ Python (#4956), EPIC #3801 Prong B. Le Demineur modélisé comme CSP : solveur par règles (Rule 1/2), solveur CSP (énumération backtracking from-scratch, pas de lib python-constraint), solveur probabiliste. Implémenté from-scratch en C# pur (BCL seule, 0 NuGet, matplotlib → visualisation ASCII).

Navigation : << App-5-Timetabling | App-7-Wordle >> | Twin Python | Index CSP

Kernel : .NET 9.0 + dotnet-interactive (.net-csharp)

---

Introduction

Le Démineur est un problème de contraintes : chaque chiffre révélé contraint ses voisins inconnus. Ce notebook C# accompagne le twin Python et fournit :

1. Représentation du plateau (génération, révélation en cascade, marquage).
2. Solveur par règles (déductions locales Rule 1 / Rule 2).
3. Solveur CSP — énumération backtracking from-scratch de toutes les affectations cohérentes de la frontière binaire (le twin Python délègue à python-constraint.Problem + ExactSumConstraint + getSolutions()).
4. Solveur probabiliste (règles → CSP → choix de la cellule à P(mine) minimale).
5. Benchmark comparant les trois approches sur N parties.

Pourquoi le CSP intéressant en IA ?

Le Démineur est NP-complet (Kaye 2000) : trouver la stratégie gagnante optimale est intrinsèquement dur. Les solveurs ci-dessous illustrent la hiérarchie classique raisonnement-contraint / recherche exhaustive / décision probabiliste sous incertitude.

Objectifs d’apprentissage

1. Modéliser le Démineur comme un CSP binaire (frontière de cellules inconnues).
2. Implémenter les règles de déduction locale (Rule 1, Rule 2).
3. Énumérer les solutions d’un CSP binaire par backtracking from-scratch (sans lib externe) — comprendre la mécanique que python-constraint cache.
4. Calculer la probabilité de mine par cellule (fréquence sur les solutions).
5. Combiner règles + CSP + probabilités en une stratégie hybride.

Prerequis

• Notions de CSP (variables, domaine, contraintes) — voir App-1-NQueens.
• Récursion / backtracking.
• .NET 9.0 + dotnet-interactive.

Duree estimee : 50 minutes

Source

• Kaye, R. Minesweeper is NP-complete (Mathematical Intelligencer, 2000).
• Twin Python : App-6-Minesweeper.ipynb.

1. Representation du plateau

MinesweeperBoard : grille rows x cols avec un ensemble de mines, un tableau d’indices (numbers[r,c] = nombre de mines voisines), un ensemble de cellules révélées et un ensemble de cellules marquées (drapeaux). La révélation d’un 0 propage en cascade (flood-fill) aux voisins.

using System;
using System.Collections.Generic;
using System.Linq;

public class MinesweeperBoard
{
    public int Rows, Cols, NMines;
    public HashSet<(int r, int c)> Mines = new();
    public int[,] Numbers;          // nombre de mines voisines
    public HashSet<(int r, int c)> Revealed = new();
    public HashSet<(int r, int c)> Flagged = new();
    public bool GameOver, Won;
    private static readonly (int r, int c)[] Offsets = {
        (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)
    };

    public MinesweeperBoard(int rows, int cols, int nMines, (int r,int c)? safeCell, Random rng)
    {
        Rows = rows; Cols = cols; NMines = nMines;
        Numbers = new int[rows, cols];
        // Cellules candidates (exclure safe_cell + ses voisins pour un premier clic sûr)
        var excluded = new HashSet<(int r, int c)>();
        if (safeCell is { } sc) { excluded.Add(sc); foreach (var n in Neighbors(sc.r, sc.c)) excluded.Add(n); }
        var candidates = new List<(int r, int c)>();
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
            if (!excluded.Contains((r,c))) candidates.Add((r,c));
        // Echantillonner nMines mines (Fisher-Yates partiel)
        for (int i = 0; i < Math.Min(nMines, candidates.Count); i++) {
            int j = rng.Next(i, candidates.Count);
            (candidates[i], candidates[j]) = (candidates[j], candidates[i]);
            Mines.Add(candidates[i]);
        }
        // Calculer les indices
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
            if (!Mines.Contains((r,c))) {
                int cnt = 0; foreach (var (nr,nc) in Neighbors(r,c)) if (Mines.Contains((nr,nc))) cnt++;
                Numbers[r,c] = cnt;
            }
    }

    public List<(int r, int c)> Neighbors(int r, int c) {
        var res = new List<(int r, int c)>(8);
        foreach (var (dr,dc) in Offsets) {
            int nr = r+dr, nc = c+dc;
            if (nr >= 0 && nr < Rows && nc >= 0 && nc < Cols) res.Add((nr,nc));
        }
        return res;
    }

    public bool Reveal(int r, int c) {
        if (Revealed.Contains((r,c)) || Flagged.Contains((r,c))) return true;
        if (Mines.Contains((r,c))) { GameOver = true; return false; }
        Revealed.Add((r,c));
        if (Numbers[r,c] == 0)
            foreach (var (nr,nc) in Neighbors(r,c))
                if (!Revealed.Contains((nr,nc))) Reveal(nr,nc);
        int safeCells = Rows*Cols - Mines.Count;
        if (Revealed.Count == safeCells) Won = true;
        return true;
    }

    public void Flag(int r, int c) {
        if (Revealed.Contains((r,c))) return;
        if (!Flagged.Add((r,c))) Flagged.Remove((r,c));  // toggle
    }

    public List<(int r,int c)> UnknownNeighbors(int r, int c) =>
        Neighbors(r,c).Where(p => !Revealed.Contains(p) && !Flagged.Contains(p)).ToList();
    public List<(int r,int c)> FlaggedNeighbors(int r, int c) =>
        Neighbors(r,c).Where(p => Flagged.Contains(p)).ToList();
    public int RemainingMines => NMines - Flagged.Count;

    public MinesweeperBoard Copy() {
        var b = new MinesweeperBoard(Rows, Cols, 0, null, null) {
            Rows = Rows, Cols = Cols, NMines = NMines, Numbers = (int[,])Numbers.Clone(),
            Mines = new HashSet<(int r, int c)>(Mines), Revealed = new HashSet<(int r, int c)>(Revealed),
            Flagged = new HashSet<(int r, int c)>(Flagged), GameOver = GameOver, Won = Won
        };
        return b;
    }
}

// Plateau de demonstration : 8x8, 10 mines, premier clic (4,4) garantit sur.
var rng0 = new Random(1);
var board0 = new MinesweeperBoard(8, 8, 10, safeCell: (4,4), rng0);
board0.Reveal(4, 4);
Console.WriteLine($"Plateau : {board0.Rows}x{board0.Cols}, {board0.NMines} mines");
Console.WriteLine($"Cellules revelees apres le premier clic : {board0.Revealed.Count}");
Console.WriteLine($"Cellules restantes (inconnues)          : {board0.Rows*board0.Cols - board0.Revealed.Count}");
Console.WriteLine($"Mines a trouver                          : {board0.RemainingMines}");

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

Plateau : 8x8, 10 mines
Cellules revelees apres le premier clic : 15
Cellules restantes (inconnues)          : 49
Mines a trouver                          : 10

2. Visualisation ASCII du plateau

Le twin Python trace le plateau en couleurs avec matplotlib. En C# pur (sans lib de plot), on visualise avec une grille ASCII : . pour inconnu, chiffre pour révélé, F pour drapeau, * pour mine (en mode debug).

// Visualisation ASCII d'un plateau de Demineur.
void DrawBoard(MinesweeperBoard b, string title, bool showMines = false) {
    Console.WriteLine($"--- {title} ---");
    Console.Write("   ");
    for (int c = 0; c < b.Cols; c++) Console.Write(c % 10);
    Console.WriteLine();
    for (int r = 0; r < b.Rows; r++) {
        Console.Write($"{r % 10}: ");
        for (int c = 0; c < b.Cols; c++) {
            var p = (r, c);
            if (b.Revealed.Contains(p))
                Console.Write(b.Numbers[r, c] == 0 ? ' ' : b.Numbers[r, c].ToString()[0]);
            else if (b.Flagged.Contains(p)) Console.Write('F');
            else if (showMines && b.Mines.Contains(p)) Console.Write('*');
            else Console.Write('.');
        }
        Console.WriteLine();
    }
    Console.WriteLine();
}

DrawBoard(board0, "Etat apres le premier clic (4,4)");
DrawBoard(board0, "Plateau complet (mines revelees)", showMines: true);

--- Etat apres le premier clic (4,4) ---
   01234567
0: ........
1: ........
2: ...2222.
3: ...1  1.
4: ...1 12.
5: ...112..
6: ........
7: ........

--- Plateau complet (mines revelees) ---
   01234567
0: ..*...*.
1: ....**..
2: ...2222*
3: ..*1  1.
4: ...1 12.
5: ...112**
6: ....*...
7: .....*..

3. Solveur par règles simples

Deux règles locales suffisantes pour de nombreuses situations :

• Règle 1 : si le nombre de mines restantes à placer autour d’une cellule révélée égale le nombre de voisins inconnus, alors tous les inconnus sont des mines.
• Règle 2 : s’il ne reste aucune mine à placer autour d’une cellule révélée, alors tous les inconnus sont sûrs.

public class RuleBasedSolver
{
    public MinesweeperBoard Board;
    public List<(string kind, (int r,int c) cell, (int r,int c) src)> MovesLog = new();

    public RuleBasedSolver(MinesweeperBoard board) { Board = board; }

    public bool SolveStep() {
        bool progress = false;
        for (int r = 0; r < Board.Rows; r++) for (int c = 0; c < Board.Cols; c++) {
            if (!Board.Revealed.Contains((r,c))) continue;
            int num = Board.Numbers[r, c];
            if (num == 0) continue;
            var unknown = Board.UnknownNeighbors(r, c);
            var flagged = Board.FlaggedNeighbors(r, c);
            int remaining = num - flagged.Count;
            if (remaining == unknown.Count && unknown.Count > 0) {
                foreach (var (ur,uc) in unknown) { Board.Flag(ur, uc); MovesLog.Add(("flag", (ur,uc), (r,c))); progress = true; }
            } else if (remaining == 0 && unknown.Count > 0) {
                foreach (var (ur,uc) in unknown) {
                    bool safe = Board.Reveal(ur, uc); MovesLog.Add(("reveal", (ur,uc), (r,c)));
                    if (!safe) return false; progress = true;
                }
            }
        }
        return progress;
    }

    public int Solve(int maxIter = 100) {
        int i;
        for (i = 0; i < maxIter; i++) {
            if (Board.GameOver || Board.Won) break;
            if (!SolveStep()) break;
        }
        return i + 1;
    }
}

// Test sur le plateau de demonstration.
var boardRules = board0.Copy();
var ruleSolver = new RuleBasedSolver(boardRules);
int iters = ruleSolver.Solve();
Console.WriteLine($"Regles : {iters} iterations, {ruleSolver.MovesLog.Count} deductions");
Console.WriteLine($"Cellules revelees : {boardRules.Revealed.Count}/{boardRules.Rows*boardRules.Cols - boardRules.NMines} sures");
Console.WriteLine($"Drapeaux poses    : {boardRules.Flagged.Count}/{boardRules.NMines}");
Console.WriteLine($"Partie gagnee ?   : {boardRules.Won}");
DrawBoard(boardRules, "Apres solveur par regles");

Regles : 2 iterations, 1 deductions
Cellules revelees : 15/54 sures
Drapeaux poses    : 1/10
Partie gagnee ?   : False
--- Apres solveur par regles ---
   01234567
0: ........
1: ........
2: ...2222.
3: ...1  1.
4: ...1 12.
5: ...112F.
6: ........
7: ........

4. Solveur CSP — enumeration backtracking from-scratch

C’est le coeur du Prong B. Le twin Python construit un Problem via la lib python-constraint, ajoute des ExactSumConstraint(remaining) et appelle getSolutions(). Ici on implémente manuellement l’énumération :

1. Frontière = cellules inconnues adjacentes à une cellule révélée.
2. Variables binaires : chaque cellule-frontière vaut 0 (sûre) ou 1 (mine).
3. Contraintes : pour chaque cellule révélée non-nulle, la somme de ses voisins-frontière inconnus = remaining (indice − drapeaux déjà posés).
4. Backtracking : on instancie les variables une par une (0 puis 1), on vérifie chaque contrainte dès que toutes ses variables sont assignées, on élague toute branche violant une contrainte. On collecte toutes les solutions complètes.
5. Déduction : une cellule forcée sûre (mine) = valant 0 (1) dans toutes les solutions.

La complexité est O(2^k) pour une frontière de taille k ; on plafonne k pour garder un runtime pédagogique (le twin Python bénéficie de la propagation de la lib, ici on voit la recherche brute).

public class CSPSolver
{
    public MinesweeperBoard Board;
    public CSPSolver(MinesweeperBoard board) { Board = board; }

    public HashSet<(int r, int c)> Frontier() {
        var f = new HashSet<(int r, int c)>();
        foreach (var (r,c) in Board.Revealed)
            foreach (var n in Board.Neighbors(r,c))
                if (!Board.Revealed.Contains(n) && !Board.Flagged.Contains(n)) f.Add(n);
        return f;
    }

    // Retourne la liste des contraintes : (variables impliquees, somme exacte attendue).
    public List<(List<(int r, int c)> vars, int sum)> Constraints(HashSet<(int r, int c)> frontier) {
        var res = new List<(List<(int r, int c)>, int)>();
        foreach (var (r,c) in Board.Revealed) {
            int num = Board.Numbers[r, c];
            if (num == 0) continue;
            var unknown = Board.UnknownNeighbors(r, c);
            var inFront = unknown.Where(u => frontier.Contains(u)).ToList();
            if (inFront.Count == 0) continue;
            int remaining = num - Board.FlaggedNeighbors(r, c).Count;
            res.Add((inFront, remaining));
        }
        return res;
    }

    // Enumeration backtracking de toutes les solutions. Retourne une liste de
    // dictionnaires (cellule -> 0/1). Plafonne la taille de frontiere.
    public List<Dictionary<(int r, int c), int>> AllSolutions(int maxFrontier = 22) {
        var frontier = Frontier().ToList();
        if (frontier.Count == 0 || frontier.Count > maxFrontier) return new();
        var constraints = Constraints(frontier.ToHashSet());
        var varIdx = new Dictionary<(int r, int c), int>();
        for (int i = 0; i < frontier.Count; i++) varIdx[frontier[i]] = i;
        // Pour chaque contrainte : liste d'indices + somme
        var cIdx = constraints.Select(c => (c.vars.Select(v => varIdx[v]).ToList(), c.sum)).ToList();
        // Ordre : pour chaque index, quelles contraintes deviennent verifiables quand il est assigne en dernier
        var assign = new int[frontier.Count];
        var solutions = new List<Dictionary<(int r, int c), int>>();
        void Dfs(int pos) {
            if (pos == frontier.Count) {
                // Toutes contraintes deja verifiees en cours ; enregistrer
                var sol = new Dictionary<(int r, int c), int>();
                for (int i = 0; i < frontier.Count; i++) sol[frontier[i]] = assign[i];
                solutions.Add(sol);
                return;
            }
            for (int v = 0; v <= 1; v++) {
                assign[pos] = v;
                // Verifier toute contrainte dont la variable de plus grand index == pos
                bool ok = true;
                foreach (var (vars, sum) in cIdx) {
                    int maxI = vars.Max();
                    if (maxI == pos) {  // contrainte complete a ce stade
                        int s = 0; foreach (var vi in vars) s += assign[vi];
                        if (s != sum) { ok = false; break; }
                    }
                }
                if (ok) Dfs(pos + 1);
            }
        }
        Dfs(0);
        return solutions;
    }

    // Deduit les cellules forcees a partir de toutes les solutions.
    public (HashSet<(int r, int c)> safe, HashSet<(int r, int c)> mines) Solve(out List<Dictionary<(int r, int c),int>> sols) {
        sols = AllSolutions();
        var safe = new HashSet<(int r, int c)>();
        var mines = new HashSet<(int r, int c)>();
        if (sols.Count == 0) return (safe, mines);
        var frontier = sols[0].Keys.ToList();
        foreach (var cell in frontier) {
            var vals = sols.Select(s => s[cell]).Distinct().ToList();
            if (vals.Count == 1) {
                if (vals[0] == 0) safe.Add(cell); else mines.Add(cell);
            }
        }
        return (safe, mines);
    }

    // Probabilite de mine par cellule = freq(mines) sur les solutions.
    public Dictionary<(int r, int c), double> Probabilities(List<Dictionary<(int r, int c),int>> sols) {
        var probs = new Dictionary<(int r, int c), double>();
        if (sols.Count == 0) return probs;
        var cells = sols[0].Keys;
        foreach (var cell in cells) {
            int mineCount = sols.Count(s => s[cell] == 1);
            probs[cell] = (double)mineCount / sols.Count;
        }
        return probs;
    }
}

// Demonstration : partir du plateau bloque par les regles et deduire via CSP.
var boardCsp = board0.Copy();
var rs = new RuleBasedSolver(boardCsp); rs.Solve();
Console.WriteLine($"Apres regles : {boardCsp.Revealed.Count} revelees, {boardCsp.Flagged.Count} drapeaux, gagne={boardCsp.Won}");
var csp = new CSPSolver(boardCsp);
var frontier = csp.Frontier();
var constraints = csp.Constraints(frontier);
Console.WriteLine($"Frontiere CSP : {frontier.Count} cellules, {constraints.Count} contraintes");
var (safe, mines) = csp.Solve(out var sols);
Console.WriteLine($"Solutions CSP enumerees : {sols.Count}");
Console.WriteLine($"Cellules forcees sures  : {safe.Count}");
Console.WriteLine($"Cellules forcees mines  : {mines.Count}");
if (frontier.Count > 0 && frontier.Count <= 12) {
    Console.Write("Frontiere : ");
    foreach (var p in frontier.Take(12)) Console.Write($"{p} ");
    Console.WriteLine();
}

Apres regles : 15 revelees, 1 drapeaux, gagne=False
Frontiere CSP : 19 cellules, 11 contraintes
Solutions CSP enumerees : 23
Cellules forcees sures  : 0
Cellules forcees mines  : 0

4bis. Tranche 2 — solveur CSP via OR-Tools CP-SAT

La §4 ci-dessus implémente le solveur CSP à la main : énumération backtracking des 2^k affectations d’une frontière de taille k. C’est fidèle au concept, mais le coût explose et la recherche reste brute (aucune propagation). Le twin Python délègue, lui, cette énumération à la lib python-constraint (getSolutions()).

Cette tranche branche le vrai moteur de production de l’écosystème .NET : Google OR-Tools et son solveur CP-SAT. On reprend exactement le même modèle CSP (variables binaires 0/1 par cellule-frontière, contraintes ExactSum sur les voisins), mais on laisse CP-SAT faire le travail de propagation + apprentissage de clauses (CDCL) qu’un backtracking manuel ne sait pas faire.

Deux apports pédagogiques du moteur, que le solveur §4 from-scratch n’a pas :

1. Déduction par test d’inconsistance (UNSAT). Pour savoir si une cellule v est forcée, on n’énumère plus les 2^k solutions : on teste si v == 0 est réalisable, puis si v == 1 l’est. Si l’un est INFEASIBLE, v est forcée à l’autre valeur. C’est O(k) résolutions CP-SAT (chacune tronquée par propagation) au lieu de O(2^k) — l’apprentissage de clauses de CP-SAT prouve l’inconsistance sans explorer l’arbre. La Démo 1 confirme le verdict §4 par cette voie indépendante.
2. Contrainte globale sur le total des mines. Le solveur §4 n’utilise que les contraintes locales (une par cellule révélée). CP-SAT accepte en plus une contrainte globale « la somme des mines de la frontière ≤ mines restantes » — c’est l’objectif de l’Exercice 1 ci-dessous, qu’un moteur CSP intègre nativement alors qu’il demanderait une refonte du backtracking manuel. La Démo 2 la mobilise.

Verdict SOTA (Prong A). OR-Tools CP-SAT est le solveur CSP/SAT de production du dépôt (déjà bridgé sur App-1, App-8, App-10, Sudoku-09…). La §4 from-scratch reste pour enseigner la mécanique de la recherche ; cette tranche montre le moteur réel qui propage et qui passe à l’échelle. bridge_verdict: RECOVERABLE-LOCAL — l’écart était comblable par un NuGet first-class, c’est fait.

// === Tranche 2 : solveur CSP via OR-Tools CP-SAT (pont moteur de production) ===
// Reprend le modele CSP de la §4 (variables binaires frontieres, contraintes
// ExactSum) et delegue la deduction a Google.OrTools CP-SAT.
#r "nuget: Google.OrTools"
using Google.OrTools.Sat;

// OrToolsCSPSolver : deduction par propagation (tests UNSAT), la technique
// qu'un moteur CSP apporte et qu'un backtracking scolaire (§4, 2^k) n'a pas.
public class OrToolsCSPSolver
{
    public MinesweeperBoard Board;
    public OrToolsCSPSolver(MinesweeperBoard board) { Board = board; }

    // Reutilise la definition de frontiere et de contraintes de CSPSolver.
    public HashSet<(int r, int c)> Frontier() => new CSPSolver(Board).Frontier();
    public List<(List<(int r, int c)> vars, int sum)> Constraints(HashSet<(int r, int c)> f)
        => new CSPSolver(Board).Constraints(f);

    // Construit le modele CP-SAT : BoolVar par cellule-frontiere, contrainte
    // LinearExpr.Sum(voisins) == remaining pour chaque cellule revelee.
    // withGlobalTotal : ajoute la contrainte globale (Exercice 1) "somme des mines
    // de la frontiere <= RemainingMines" -- hors-portee du from-scratch, natif CP-SAT.
    private (CpModel model, Dictionary<(int r, int c), BoolVar> vars) BuildModel(bool withGlobalTotal = false)
    {
        var frontier = Frontier();
        var model = new CpModel();
        var vars = new Dictionary<(int r, int c), BoolVar>();
        foreach (var cell in frontier) vars[cell] = model.NewBoolVar($"m_{cell.r}{cell.c}");
        foreach (var (vs, sum) in Constraints(frontier))
        {
            var terms = vs.Where(v => vars.ContainsKey(v)).Select(v => (LinearExpr)vars[v]).ToArray();
            if (terms.Length > 0) model.Add(LinearExpr.Sum(terms) == sum);
        }
        if (withGlobalTotal && frontier.Count > 0)
        {
            var allTerms = frontier.Select(c => (LinearExpr)vars[c]).ToArray();
            model.Add(LinearExpr.Sum(allTerms) <= Board.RemainingMines);
        }
        return (model, vars);
    }

    // Deduction par tests UNSAT : une cellule est FORCEE si v==0 (ou v==1) est
    // INFEASIBLE. O(k) resolutions CP-SAT tronquees par propagation (CDCL) --
    // c'est l'apprentissage de clauses qu'un backtracking manuel n'a pas.
    // Retourne (safe, mines, status) ; status<0 si le modele de base est vide/infeasible.
    public (HashSet<(int r, int c)> safe, HashSet<(int r, int c)> mines, int status) DeduceByUnsat(bool withGlobalTotal = false)
    {
        var safe = new HashSet<(int r, int c)>();
        var mines = new HashSet<(int r, int c)>();
        var solver = new CpSolver();
        var (baseModel, _) = BuildModel(withGlobalTotal);
        var baseStatus = solver.Solve(baseModel);
        if (baseStatus == CpSolverStatus.Infeasible) return (safe, mines, -1);
        if (baseStatus == CpSolverStatus.Unknown) return (safe, mines, -2);
        foreach (var cell in Frontier())
        {
            var (mSafe, vSafe) = BuildModel(withGlobalTotal); mSafe.Add(vSafe[cell] == 0);
            var (mMine, vMine) = BuildModel(withGlobalTotal); mMine.Add(vMine[cell] == 1);
            var sSafe = solver.Solve(mSafe);
            var sMine = solver.Solve(mMine);
            if (sSafe == CpSolverStatus.Infeasible) mines.Add(cell);      // v==0 impossible -> mine
            else if (sMine == CpSolverStatus.Infeasible) safe.Add(cell);  // v==1 impossible -> safe
        }
        return (safe, mines, 0);
    }
}

// DÉMO 1 : meme plateau bloque que la §4, deduction par propagation CP-SAT.
// Doit confirmer le verdict du from-scratch (0 forcees sur ce plateau a ce stade)
// par une VOIE INDEPENDANTE (propagation + UNSAT, pas enumeration brute).
var boardOt = board0.Copy();
var rsOt = new RuleBasedSolver(boardOt); rsOt.Solve();
var otFrontier0 = new OrToolsCSPSolver(boardOt).Frontier();
Console.WriteLine($"--- Démo 1 : déduction OR-Tools CP-SAT (tests UNSAT), frontière={otFrontier0.Count} ---");
var swOt = System.Diagnostics.Stopwatch.StartNew();
var (safeOt, minesOt, stOt) = new OrToolsCSPSolver(boardOt).DeduceByUnsat();
swOt.Stop();
Console.WriteLine($"Cellules forcées sûres  : {safeOt.Count}");
Console.WriteLine($"Cellules forcées mines  : {minesOt.Count}");
Console.WriteLine($"Temps                   : {swOt.Elapsed.TotalMilliseconds:F1} ms");
Console.WriteLine("(Le solveur §4 from-scratch trouvait aussi 0 forcées sur ce plateau :");
Console.WriteLine(" confirmation indépendante par propagation CP-SAT, sans énumérer 2^k.)");

// DÉMO 2 : avec la contrainte GLOBALE total-mines (Exercice 1, TODO étudiant).
// Le solveur §4 n'utilise que les contraintes locales ; CP-SAT l'accepte nativement
// et restreint l'espace, ce qui peut révéler des cellules forcées supplémentaires.
Console.WriteLine($"--- Démo 2 : même déduction AVEC contrainte globale (RemainingMines={boardOt.RemainingMines}) ---");
var swG = System.Diagnostics.Stopwatch.StartNew();
var (safeG, minesG, stG) = new OrToolsCSPSolver(boardOt).DeduceByUnsat(withGlobalTotal: true);
swG.Stop();
Console.WriteLine($"Cellules forcées sûres  : {safeG.Count}  (avec contrainte globale)");
Console.WriteLine($"Cellules forcées mines  : {minesG.Count}  (avec contrainte globale)");
Console.WriteLine($"Temps                   : {swG.Elapsed.TotalMilliseconds:F1} ms");
Console.WriteLine("(La contrainte globale restreint l'espace : le compte de forcées peut augmenter.)");

Installed Packages

• Google.OrTools, 9.15.6755

--- Démo 1 : déduction OR-Tools CP-SAT (tests UNSAT), frontière=19 ---
Cellules forcées sûres  : 0
Cellules forcées mines  : 0
Temps                   : 668,9 ms
(Le solveur §4 from-scratch trouvait aussi 0 forcées sur ce plateau :
 confirmation indépendante par propagation CP-SAT, sans énumérer 2^k.)
--- Démo 2 : même déduction AVEC contrainte globale (RemainingMines=9) ---
Cellules forcées sûres  : 0  (avec contrainte globale)
Cellules forcées mines  : 0  (avec contrainte globale)
Temps                   : 590,0 ms
(La contrainte globale restreint l'espace : le compte de forcées peut augmenter.)

5. Solveur probabiliste — combiner règles, CSP et choix min-risk

Quand ni les règles ni le CSP ne forcent de cellule, on choisit la cellule à plus faible probabilité de mine. Le solveur probabiliste orchestre :

1. Appliquer les règles (gratuit, sûr).
2. Si bloqué, résoudre le CSP pour les cellules forcées.
3. Si toujours bloqué, calculer P(mine) de chaque cellule (frontière via CSP, hors-frontière via ratio mines-restantes / cellules-hors-frontière) et révéler la cellule la moins risquée.

public class ProbabilisticSolver
{
    public MinesweeperBoard Board;
    public Dictionary<string, int> Decisions = new() { ["rules"]=0, ["csp"]=0, ["guess"]=0 };
    public List<((int r,int c), double prob)> Guesses = new();

    public ProbabilisticSolver(MinesweeperBoard board) { Board = board; }

    ((int r,int c)? cell, double prob) ChooseBest(CSPSolver csp, List<Dictionary<(int r, int c),int>> sols) {
        var frontier = csp.Frontier();
        var probs = csp.Probabilities(sols);
        // Cellules hors frontiere : proba uniforme = mines restantes non attribuees / nb
        var allUnknown = new List<(int r, int c)>();
        for (int r = 0; r < Board.Rows; r++) for (int c = 0; c < Board.Cols; c++) {
            var p = (r, c);
            if (!Board.Revealed.Contains(p) && !Board.Flagged.Contains(p)) allUnknown.Add(p);
        }
        var nonFrontier = allUnknown.Where(p => !frontier.Contains(p)).ToList();
        if (nonFrontier.Count > 0) {
            double minesInFrontier = frontier.Sum(p => probs.GetValueOrDefault(p, 0.5));
            double rem = Math.Max(0, Board.RemainingMines - minesInFrontier);
            double nfProb = rem / nonFrontier.Count;
            foreach (var p in nonFrontier) probs[p] = nfProb;
        }
        if (probs.Count == 0) return (null, 1.0);
        var best = probs.Aggregate((a, b) => a.Value <= b.Value ? a : b);
        return (best.Key, best.Value);
    }

    public bool PlayGame(bool verbose = false) {
        while (!Board.GameOver && !Board.Won) {
            // 1. Regles
            var rs = new RuleBasedSolver(Board); rs.Solve();
            if (rs.MovesLog.Count > 0) { Decisions["rules"] += rs.MovesLog.Count; continue; }
            if (Board.GameOver || Board.Won) break;
            // 2. CSP
            var csp = new CSPSolver(Board);
            var (safe, mines) = csp.Solve(out var sols);
            if (safe.Count + mines.Count > 0) {
                foreach (var m in mines) Board.Flag(m.r, m.c);
                foreach (var s in safe) Board.Reveal(s.r, s.c);
                Decisions["csp"] += safe.Count + mines.Count;
                continue;
            }
            if (Board.GameOver || Board.Won) break;
            // 3. Choix probabiliste
            var (cell, prob) = ChooseBest(csp, sols);
            if (cell is null) break;
            if (verbose) Console.WriteLine($"  Devinette : {cell} (P(mine) = {prob:P1})");
            var cellPos = (cell.Value.Item1, cell.Value.Item2);
            Guesses.Add((cellPos, prob));
            Decisions["guess"]++;
            Board.Reveal(cellPos.Item1, cellPos.Item2);
        }
        return Board.Won;
    }
}

// Demonstration : une partie complete avec solveur probabiliste.
var boardProb = new MinesweeperBoard(8, 8, 10, safeCell: (4,4), new Random(2));
boardProb.Reveal(4, 4);
var pSolver = new ProbabilisticSolver(boardProb);
bool won = pSolver.PlayGame(verbose: false);
Console.WriteLine($"Partie probabiliste : gagne={won}");
Console.WriteLine($"Decisions : rules={pSolver.Decisions["rules"]}, csp={pSolver.Decisions["csp"]}, guess={pSolver.Decisions["guess"]}");
Console.WriteLine($"Devinettes faites : {pSolver.Guesses.Count}");

Partie probabiliste : gagne=True
Decisions : rules=31, csp=3, guess=1
Devinettes faites : 1

6. Stratégies pures pour le benchmark

Trois stratégies isolées pour mesurer chaque contribution :

• play_rule_only : règles + tirage aléatoire quand bloqué.
• play_csp_only : règles + CSP + tirage aléatoire quand bloqué.
• play_probabilistic : règles + CSP + choix min-risk quand bloqué.

// Strategie 1 : regles + aleatoire quand bloque.
(string, Dictionary<string,int>) PlayRuleOnly(MinesweeperBoard b, Random rng) {
    var dec = new Dictionary<string,int> { ["rules"]=0, ["random"]=0 };
    while (!b.GameOver && !b.Won) {
        var s = new RuleBasedSolver(b); s.Solve();
        if (s.MovesLog.Count > 0) { dec["rules"] += s.MovesLog.Count; continue; }
        if (b.GameOver || b.Won) break;
        var unknown = new List<(int r, int c)>();
        for (int r = 0; r < b.Rows; r++) for (int c = 0; c < b.Cols; c++) {
            var p = (r, c);
            if (!b.Revealed.Contains(p) && !b.Flagged.Contains(p)) unknown.Add(p);
        }
        if (unknown.Count == 0) break;
        var pick = unknown[rng.Next(unknown.Count)];
        b.Reveal(pick.r, pick.c); dec["random"]++;
    }
    return (b.Won ? "win" : "loss", dec);
}

// Strategie 2 : regles + CSP + aleatoire quand bloque.
(string, Dictionary<string,int>) PlayCspOnly(MinesweeperBoard b, Random rng) {
    var dec = new Dictionary<string,int> { ["rules"]=0, ["csp"]=0, ["random"]=0 };
    while (!b.GameOver && !b.Won) {
        var s = new RuleBasedSolver(b); s.Solve();
        if (s.MovesLog.Count > 0) { dec["rules"] += s.MovesLog.Count; continue; }
        if (b.GameOver || b.Won) break;
        var csp = new CSPSolver(b);
        var (safe, mines) = csp.Solve(out _);
        if (safe.Count + mines.Count > 0) {
            foreach (var m in mines) b.Flag(m.r, m.c);
            foreach (var sf in safe) b.Reveal(sf.r, sf.c);
            dec["csp"] += safe.Count + mines.Count; continue;
        }
        if (b.GameOver || b.Won) break;
        var unknown = new List<(int r, int c)>();
        for (int r = 0; r < b.Rows; r++) for (int c = 0; c < b.Cols; c++) {
            var p = (r, c);
            if (!b.Revealed.Contains(p) && !b.Flagged.Contains(p)) unknown.Add(p);
        }
        if (unknown.Count == 0) break;
        var pick = unknown[rng.Next(unknown.Count)];
        b.Reveal(pick.r, pick.c); dec["random"]++;
    }
    return (b.Won ? "win" : "loss", dec);
}

// Strategie 3 : regles + CSP + choix probabiliste.
(string, Dictionary<string,int>) PlayProbabilistic(MinesweeperBoard b, Random rng) {
    var dec = new Dictionary<string,int> { ["rules"]=0, ["csp"]=0, ["guess"]=0 };
    while (!b.GameOver && !b.Won) {
        var s = new RuleBasedSolver(b); s.Solve();
        if (s.MovesLog.Count > 0) { dec["rules"] += s.MovesLog.Count; continue; }
        if (b.GameOver || b.Won) break;
        var csp = new CSPSolver(b);
        var (safe, mines) = csp.Solve(out var sols);
        if (safe.Count + mines.Count > 0) {
            foreach (var m in mines) b.Flag(m.r, m.c);
            foreach (var sf in safe) b.Reveal(sf.r, sf.c);
            dec["csp"] += safe.Count + mines.Count; continue;
        }
        if (b.GameOver || b.Won) break;
        // Choix min-risk (fallback aleatoire si CSP vide)
        var probs = csp.Probabilities(sols);
        var frontier = csp.Frontier();
        (int r,int c) pick;
        if (probs.Count > 0) {
            // Etendre aux hors-frontiere
            var allUnknown = new List<(int r, int c)>();
            for (int r = 0; r < b.Rows; r++) for (int c = 0; c < b.Cols; c++) {
                var p = (r, c);
                if (!b.Revealed.Contains(p) && !b.Flagged.Contains(p)) allUnknown.Add(p);
            }
            var nonFrontier = allUnknown.Where(p => !frontier.Contains(p)).ToList();
            if (nonFrontier.Count > 0) {
                double minesInFrontier = frontier.Sum(p => probs.GetValueOrDefault(p, 0.5));
                double rem = Math.Max(0, b.RemainingMines - minesInFrontier);
                double nfProb = rem / nonFrontier.Count;
                foreach (var p in nonFrontier) probs[p] = nfProb;
            }
            pick = probs.Aggregate((a, x) => a.Value <= x.Value ? a : x).Key;
        } else {
            var unknown = new List<(int r, int c)>();
            for (int r = 0; r < b.Rows; r++) for (int c = 0; c < b.Cols; c++) {
                var p = (r, c);
                if (!b.Revealed.Contains(p) && !b.Flagged.Contains(p)) unknown.Add(p);
            }
            if (unknown.Count == 0) break;
            pick = unknown[rng.Next(unknown.Count)];
        }
        b.Reveal(pick.r, pick.c); dec["guess"]++;
    }
    return (b.Won ? "win" : "loss", dec);
}

Console.WriteLine("Trois strategies definies : PlayRuleOnly, PlayCspOnly, PlayProbabilistic.");

Trois strategies definies : PlayRuleOnly, PlayCspOnly, PlayProbabilistic.

7. Benchmark — comparer les trois approches

On joue N parties (graines reproductibles) avec chaque stratégie et on mesure le taux de victoire. Le twin Python utilise les mêmes graines (random.seed(1000+game_id) pour le plateau, random.seed(2000+game_id) pour le solveur).

// Benchmark sur N parties (meme graines que le twin Python).
int N_GAMES = 50;
int ROWS = 8, COLS = 8, NMINES = 10;

(string name, Func<MinesweeperBoard, Random, (string, Dictionary<string,int>)> play)[] approaches = {
    ("Regles + aleatoire",        (b, rng) => PlayRuleOnly(b, rng)),
    ("Regles + CSP + aleatoire",  (b, rng) => PlayCspOnly(b, rng)),
    ("Regles + CSP + probabilites", (b, rng) => PlayProbabilistic(b, rng)),
};

Console.WriteLine($"Benchmark : {N_GAMES} parties, plateau {ROWS}x{COLS}, {NMINES} mines\n");
foreach (var (name, play) in approaches) {
    int wins = 0;
    double totalMs = 0;
    var totalDec = new Dictionary<string,int>();
    for (int g = 0; g < N_GAMES; g++) {
        var boardRng = new Random(1000 + g);   // meme graine plateau que twin Python
        var b = new MinesweeperBoard(ROWS, COLS, NMINES, safeCell: (ROWS/2, COLS/2), boardRng);
        b.Reveal(ROWS/2, COLS/2);
        var solverRng = new Random(2000 + g);  // graine solveur
        var sw = System.Diagnostics.Stopwatch.StartNew();
        var (res, dec) = play(b, solverRng);
        sw.Stop();
        totalMs += sw.Elapsed.TotalMilliseconds;
        if (res == "win") wins++;
        foreach (var kv in dec) totalDec[kv.Key] = totalDec.GetValueOrDefault(kv.Key, 0) + kv.Value;
    }
    double winRate = (double)wins / N_GAMES * 100;
    double avgMs = totalMs / N_GAMES;
    Console.WriteLine($"{name}");
    Console.WriteLine($"  Victoires : {wins}/{N_GAMES} ({winRate:F0}%)");
    Console.WriteLine($"  Temps moyen : {avgMs:F1} ms/partie");
    Console.WriteLine($"  Decisions cumulees : {string.Join(", ", totalDec.Select(kv => $"{kv.Key}={kv.Value}"))}");
    Console.WriteLine();
}

Benchmark : 50 parties, plateau 8x8, 10 mines

Regles + aleatoire
  Victoires : 32/50 (64%)
  Temps moyen : 0,3 ms/partie
  Decisions cumulees : rules=1131, random=46

Regles + CSP + aleatoire
  Victoires : 36/50 (72%)
  Temps moyen : 0,5 ms/partie
  Decisions cumulees : rules=1113, csp=134, random=29

Regles + CSP + probabilites
  Victoires : 41/50 (82%)
  Temps moyen : 1,0 ms/partie
  Decisions cumulees : rules=1138, csp=147, guess=32

Exercice 1 : solveur global (contrainte du total de mines)

Le solveur CSP ci-dessus n’utilise que les contraintes locales (une par cellule révélée). Une amélioration : ajouter la contrainte globale « le nombre total de mines marquées dans la frontière ne dépasse pas remaining_mines ».

1. Ajoutez une contrainte globale dans Constraints(...) : la somme de toutes les variables de frontière doit être <= Board.RemainingMines.
2. Relancez le benchmark — le taux de victoire augmente-t-il ?
3. (Bonus) Forcez aussi une égalité quand toute mine restante est dans la frontière.

Indice : ajoutez (frontier.ToList(), Board.RemainingMines) comme contrainte ExactSum (pas juste <=) quand frontier.Count est petit et que les mines hors-frontière sont connues.

// EXERCICE 1 : contrainte globale sur le total de mines
// TODO etudiant : modifier CSPSolver.Constraints pour ajouter une contrainte
//   globale (somme de toutes les vars de frontiere <= Board.RemainingMines),
//   puis relancer le benchmark pour mesurer l'impact sur le taux de victoire.
Console.WriteLine("Exercice contrainte globale a completer (voir indice ci-dessus).");

Exercice contrainte globale a completer (voir indice ci-dessus).

Exercice 2 : Révéler une cellule garantie safe (probabilité 0 sur toutes les solutions CSP)

Le solveur probabiliste (section 5) choisit la cellule de risque minimal, mais peut encore deviner. L’énumération CSP exhaustive offre une garantie plus forte : si une cellule de frontière est safe dans 100 % des solutions valides (probabilité de mine = 0), on peut la révéler sans aucun risque. Cet exercice fait la différence entre minimiser le risque (heuristique) et l’éliminer totalement sur une cellule donnée (garantie logique).

// EXERCICE 2 : identifier une cellule garantie safe (proba de mine = 0 sur toutes les solutions CSP)
// TODO etudiant :
//   1. Pour un plateau donné, énumérer toutes les solutions valides du CSP via CSPSolver.
//   2. Pour chaque cellule de frontiere, calculer P(mine) = (#solutions où la cellule est une mine) / (#solutions total).
//   3. Révéler (Board.Reveal) toute cellule dont P(mine) == 0 — c'est une garantie safe, pas un guess.
// Indice : CSPSolver.Probabilities(solutions) calcule déjà ces probas ; il faut filtrer celles == 0
//          (pas juste prendre le argmin comme fait ChooseBest dans le solveur probabiliste).
//          Comparer le nombre de révélations garantie-safe vs le solveur min-risk sur le benchmark.
Console.WriteLine("Exercice 2 (cellule garantie safe) à compléter : filtrez les probas == 0 et révélez sans risque.");

Exercice 2 (cellule garantie safe) à compléter : filtrez les probas == 0 et révélez sans risque.

Exercice 3 : Décomposition de la frontière en composantes connectées

Sur un grand plateau, la frontière (cellules inconnues adjacentes à une cellule révélée) peut former plusieurs blocs indépendants séparés par des zones sûres. Énumérer le CSP sur toute la frontière d’un coup devient prohibitif (explosion combinatoire). La technique standard des solveurs de démineur performants consiste à décomposer la frontière en composantes connectées (deux cellules sont connectées si elles partagent une contrainte commune via un voisin révélé) et à résoudre chaque composante séparément — le produit des complexités est bien moindre que la complexité de l’ensemble.

// EXERCICE 3 : décomposer la frontière en composantes connectées et résoudre chaque bloc séparément
// TODO etudiant :
//   1. Construire le graphe d'adjacence de la frontière : deux cellules (r1,c1) et (r2,c2) sont
//      connectées si elles apparaissent ensemble dans au moins une contrainte (même cellule révélée voisine).
//   2. Calculer les composantes connectées (DFS ou Union-Find).
//   3. Pour chaque composante, énumérer ses solutions CSP locales et sommer pour les probabilités.
// Indice : CSPSolver.Constraints(frontier) retourne les contraintes ; deux vars sont connectées
//          si elles co-occurent dans une même contrainte. Mesurer le gain de temps sur un plateau
//          à frontière disjointe (ex. 2 îlots séparés) vs énumération globale naive.
Console.WriteLine("Exercice 3 (décomposition composantes connectées) à compléter : factorisez le CSP par bloc indépendant.");

Exercice 3 (décomposition composantes connectées) à compléter : factorisez le CSP par bloc indépendant.

Bilan

Ce notebook C# a présenté le Démineur comme CSP, jumeau C# du notebook Python :

1. Représentation du plateau avec génération sûre (Fisher-Yates partiel) et révélation en cascade.
2. Solveur par règles (Rule 1 = tous inconnus mines, Rule 2 = tous inconnus sûrs).
3. Solveur CSP — énumération backtracking from-scratch avec élagage par contrainte (le twin Python délègue à python-constraint ; ici on voit la recherche 2^k).
4. Solveur probabiliste combinant règles → CSP → choix min-risk (frontière via fréquence des solutions, hors-frontière via ratio uniforme).
5. Benchmark isolant la contribution de chaque couche (règles / CSP / probabilités).

Parité : jumeau C# de App-6-Minesweeper.ipynb. Le twin Python utilise python-constraint (lib) + numpy + matplotlib ; le twin C# implémente le CSP backtracking from-scratch (BCL pure, 0 NuGet) et remplace matplotlib par une grille ASCII (Prong B : on enseigne l’algorithme, pas la lib). Marathon parité .NET ⇄ Python (#4956), EPIC #3801 (Prong B).

Exercices supplementaires

Exercice 2 : generation differee des mines (safe-click garanti)

Implémentez une variante LazyMinesweeperBoard qui ne place les mines qu’au premier clic, en excluant la cellule cliquée et ses voisins. Pourquoi cette approche est-elle standard dans les Démineurs modernes ? (Indice : un premier clic qui tue casse le jeu.)

Exercice 3 : benchmark 16x16 (difficulte intermediaire)

Relancez le benchmark avec un plateau 16x16, 40 mines (niveau Intermédiaire). Comment évolue l’écart de taux de victoire entre les trois stratégies ? Pourquoi le CSP devient-il plus déterminant sur les grands plateaux ?

References

• Kaye, R. Minesweeper is NP-complete (Mathematical Intelligencer, 2000).
• Twin Python : App-6-Minesweeper.ipynb.
• Marathon parité : #4956.