Twin C# de
App-20-SudokuBenchmark-Python(Python stdlib :time,random,copy). Marathon .NET / Python (#4956), volet Search / Applications / CSP.
Navigation : << App-20 Python | Index | App-7 Wordle >>
A la fin de ce notebook, vous saurez :
Le code est entierement reecrit en C# (.NET 9, 0 NuGet), en miroir de la version Python qui n’utilisait que la stdlib. Le critere de parite = le nombre d’appels recursifs (déterministe, indépendant du runtime) : pour un même solveur et une même grille, le compte Python et C# doit concorder exactement. Le temps, lui, varie avec le runtime (C# typiquement plus rapide) et n’est pas un critere de parite.
Setup OK. Seed=42, TIMEOUT=60sTrois grilles 9x9 representative des niveaux de difficulte (0 = case vide). Elles sont strictement identiques au notebook Python, condition necessaire a la parite du nombre d’appels.
static readonly int[,] EASY_GRID = {
{5,3,0, 0,7,0, 0,0,0},
{6,0,0, 1,9,5, 0,0,0},
{0,9,8, 0,0,0, 0,6,0},
{8,0,0, 0,6,0, 0,0,3},
{4,0,0, 8,0,3, 0,0,1},
{7,0,0, 0,2,0, 0,0,6},
{0,6,0, 0,0,0, 2,8,0},
{0,0,0, 4,1,9, 0,0,5},
{0,0,0, 0,8,0, 0,7,9},
};
static readonly int[,] MEDIUM_GRID = {
{0,0,0, 2,6,0, 7,0,1},
{6,8,0, 0,7,0, 0,9,0},
{1,9,0, 0,0,4, 5,0,0},
{8,2,0, 1,0,0, 0,4,0},
{0,0,4, 6,0,2, 9,0,0},
{0,5,0, 0,0,3, 0,2,8},
{0,0,9, 3,0,0, 0,7,4},
{0,4,0, 0,5,0, 0,3,6},
{7,0,3, 0,1,8, 0,0,0},
};
static readonly int[,] HARD_GRID = {
{0,0,0, 6,0,0, 4,0,0},
{7,0,0, 0,0,3, 6,0,0},
{0,0,0, 0,9,1, 0,8,0},
{0,0,0, 0,0,0, 0,0,0},
{0,5,0, 1,8,0, 0,0,3},
{0,0,0, 3,0,6, 0,4,5},
{0,4,0, 2,0,0, 0,6,0},
{9,0,3, 0,0,0, 0,0,0},
{0,2,0, 0,0,0, 1,0,0},
};
static readonly Dictionary<string,int[,]> GRIDS = new()
{
{"Easy", EASY_GRID}, {"Medium", MEDIUM_GRID}, {"Hard", HARD_GRID}
};
// Copie profonde d'une grille (les solveurs muent la grille en place).
static int[,] CopyGrid(int[,] src)
{
var dst = new int[9,9];
for (int r=0;r<9;r++) for (int c=0;c<9;c++) dst[r,c]=src[r,c];
return dst;
}
foreach (var (name, grid) in GRIDS)
{
int givens = 0;
for (int r=0;r<9;r++) for (int c=0;c<9;c++) if (grid[r,c]!=0) givens++;
Console.WriteLine($"{name,-6} : {givens,2} indices donnes, {81-givens,2} cases vides");
}Easy : 30 indices donnes, 51 cases vides
Medium : 36 indices donnes, 45 cases vides
Hard : 23 indices donnes, 58 cases videsLe solveur le plus simple : trouver la première case vide (ordre ligne-par-ligne, colonne-par-colonne), essayer les valeurs 1..9 dans l’ordre, verifier la validite (ligne + colonne + carre 3x3), et recurser. Aucune heuristique : l’arbre de recherche explose rapidement sur les grilles difficiles.
// --- Solveur 1 : backtracking naif ---
static (int r, int c)? FindEmptyNaive(int[,] g)
{
for (int r=0;r<9;r++) for (int c=0;c<9;c++)
if (g[r,c]==0) return (r,c);
return null;
}
static bool IsValidNaive(int[,] g, int row, int col, int val)
{
for (int i=0;i<9;i++) { if (g[row,i]==val) return false; if (g[i,col]==val) return false; }
int br=3*(row/3), bc=3*(col/3);
for (int r=br;r<br+3;r++) for (int c=bc;c<bc+3;c++) if (g[r,c]==val) return false;
return true;
}
static bool SolveBacktracking(int[,] g, ref int calls)
{
calls++;
var empty = FindEmptyNaive(g);
if (empty is null) return true;
int row=empty.Value.r, col=empty.Value.c;
for (int val=1; val<=9; val++)
{
if (IsValidNaive(g, row, col, val))
{
g[row,col]=val;
if (SolveBacktracking(g, ref calls)) return true;
g[row,col]=0;
}
}
return false;
}
static (bool ok, double ms, int calls) RunBacktracking(int[,] grid)
{
var g = CopyGrid(grid);
int calls=0;
var sw = Stopwatch.StartNew();
bool success = SolveBacktracking(g, ref calls);
sw.Stop();
return (success, sw.Elapsed.TotalMilliseconds, calls);
}
var (ok1, ms1, calls1) = RunBacktracking(EASY_GRID);
Console.WriteLine($"Backtracking simple -- Easy : succes={ok1}, temps={ms1:F2} ms, appels={calls1}");Backtracking simple -- Easy : succes=True, temps=1,69 ms, appels=4209Le même backtracking, mais on choisit a chaque pas la case vide avec le moins de valeurs possibles. L’heuristique MRV reduit drastiquement le facteur de branchement : une case avec une seule valeur possible est remplie immediatement (propagation implicite), et les branches mortes sont coupees plus tot.
// --- Solveur 2 : backtracking + MRV ---
static (int r, int c, List<int> possibles)? FindEmptyMRV(int[,] g)
{
(int r, int c, List<int> possibles)? best = null;
for (int r=0;r<9;r++) for (int c=0;c<9;c++)
{
if (g[r,c]!=0) continue;
var used = new HashSet<int>();
for (int i=0;i<9;i++) { used.Add(g[r,i]); used.Add(g[i,c]); }
int br=3*(r/3), bc=3*(c/3);
for (int i=br;i<br+3;i++) for (int j=bc;j<bc+3;j++) used.Add(g[i,j]);
var poss = new List<int>();
for (int v=1;v<=9;v++) if (!used.Contains(v)) poss.Add(v);
if (best is null || poss.Count < best.Value.possibles.Count)
{
best = (r, c, poss);
if (poss.Count==0) return best; // fail-fast : case vide sans possibilite
}
}
return best;
}
static bool SolveBacktrackingMRV(int[,] g, ref int calls)
{
calls++;
var cell = FindEmptyMRV(g);
if (cell is null) return true;
int row=cell.Value.r, col=cell.Value.c;
foreach (var val in cell.Value.possibles)
{
g[row,col]=val;
if (SolveBacktrackingMRV(g, ref calls)) return true;
g[row,col]=0;
}
return false;
}
static (bool ok, double ms, int calls) RunBacktrackingMRV(int[,] grid)
{
var g = CopyGrid(grid);
int calls=0;
var sw = Stopwatch.StartNew();
bool success = SolveBacktrackingMRV(g, ref calls);
sw.Stop();
return (success, sw.Elapsed.TotalMilliseconds, calls);
}
var (ok2, ms2, calls2) = RunBacktrackingMRV(EASY_GRID);
Console.WriteLine($"Backtracking+MRV -- Easy : succes={ok2}, temps={ms2:F2} ms, appels={calls2}");Backtracking+MRV -- Easy : succes=True, temps=1,22 ms, appels=52On ajoute une propagation de contraintes avant la recherche : l’algorithme AC-3 (Arc Consistency 3) elimine des domaines des variables les valeurs sans support dans les domaines de leurs voisins. Pour le Sudoku, deux cases liees (même ligne/colonne/carre) sont des variables dont les valeurs doivent etre différentes. Après propagation, le backtracking (avec MRV) travaille sur des domaines déjà reduits.
Si la propagation vide un domaine, le problème est inconsistent (infeasible) et on arrete.
// --- Solveur 3 : AC-3 + backtracking ---
static List<(int r,int c)> Neighbors(int r, int c)
{
var out_ = new List<(int,int)>();
for (int i=0;i<9;i++)
{
if (i!=c) out_.Add((r,i));
if (i!=r) out_.Add((i,c));
}
int br=3*(r/3), bc=3*(c/3);
for (int i=br;i<br+3;i++) for (int j=bc;j<bc+3;j++)
if ((i,j)!=(r,c)) out_.Add((i,j));
return out_;
}
// Elimine de xi les valeurs sans support dans xj. Retourne true si modification.
static bool Revise(HashSet<int>[] domains, int xi, int xj, List<(int,int)> cells9)
{
bool revised=false;
var toRemove = new List<int>();
foreach (var x in domains[xi])
{
// x a un support ssi il existe y dans domains[xj] avec y != x
bool support=false;
foreach (var y in domains[xj]) { if (y!=x) { support=true; break; } }
if (!support) toRemove.Add(x);
}
foreach (var x in toRemove) { domains[xi].Remove(x); revised=true; }
return revised;
}
// AC-3 standard. Retourne false si un domaine devient vide (inconsistent).
static bool AC3(HashSet<int>[] domains, List<(int r,int c)> cells9)
{
var queue = new Queue<(int xi,int xj)>();
// voisinages precalcules par index de cellule
var neighOf = new List<int>[81];
for (int i=0;i<81;i++) { neighOf[i] = new List<int>(); var (r,c)=cells9[i]; foreach (var (nr,nc) in Neighbors(r,c)) neighOf[i].Add(nr*9+nc); }
foreach (int xi in Enumerable.Range(0,81)) foreach (var xj in neighOf[xi]) queue.Enqueue((xi,xj));
while (queue.Count>0)
{
var (xi,xj) = queue.Dequeue();
if (Revise(domains, xi, xj, cells9))
{
if (domains[xi].Count==0) return false;
foreach (var xk in neighOf[xi]) if (xk!=xj) queue.Enqueue((xk,xi));
}
}
return true;
}
static (bool ok, double ms, int calls) RunAC3(int[,] grid)
{
var cells9 = new List<(int,int)>();
for (int r=0;r<9;r++) for (int c=0;c<9;c++) cells9.Add((r,c));
var domains = new HashSet<int>[81];
for (int r=0;r<9;r++) for (int c=0;c<9;c++)
{
int idx=r*9+c;
domains[idx] = grid[r,c]!=0 ? new HashSet<int>{grid[r,c]} : new HashSet<int>{1,2,3,4,5,6,7,8,9};
}
int calls=0;
var sw = Stopwatch.StartNew();
if (!AC3(domains, cells9)) { sw.Stop(); return (false, sw.Elapsed.TotalMilliseconds, calls); }
// Backtracking avec MRV sur les domaines reduits
var assign = new int?[81];
bool Backtrack()
{
calls++;
int? pick=null; int bestSize=int.MaxValue;
for (int i=0;i<81;i++)
{
if (assign[i].HasValue) continue;
if (domains[i].Count<bestSize) { bestSize=domains[i].Count; pick=i; if (bestSize==0) return false; }
}
if (pick is null) return true; // toutes assignees
int v = pick.Value; var (vr,vc)=cells9[v];
foreach (var val in domains[v].OrderBy(x=>x))
{
bool ok=true;
foreach (var (nr,nc) in Neighbors(vr,vc)) { if (assign[nr*9+nc]==val) { ok=false; break; } }
if (!ok) continue;
assign[v]=val;
if (Backtrack()) return true;
assign[v]=null;
}
return false;
}
bool success = Backtrack();
sw.Stop();
return (success, sw.Elapsed.TotalMilliseconds, calls);
}
var (ok3, ms3, calls3) = RunAC3(EASY_GRID);
Console.WriteLine($"AC-3 -- Easy : succes={ok3}, temps={ms3:F2} ms, appels={calls3}");AC-3 -- Easy : succes=True, temps=3,42 ms, appels=82La formulation la plus elegante : Sudoku comme couverture exacte (exact cover). On encode le problème en 324 contraintes (colonnes) :
Chaque candidat (r,c,v) couvre exactement 4 colonnes. L’algorithme X de Knuth, implemente avec les Dancing Links (listes doublement chainees toroidales), resout le problème en O(c) par nœud visite. C’est asymptotiquement le plus rapide pour la couverture exacte.
// --- Solveur 4 : Dancing Links (Algorithm X, Knuth 2000) ---
class DLXNode
{
public int Row=-1, Col=-1, Size=0;
public DLXNode Up, Down, Left, Right;
}
class DLXSolver
{
private DLXNode head;
private List<DLXNode> cols;
private int[,] solution;
public bool Solve(int[,] grid)
{
const int N = 324;
head = new DLXNode();
var h = head; h.Left=h; h.Right=h; h.Up=h; h.Down=h;
cols = new List<DLXNode>(N);
// creation des colonnes
DLXNode prev = head;
for (int i=0;i<N;i++)
{
var col = new DLXNode{Col=i, Size=0};
col.Up=col; col.Down=col; col.Left=prev; prev.Right=col; prev=col;
cols.Add(col);
}
prev.Right=head; head.Left=prev;
// creation des lignes candidates (r,c,v)
for (int r=0;r<9;r++) for (int c=0;c<9;c++)
{
int v = grid[r,c];
var candidates = v!=0 ? new[]{v} : Enumerable.Range(1,9);
foreach (var vv in candidates) AddRow(r,c,vv);
}
solution = new int[9,9];
return Search(0);
}
private void AddRow(int r, int c, int v)
{
int c0 = r*9+c; // case (r,c) remplie
int c1 = 81 + r*9 + (v-1); // ligne r contient v
int c2 = 162 + c*9 + (v-1);// colonne c contient v
int b = 3*(r/3)+(c/3);
int c3 = 243 + b*9 + (v-1);// carre b contient v
int[] colIdx = {c0,c1,c2,c3};
DLXNode rowPrev=null, first=null;
foreach (var ci in colIdx)
{
var col = cols[ci];
var node = new DLXNode{Row=r*100+c*10+v, Col=ci};
// insert en bas de la colonne
node.Down=col; node.Up=col.Up; col.Up.Down=node; col.Up=node;
col.Size++;
// chaine horizontale de la ligne
if (first is null) { first=node; node.Left=node; node.Right=node; rowPrev=node; }
else { node.Left=rowPrev; rowPrev.Right=node; node.Right=first; first.Left=node; rowPrev=node; }
}
}
private void Cover(DLXNode col) { col.Right.Left=col.Left; col.Left.Right=col.Right; for (var i=col.Down;i!=col;i=i.Down) for (var j=i.Right;j!=i;j=j.Right) { j.Down.Up=j.Up; j.Up.Down=j.Down; cols[j.Col].Size--; } }
private void Uncover(DLXNode col) { for (var i=col.Up;i!=col;i=i.Up) for (var j=i.Left;j!=i;j=j.Left) { cols[j.Col].Size++; j.Down.Up=j; j.Up.Down=j; } col.Right.Left=col; col.Left.Right=col; }
private bool Search(int depth)
{
if (head.Right==head) return true; // toutes les colonnes couvertes = solution
// choisir la colonne de plus petite taille (heuristique S)
DLXNode col=head.Right; int best=col.Size;
for (var c=head.Right;c!=head;c=c.Right) if (c.Size<best) { best=c.Size; col=c; }
Cover(col);
for (var r=col.Down;r!=col;r=r.Down)
{
for (var j=r.Right;j!=r;j=j.Right) Cover(cols[j.Col]);
// decoder (r,c,v) depuis le Row tag
int tag=r.Row; int rr=tag/100, cc=(tag/10)%10, vv=tag%10;
solution[rr,cc]=vv;
if (Search(depth+1)) return true;
for (var j=r.Left;j!=r;j=j.Left) Uncover(cols[j.Col]);
}
Uncover(col);
return false;
}
public int[,] GetSolution() => solution;
}
static (bool ok, double ms, int calls) RunDLX(int[,] grid)
{
var g = CopyGrid(grid);
var solver = new DLXSolver();
var sw = Stopwatch.StartNew();
bool success = solver.Solve(g);
sw.Stop();
return (success, sw.Elapsed.TotalMilliseconds, 0); // DLX n'expose pas calls directement (cf. exercice 2)
}
var (ok4, ms4, calls4) = RunDLX(EASY_GRID);
Console.WriteLine($"DLX (Knuth) -- Easy : succes={ok4}, temps={ms4:F2} ms");DLX (Knuth) -- Easy : succes=True, temps=0,95 msOn execute les quatre solveurs sur les trois grilles et on mesure : (a) le succes, (b) le nombre d’appels recursifs (déterministe, critere de parite), (c) le temps wall-clock (informatif, varie avec le runtime).
// Wrapper pour uniformiser la signature des 4 solveurs dans le benchmark.
static (bool ok, double ms, int calls) RunByName(string sname, int[,] grid) => sname switch
{
"Backtracking simple" => RunBacktracking(grid),
"Backtracking + MRV" => RunBacktrackingMRV(grid),
"AC-3 + backtracking" => RunAC3(grid),
"DLX (Knuth)" => RunDLX(grid),
_ => (false, 0, 0)
};
string[] SOLVER_NAMES = { "Backtracking simple", "Backtracking + MRV", "AC-3 + backtracking", "DLX (Knuth)" };
Console.WriteLine($"{"Diff",6} | {"Solveur",-22} | {"Succes",-7} | {"Temps(ms)",10} | {"Appels",10}");
Console.WriteLine(new string('-', 65));
foreach (var diffName in DIFFICULTIES)
{
var grid = GRIDS[diffName];
foreach (var sname in SOLVER_NAMES)
{
var sw = Stopwatch.StartNew();
var (ok, ms, calls) = RunByName(sname, grid);
sw.Stop();
bool timeout = sw.Elapsed.TotalSeconds > TIMEOUT_S;
bool succes = ok && !timeout;
Console.WriteLine($"{diffName,6} | {sname,-22} | {succes,-7} | {ms,10:F2} | {calls,10}{(timeout?" [TIMEOUT]":"")}");
}
} Diff | Solveur | Succes | Temps(ms) | Appels
-----------------------------------------------------------------
Easy | Backtracking simple | True | 1,35 | 4209
Easy | Backtracking + MRV | True | 0,73 | 52
Easy | AC-3 + backtracking | True | 1,33 | 82
Easy | DLX (Knuth) | True | 0,13 | 0
Medium | Backtracking simple | True | 0,02 | 55
Medium | Backtracking + MRV | True | 0,62 | 46
Medium | AC-3 + backtracking | True | 1,29 | 82
Medium | DLX (Knuth) | True | 0,13 | 0
Hard | Backtracking simple | True | 346,21 | 879418
Hard | Backtracking + MRV | True | 140,87 | 5565
Hard | AC-3 + backtracking | True | 1884,22 | 981113
Hard | DLX (Knuth) | True | 0,31 | 0Les faits marquants (a confronter a la sortie ci-dessus) :
Les trois solveurs déterministes (naif, MRV, AC-3) visitent exactement le meme nombre de nœuds en C# et en Python :
| Grille | Naif | MRV | AC-3 |
|---|---|---|---|
| Easy | 4209 | 52 | 82 |
| Medium | 55 | 46 | 82 |
| Hard | 879418 | 5565 | 981113 |
Ces comptes concordent au nombre pres entre les deux langages : c’est le critere de parite (algorithme déterministe).
Le temps wall-clock depend du runtime (JIT .NET vs CPython, charge systeme, version .NET, machine), et cet ecart a un effet visible sur le benchmark :
succes=False a l’issue du budget 60 s, qui est un parametre de benchmark deterministe) apres 981 113 appels. Ce twin C# termine sous le budget (runtime machine-dep) avec le meme nombre d’appels (981 113). La difference de succes apparente (False cote Python, True cote C#) n’est pas un bug : elle reflete l’avantage du JIT .NET sur CPython pour les boucles tight. Le critere de parite (nombre d’appels) est respecte ; le temps, lui, est runtime-dependant.Note methodologique – separation structurel / machine-dep : le nombre d’appels recursifs (table ci-dessus) est un invariant structurel (resultat solveur sur instance specifique, deterministe sur la grainee fixee SEED=42) – c’est le critere de parite entre les deux langages. En revanche, le temps wall-clock (runtime C# et Python), le timeout eventuel, et le ratio cross-runtime sont machine-dep (JIT .NET vs CPython, charge systeme, version .NET, taille de l’instance) et ne survivent pas a une re-execution sur une autre machine. L’ordre de grandeur qualitatif (C# naif/baseline rapide vs C# naif Hard lent, C# DLX tres rapide) reste structurel, mais le ratio exact est lui aussi machine-dep. Pour observer vos propres timings, executez la cellule de benchmark ci-dessus (la cellule
RunByNameutiliseStopwatchpour mesurer le wall-clock).
Le point pedagogique (l’explosion combinatoire du naif, le gain de MRV, la superieur asymptotique de DLX) est identique dans les deux langages ; seul le mur de temps (le budget parametrable de 60 s) est franchi ou non selon le runtime.
Les quatre solveurs ci-dessus sont des réimplémentations from-scratch : leur rôle est pédagogique. Cette tranche confronte le socle au moteur de production utilisé par l’industrie : CP-SAT, le solveur de programmation par contraintes de Google OR-Tools (Perron & Furnon). C’est le même moteur des deux côtés de la parité – le twin Python appelle ortools (pip) et ce jumeau C# appelle Google.OrTools (NuGet) : la parité passe de semantic à native-both (lib-vs-lib, EPIC #10382 / arbitrage #11200 Option A).
Modélisation miroir (identique au twin Python) :
c_r_c par case : domaine réduit au chiffre donné si la case est remplie, [1, 9] sinon ;AddAllDifferent : 9 lignes + 9 colonnes + 9 carrés 3x3.Invariants comparables (paramètres fixés pour le déterminisme) :
| Invariant | Statut |
|---|---|
Statut de résolution (OPTIMAL, …) |
déterministe |
| Grille valide (indices préservés + règles du Sudoku) | déterministe |
branches / conflicts |
déterministes (mono-worker, graine fixée) |
| Propagations binaires / entières | déterministes |
| Temps wall-clock | informatif, machine-dep |
Deux configurations sont mesurées : presolve=on (défaut industriel) et presolve=off (recherche SAT exposée). Paramètres : num_search_workers:1 (mono-thread – condition du déterminisme), random_seed:42 (miroir du SEED du socle), max_time_in_seconds:60 (miroir du TIMEOUT_S). La version NuGet est épinglée à 9.15.6755 – exactement la version ortools du twin Python, pour garantir la comparaison des compteurs d’invariants entre les deux moteurs.
#r "nuget: Google.OrTools, 9.15.6755"
using Google.OrTools.Sat;
// --- Tranche 2 : moteur de production CP-SAT (Google OR-Tools) ---
// Version epinglee 9.15.6755 = exactement la version 'ortools' du twin Python :
// meme moteur C++ des deux cotes, condition de comparabilite des invariants.
record CpsatResult(string Statut, bool Succes, bool Valide, long Branches, long Conflicts,
long PropBinaires, long PropEntieres, double TempsMs, int[,] Solution);
// Construit le modele miroir du twin Python : 81 variables + 27 AddAllDifferent.
static (CpModel model, Google.OrTools.Sat.IntVar[,] cells) BuildCpsatModel(int[,] grid)
{
var model = new CpModel();
var cells = new Google.OrTools.Sat.IntVar[9, 9];
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
cells[r, c] = model.NewIntVar(grid[r, c] == 0 ? 1 : grid[r, c],
grid[r, c] == 0 ? 9 : grid[r, c], $"c_{r}_{c}");
for (int i = 0; i < 9; i++)
{
var rowVars = new Google.OrTools.Sat.IntVar[9];
var colVars = new Google.OrTools.Sat.IntVar[9];
for (int j = 0; j < 9; j++) { rowVars[j] = cells[i, j]; colVars[j] = cells[j, i]; }
model.AddAllDifferent(rowVars);
model.AddAllDifferent(colVars);
}
for (int br = 0; br < 9; br += 3)
for (int bc = 0; bc < 9; bc += 3)
{
var boxVars = new Google.OrTools.Sat.IntVar[9];
for (int r = 0; r < 3; r++) for (int c = 0; c < 3; c++) boxVars[r * 3 + c] = cells[br + r, bc + c];
model.AddAllDifferent(boxVars);
}
return (model, cells);
}
// Valide une solution : indices donnes preserves + lignes/colonnes/carres = {1..9}.
static bool CheckSudokuSolution(int[,] grid, int[,] solution)
{
if (solution is null) return false;
for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++)
if (grid[r, c] != 0 && solution[r, c] != grid[r, c]) return false;
var full = Enumerable.Range(1, 9).ToArray();
for (int i = 0; i < 9; i++)
{
var row = Enumerable.Range(0, 9).Select(c => solution[i, c]).OrderBy(x => x);
var col = Enumerable.Range(0, 9).Select(r => solution[r, i]).OrderBy(x => x);
if (!row.SequenceEqual(full) || !col.SequenceEqual(full)) return false;
}
for (int br = 0; br < 9; br += 3) for (int bc = 0; bc < 9; bc += 3)
{
var box = Enumerable.Range(0, 3).SelectMany(r => Enumerable.Range(0, 3)
.Select(c => solution[br + r, bc + c])).OrderBy(x => x);
if (!box.SequenceEqual(full)) return false;
}
return true;
}
// Resout avec CP-SAT. workers=1 + seed=42 => invariants deterministes (miroir du twin Python).
static CpsatResult RunCpsat(int[,] grid, bool usePresolve = true)
{
var (model, cells) = BuildCpsatModel(grid);
var solver = new CpSolver();
solver.StringParameters = $"num_search_workers:1,random_seed:42,max_time_in_seconds:60.0,cp_model_presolve:{(usePresolve ? "true" : "false")}";
var sw = Stopwatch.StartNew();
var status = solver.Solve(model);
sw.Stop();
bool ok = status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible;
int[,] solved = null;
if (ok)
{
solved = new int[9, 9];
for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) solved[r, c] = (int)solver.Value(cells[r, c]);
}
var resp = solver.Response;
return new CpsatResult(status.ToString(), ok, CheckSudokuSolution(grid, solved),
solver.NumBranches(), solver.NumConflicts(),
resp.NumBinaryPropagations, resp.NumIntegerPropagations,
sw.Elapsed.TotalMilliseconds, solved);
}
Console.WriteLine("Google.OrTools 9.15.6755 charge (meme version de moteur que le twin Python).");
var demo = RunCpsat(EASY_GRID);
Console.WriteLine($"CP-SAT -- Easy (presolve on) : statut={demo.Statut}, branches={demo.Branches}, conflicts={demo.Conflicts}, temps={demo.TempsMs:F1} ms, solution valide={demo.Valide}");Google.OrTools 9.15.6755 charge (meme version de moteur que le twin Python).
CP-SAT -- Easy (presolve on) : statut=Optimal, branches=0, conflicts=0, temps=2039,9 ms, solution valide=TrueAvec le moteur défini, déroulons le même protocole que le socle : les trois grilles (Easy / Medium / Hard) dans deux configurations (presolve=on puis presolve=off). Pour chaque combinaison : statut, validité de la grille produite, branches, conflicts, propagations – et le temps, informatif.
// Benchmark CP-SAT : 3 grilles x 2 configurations (presolve on/off), invariants deterministes.
Console.WriteLine($"{"Grille",7} | {"Config",-12} | {"Statut",-8} | {"Valide",6} | {"Branches",9} | {"Conflicts",9} | {"Prop.bin",9} | {"Prop.int",9} | {"Temps(ms)",9}");
Console.WriteLine(new string('-', 95));
foreach (var diffName in DIFFICULTIES)
{
var grid = GRIDS[diffName];
foreach (var (configName, usePresolve) in new[] { ("presolve=on", true), ("presolve=off", false) })
{
var res = RunCpsat(grid, usePresolve);
Console.WriteLine($"{diffName,7} | {configName,-12} | {res.Statut,-8} | {res.Valide,6} | {res.Branches,9} | {res.Conflicts,9} | {res.PropBinaires,9} | {res.PropEntieres,9} | {res.TempsMs,9:F1}");
}
} Grille | Config | Statut | Valide | Branches | Conflicts | Prop.bin | Prop.int | Temps(ms)
-----------------------------------------------------------------------------------------------
Easy | presolve=on | Optimal | True | 0 | 0 | 0 | 0 | 2,5
Easy | presolve=off | Optimal | True | 0 | 0 | 340 | 111 | 12,9
Medium | presolve=on | Optimal | True | 0 | 0 | 0 | 0 | 1,2
Medium | presolve=off | Optimal | True | 0 | 0 | 251 | 49 | 2,5
Hard | presolve=on | Optimal | True | 0 | 0 | 0 | 0 | 10,7
Hard | presolve=off | Optimal | True | 5 | 2 | 790 | 213 | 6,1| Config | Branches | Conflicts | Lecture |
|---|---|---|---|
presolve=on |
0 sur les trois grilles | 0 | la grille est résolue entièrement dans le présolve – propagation pure, aucun arbre de recherche |
presolve=off |
0 (Easy, Medium), quelques unités (Hard) | quelques unités sur Hard seulement | sans le présolve, la recherche SAT n’intervient quasiment pas : la propagation des 27 contraintes AllDifferent suffit déjà |
AddAllDifferent embarque un filtrage par algorithme de flot (matching), bien plus fort que l’AC-3 du socle.num_search_workers:1 + random_seed:42 + version épinglée 9.15.6755 => les compteurs de cette table sont reproductibles à l’identique et doivent concorder avec le twin Python (même moteur C++ sous-jacent des deux côtés). C’est la parité native-both : lib contre lib.Note technique : les temps (colonne
Temps(ms)) restent informatifs et machine-dep – JIT .NET, charge système. Seuls les compteurs d’invariants (statut, validité, branches, conflicts, propagations) sont déterministes et reproductibles.
Avant le backtracking, on peut propager les singletons : toute case vide dont une seule valeur est possible doit etre remplie immediatement, et cela peut créer de nouveaux singletons (propagation en chaîne). Implementez UnitPropagation(grid) qui remplit iterativement ces cases et retourne le nombre de remplissages effectues. Comparez ensuite le nombre d’appels de RunBacktracking avant et après propagation unitaire sur la grille Hard.
// Exercice 1 : propagation unitaire. Retourne le nombre de cases remplies, ou -1 si contradiction.
static int UnitPropagation(int[,] grid)
{
// TODO etudiant : boucler tant qu'on trouve une case vide avec exactement 1 valeur possible.
// Indice : reutiliser la logique de calcul des valeurs possibles de FindEmptyMRV.
// Etape 1 : pour chaque case vide, calculer les valeurs possibles.
// Etape 2 : si une case a exactement 1 valeur possible, la remplir et recommencer.
// Etape 3 : si une case a 0 valeur possible, retourner -1 (contradiction).
Console.WriteLine("Exercice a completer -- UnitPropagation");
return 0;
}
Console.WriteLine("Exercice 1 : methode UnitPropagation definie (stub). A implementer.");Exercice 1 : methode UnitPropagation definie (stub). A implementer.Le solveur DLX ci-dessus retourne calls=0 (il n’instrumente pas le nombre de nœuds visitees). Ajoutez un compteur dans DLXSolver.Search (incrementer a chaque entree de Search) et retournz-le via RunDLX. Comparez ce compte aux calls du backtracking naif et de MRV sur la grille Hard : l’ecart quantifie l’avantage de la formulation exact-cover.
// Exercice 2 : instrumenter DLXSolver.Search avec un compteur de nœuds.
// Indice : ajouter un champ 'public int NodesVisited;' dans DLXSolver, l'incrementer en tete de Search.
// Etape 1 : modifier la signature de Search pour accepter/incrementer le compteur.
// Etape 2 : exposer le compteur via une propriete publique.
// Etape 3 : RunDLX retourne (ok, ms, nodesVisited) au lieu de (ok, ms, 0).
Console.WriteLine("Exercice a completer -- instrumentation DLX (voir commentaire ci-dessus).");Exercice a completer -- instrumentation DLX (voir commentaire ci-dessus).Ecrivez un générateur qui produit une grille de difficulte parametree : (1) resoudre une grille vide avec un solveur pour obtenir une solution complete, (2) retirer k cases au hasard tout en verifier (par re-solution) que la grille reste a solution unique. Le paramètre k contrôle la difficulte. Indice : utiliser RunBacktracking comme oracle d’unicite.
// Exercice 3 : generation de grille a difficulte controlee.
static int[,] GeneratePuzzle(int k, int seed)
{
// TODO etudiant : (1) generer une solution complete, (2) retirer k cases, (3) verifier unicite.
// Indice : pour l'unicite, resoudre 2 fois avec ordre de parcours different et comparer.
// Etape 1 : remplir une grille vide par backtracking avec tirage aleatoire des valeurs.
// Etape 2 : retirer k cases (en sauvegardant leurs positions).
// Etape 3 : verifier que la grille reduite a une solution unique.
Console.WriteLine("Exercice a completer -- GeneratePuzzle");
return new int[9,9];
}
Console.WriteLine("Exercice 3 : methode GeneratePuzzle definie (stub). A implementer.");Exercice 3 : methode GeneratePuzzle definie (stub). A implementer.Ce twin C# a reconstruit depuis zero les quatre solveurs Sudoku du notebook Python :
Google.OrTools 9.15.6755 en C# et ortools 9.15.6755 en Python.La Tranche 2 (section 4) confronte le socle from-scratch au moteur de production et confirme expérimentalement la thèse du socle – avec le présolve activé, CP-SAT résout les trois grilles en zéro branche, même sur la grille Hard : tout le travail est fait par la propagation (filtrage par flot des 27 contraintes AllDifferent), pas par la recherche. C’est l’aboutissement de la progression naif -> MRV -> AC-3 -> DLX : chaque étage délègue davantage au raisonnement sur les domaines et moins à l’exploration aveugle.
Google.OrTools vs pip ortools, même version 9.15.6755, num_search_workers:1, random_seed:42) – les invariants (statut, validité, branches, conflicts, propagations) concordent exactement entre les deux jumeaux ;Note methodologique – separation structurel / machine-dep : tous les nombres d’appels et les grilles (Easy/Medium/Hard) sont des invariants structurels (resultats solveur sur instance specifique, deterministes sur la grainee SEED=42). En revanche, tous les temps wall-clock et les ratios cross-runtime cites dans cette conclusion sont machine-dep (JIT .NET vs CPython, charge systeme, version .NET) et ne survivent pas a une re-execution sur une autre machine. Le critere de parite reste le nombre d’appels (deterministe), pas le temps (runtime-dependent). Les compteurs CP-SAT de la Tranche 2 (branches, conflicts, propagations) sont deterministes eux aussi – mono-worker, graine fixée – et constituent le critere de parité native-both.
<< App-20 Python | Index | App-7 Wordle >>
Marathon #4956 – parite .NET / Python, volet Search / Applications / CSP. Tranche 2 native-both EPIC #10382.