Navigation : Index | << Sudoku-07 C# | Sudoku-08 Python >>

Résolution de Sudoku par Stratégies Humaines

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Comprendre comment les experts humains résolvent les Sudoku, par opposition aux algorithmes de force brute 2. Implémenter les techniques de base : Naked Singles et Hidden Singles 3. Implémenter les techniques intermédiaires : Naked Pairs, Locked Candidates 4. Implémenter la technique avancée X-Wing 5. Combiner ces techniques dans un solveur hybride avec fallback vers le backtracking 6. Analyser quelles techniques sont necessaires selon la difficulté du puzzle

Prérequis

  • Sudoku-0-Environment : classes SudokuGrid, ISudokuSolver, SudokuHelper
  • Familiarite avec les règles du Sudoku (lignes, colonnes, blocs 3x3)

Durée estimee : 60 minutes

Importation de l’environnement

Nous importons les classes de base définies dans le notebook Sudoku-0-Environment : SudokuGrid, ISudokuSolver, SudokuHelper.

#!import Sudoku-00-Environment-CSharp.ipynb

Sudoku-00 : Environnement et Classes de Base (C#)

Navigation : Index | Sudoku-01 Backtracking C# >>

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Comprendre la structure de données SudokuGrid et ses méthodes principales 2. Utiliser ISudokuSolver pour implémenter un solveur de Sudoku 3. Exploiter SudokuHelper pour charger des grilles et tester des solveurs 4. Comparer les performances de plusieurs solveurs sur différentes difficultés

Prérequis : Notions de base en C# (.NET Interactive)
Durée estimée : ~15 min

Installing Packages
  • Plotly.NET

Définition de la classe SudokuGrid

Nous définissons ici la classe SudokuGrid qui représente une grille de Sudoku et fournit des méthodes pour manipuler et afficher les grilles.

SudokuGrid defini.

Interprétation : Structure de données pour la grille Sudoku

Sortie obtenue : La classe SudokuGrid encapsule toutes les opérations de manipulation, validation et affichage d’une grille de Sudoku 9x9.

Aspect Valeur Signification
Cells[9,9] int[,] Stockage interne des valeurs (0 = vide)
AllNeighbours 27 x 9 positions Pré-calcul des voisins ligne/colonne/bloc
CellNeighbours[9][9] ~20 positions chacune Voisins directs de chaque cellule
GetAvailableNumbers() int[] Candidats valides pour une cellule
NbErrors() int Nombre de conflits + modifications erronées

Points clés : 1. Pré-calcul des voisins : AllNeighbours et CellNeighbours sont calculés une seule fois à l’initialisation, évitant les recalculs coûteux 2. Conversion flexible : Méthodes pour convertir entre tableaux 1D, 2D et jagged arrays (utile pour différents formats de fichiers) 3. Validation robuste : NbErrors compte à la fois les doublons (ligne/colonne/bloc) et les modifications de indices pré-remplis 4. Parsing tolerant : ReadMultiSudoku accepte plusieurs formats (., X, -, espaces)

Note technique : La structure CellNeighbours[i][j] contient environ 20 positions (8 ligne + 8 colonne + 4 bloc, moins les doublons). Ce pré-calcul est crucial pour les performances des algorithmes de backtracking et de propagation de contraintes.

Définition de l’interface ISudokuSolver

Nous définissons ici l’interface ISudokuSolver qui sera implémentée par les différentes stratégies de résolution de Sudoku.

ISudokuSolver defini.

Interprétation : Interface de stratégie

Sortie obtenue : L’interface ISudokuSolver définit le contrat que tous les solveurs doivent respecter.

Aspect Valeur Signification
Solve(SudokuGrid) SudokuGrid Méthode unique de résolution
Pattern Stratégie Permuter les algorithmes sans modifier le code client

Points clés : 1. Simplicité : Une seule méthode Solve prenant une grille et retournant une grille résolue 2. Flexibilité : N’importe quel algorithme (backtracking, CSP, métaheuristique) peut implémenter cette interface 3. Composabilité : Les solveurs peuvent être passés en paramètre, stockés dans des listes, testés unitairement 4. Extensibilité : Ajouter un nouveau solver ne nécessite que d’implémenter l’interface

Note technique : Ce design pattern permet à SudokuHelper.TestSolvers d’accepter une liste de (string, ISudokuSolver) pour comparer tous les algorithmes avec le même code de test.

Définition de la classe SudokuHelper

Nous ajoutons ici la classe SudokuHelper qui contient des méthodes utilitaires pour charger des grilles de Sudoku et tester des solvers.

  • GetSudokus : Renvoie des listes de Sudoku issues de fichiers de 3 difficultés différentes.
  • SolveSudoku : effectue un test simple d’un solver sur un sudoku donné.
  • TestSolvers : exécute les tests de performance sur plusieurs solveurs.
  • DisplayResults : affiche les résultats des tests sous forme de graphiques.
SudokuHelper defini.

Interprétation : Infrastructure de test et benchmark

Sortie obtenue : La classe SudokuHelper fournit une infrastructure complète pour tester et comparer les solveurs de Sudoku.

Aspect Valeur Signification
GetSudokus() 51/95/100 grilles Trois niveaux de difficulté (Easy/Medium/Hard)
TestSolvers() Performance multi-solveurs Exécution parallèle avec timeout
DisplayResults() Graphiques SVG inline (SvgChartHelper) Comparaison des temps par difficulté, sérialisée dans le notebook
SolveSudoku() Test unitaire Résolution individuelle avec affichage

Points clés : 1. Chargement intelligent : Recherche récursive du dossier Puzzles dans l’arborescence 2. Robustesse : Gestion des timeouts (3 000 ms par défaut — paramètre de configuration du solveur, valeur fixée dans le code) et exceptions 3. Mesures : Temps d’exécution total + nombre de grilles resolues 4. Disqualification : Un solver échouant sur une grille est disqualifié pour la difficulté

Note technique : La méthode TestSolvers utilise Interlocked.Increment pour un thread-safe incrément du compteur de solutions. Le CancellationToken permet d’interrompre proprement les solveurs trop lents.

Exercice : Validation d’une grille Sudoku

Énoncé

Implémentez une méthode IsValidSolution qui vérifie qu’une grille est une solution valide de Sudoku, c’est-à-dire que chaque ligne, chaque colonne et chaque bloc 3x3 contient exactement une fois chaque chiffre de 1 à 9.

Utilisez cette méthode pour valider les résultats de SudokuHelper.SolveSudoku.

Indices :

  • Parcourez les 9 lignes, 9 colonnes et 9 blocs
  • Pour chaque unité, verifiez que les 9 chiffres sont tous présents sans doublon
  • SudokuGrid.AllNeighbours contient déjà les indices des unités
Exercice a completer

Résumé et perspectives

Ce notebook a posé les fondations de toute la série Sudoku en définissant trois composants essentiels. La classe SudokuGrid encapsule la représentation d’une grille 9x9 avec le pré-calcul des voisins (AllNeighbours, CellNeighbours), ce qui évite les recalculs coûteux lors de la résolution. L’interface ISudokuSolver implante le pattern Stratégie, permettant de permuter les algorithmes de résolution sans modifier le code client. Enfin, la classe SudokuHelper fournit une infrastructure de benchmark complète avec chargement de puzzles, mesures de performance et visualisation SVG inline (SvgChartHelper, zéro dépendance).

L’infrastructure de test (TestSolvers, DisplayResults) permet de comparer objectivement les solveurs sur trois niveaux de difficulté (Easy, Medium, Hard) avec gestion des timeouts et des disqualifications. Ce cadre de benchmark sera utilisé dans tous les notebooks suivants pour mesurer les performances de chaque algorithme.

Le notebook suivant, Sudoku-01-Backtracking, utilise ces classes pour implémenter le premier algorithme de résolution : le backtracking récursif avec ses heuristiques d’amélioration.

1. Introduction : Comment les humains résolvent les Sudoku (~3 min)

Les algorithmes que nous avons vus dans les notebooks précédents (backtracking, OR-Tools, Dancing Links, etc.) résolvent les Sudoku par force brute ou par satisfaction de contraintes de manière systématique. Un expert humain procède tout autrement : il applique des techniques de déduction logique de difficulté croissante, en commencant par les plus simples.

Hiérarchie des techniques

Le projet Sudoku.Human identifie 13 techniques, classees par difficulté :

Niveau Technique Principe
Basique Naked Singles Une cellule n’a qu’un seul candidat possible
Basique Hidden Singles Une valeur ne peut aller qu’a un seul endroit dans une unité
Intermédiaire Naked Pairs/Triples N cellules partagent les mêmes N candidats dans une unité
Intermédiaire Hidden Pairs/Triples N valeurs sont restreintes aux mêmes N cellules dans une unité
Intermédiaire Locked Candidates (Pointing) Candidats dans un bloc restreints a une seule ligne/colonne
Intermédiaire Locked Candidates (Claiming) Candidats dans une ligne/colonne restreints a un seul bloc
Avance X-Wing 2 lignes ou le même candidat est restreint aux mêmes 2 colonnes
Avance Y-Wing Chaîne de 3 cellules avec pattern de candidats spécifique
Avance XYZ-Wing Extension du Y-Wing a 3 candidats
Expert Swordfish Extension de X-Wing a 3 lignes/colonnes
Expert Jellyfish Extension de X-Wing a 4 lignes/colonnes
Expert 3D Medusa Technique de coloriage sur graphe de candidats
Expert Unique Rectangles Evitement de patterns mortels (deadly patterns)

Approche du notebook

Nous allons implémenter les techniques les plus courantes et les combiner dans un solveur HumanSolver qui : 1. Maintient une grille de candidats pour chaque cellule vide 2. Applique les techniques dans l’ordre de difficulté croissante 3. Recommence au début a chaque progrès 4. Utilise le backtracking en dernier recours si aucune technique ne fonctionne

2. Infrastructure : Grille de candidats

Avant d’implémenter les techniques, nous avons besoin d’une structure de données pour gerer les candidats de chaque cellule. Pour chaque cellule vide, nous maintenons l’ensemble des valeurs encore possibles.

La classe CandidateGrid encapsule cette logique et fournit des méthodes utilitaires pour : - Initialiser les candidats a partir d’une grille de Sudoku - Eliminer un candidat d’une cellule (avec propagation aux voisins) - Placer une valeur dans une cellule - Interroger les candidats d’une unité (ligne, colonne, bloc)

/// <summary>
/// Grille de candidats pour le solveur humain.
/// Chaque cellule vide possede un ensemble de valeurs candidates (1-9).
/// </summary>
public class CandidateGrid
{
    // Grille 9x9 de HashSet : null si la cellule est resolue, sinon les candidats
    public HashSet<int>[,] Candidates { get; private set; } = new HashSet<int>[9, 9];
    
    // Reference vers la grille de Sudoku associee
    public SudokuGrid Grid { get; private set; }
    
    /// <summary>
    /// Initialise les candidats a partir d'une grille de Sudoku.
    /// Pour chaque cellule vide, les candidats sont les valeurs non presentes chez les voisins.
    /// </summary>
    public CandidateGrid(SudokuGrid grid)
    {
        Grid = grid;
        for (int row = 0; row < 9; row++)
        {
            for (int col = 0; col < 9; col++)
            {
                if (grid.Cells[row, col] == 0)
                {
                    Candidates[row, col] = new HashSet<int>(grid.GetAvailableNumbers(row, col));
                }
                else
                {
                    Candidates[row, col] = null; // Cellule deja resolue
                }
            }
        }
    }
    
    /// <summary>
    /// Place une valeur dans une cellule et elimine cette valeur des candidats des voisins.
    /// Retourne true si le placement est valide (pas de conflit).
    /// </summary>
    public bool PlaceValue(int row, int col, int value)
    {
        Grid.Cells[row, col] = value;
        Candidates[row, col] = null;
        
        // Eliminer la valeur des candidats de tous les voisins
        foreach (var (nRow, nCol) in SudokuGrid.CellNeighbours[row][col])
        {
            if (Candidates[nRow, nCol] != null)
            {
                Candidates[nRow, nCol].Remove(value);
                if (Candidates[nRow, nCol].Count == 0)
                    return false; // Conflit : un voisin n'a plus de candidats
            }
        }
        return true;
    }
    
    /// <summary>
    /// Elimine un candidat d'une cellule. Retourne true si le candidat etait present.
    /// </summary>
    public bool EliminateCandidate(int row, int col, int value)
    {
        if (Candidates[row, col] == null) return false;
        return Candidates[row, col].Remove(value);
    }
    
    /// <summary>
    /// Retourne les cellules non resolues d'une unite donnee (ligne, colonne ou bloc).
    /// </summary>
    public List<(int row, int col, HashSet<int> candidates)> GetUnitCells((int row, int col)[] unit)
    {
        var result = new List<(int, int, HashSet<int>)>();
        foreach (var (r, c) in unit)
        {
            if (Candidates[r, c] != null && Candidates[r, c].Count > 0)
            {
                result.Add((r, c, Candidates[r, c]));
            }
        }
        return result;
    }
    
    /// <summary>
    /// Verifie si le puzzle est completement resolu.
    /// </summary>
    public bool IsSolved()
    {
        for (int row = 0; row < 9; row++)
            for (int col = 0; col < 9; col++)
                if (Grid.Cells[row, col] == 0) return false;
        return true;
    }
    
    /// <summary>
    /// Nombre de cellules encore non resolues.
    /// </summary>
    public int RemainingCells()
    {
        int count = 0;
        for (int row = 0; row < 9; row++)
            for (int col = 0; col < 9; col++)
                if (Grid.Cells[row, col] == 0) count++;
        return count;
    }
    
    /// <summary>
    /// Affiche un resume de l'etat des candidats.
    /// </summary>
    public string Summary()
    {
        int totalCells = 0, totalCandidates = 0;
        for (int row = 0; row < 9; row++)
            for (int col = 0; col < 9; col++)
                if (Candidates[row, col] != null)
                {
                    totalCells++;
                    totalCandidates += Candidates[row, col].Count;
                }
        return $"Cellules non resolues: {totalCells}, Candidats totaux: {totalCandidates}, " +
               $"Moyenne: {(totalCells > 0 ? (double)totalCandidates / totalCells : 0):F1} candidats/cellule";
    }
}

Console.WriteLine("Classe CandidateGrid definie (grille de candidats avec propagation)");
Classe CandidateGrid definie (grille de candidats avec propagation)

Interprétation : CandidateGrid

La classe CandidateGrid est le fondement de toute l’approche humaine. Contrairement au backtracking qui teste les valeurs une a une, ici on maintient en permanence la liste des valeurs possibles pour chaque cellule. C’est exactement ce que fait un joueur humain quand il note les petits chiffres au crayon dans les cases.

Méthode Rôle
PlaceValue Place une valeur et propage l’élimination aux voisins
EliminateCandidate Retire un candidat d’une cellule spécifique
GetUnitCells Recupere les cellules non résolues d’une unité (ligne/colonne/bloc)
IsSolved Vérifié si le puzzle est complètement résolu

Testons cette infrastructure sur un puzzle facile.

// Test de la grille de candidats sur un puzzle facile
var testGrid = SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First();
display($"Puzzle initial :\n{testGrid}");

var candidates = new CandidateGrid(testGrid);
display(candidates.Summary());

// Afficher les candidats de quelques cellules
for (int row = 0; row < 3; row++)
{
    for (int col = 0; col < 3; col++)
    {
        if (candidates.Candidates[row, col] != null)
        {
            var vals = string.Join(", ", candidates.Candidates[row, col].OrderBy(v => v));
            display($"  Cellule ({row},{col}) : candidats = {{{vals}}}");
        }
    }
}
Puzzle initial :
-------------------------------
| 9     2 |       5 | 4     3 | 
| 1       |    6  3 |    2  5 | 
| 5     8 | 4     7 |    6    | 
-------------------------------
|    2  6 | 3     9 |       1 | 
|    5  7 |    1    | 2  9    | 
|    9    | 6  7    | 5  3    | 
-------------------------------
| 2  4    | 5  3    | 6       | 
| 7     5 | 2       | 3     4 | 
|    8    |    4  1 | 9  5    | 
-------------------------------
Cellules non resolues: 36, Candidats totaux: 66, Moyenne: 1,8 candidats/cellule
  Cellule (0,1) : candidats = {6, 7}
  Cellule (1,1) : candidats = {7}
  Cellule (1,2) : candidats = {4}
  Cellule (2,1) : candidats = {3}

Interprétation : Grille de candidats

La sortie montre le fonctionnement de la classe CandidateGrid sur un puzzle facile :

Métrique Valeur observée (puzzle ci-dessus) Signification
Cellules non résolues 36 Nombre de cases vides au départ
Candidats totaux 66 Somme des candidats pour toutes les cellules vides
Moyenne candidats/cellule 1,8 Nombre moyen de possibilités par case

Ce puzzle “facile” est très contraint (beaucoup d’indices de départ), d’ou une moyenne de candidats faible : la plupart des cases vides n’ont déjà plus qu’un ou deux candidats. Sur un puzzle plus difficile, cette moyenne serait nettement plus élevée.

Observation : Les premières cellules non résolues affichees – (0,1) = {6, 7}, (1,1) = {7}, (1,2) = {4}, (2,1) = {3} – montrent leurs candidats respectifs (certaines n’ont déjà plus qu’un seul candidat : ce sont des naked singles). Cette grille de candidats est la base de toutes les techniques humaines qui suivent.

Note technique : La méthode Summary() fournit une vue macroscopique de l’etat du puzzle, utile pour suivre la progression de la résolution.

3. Techniques de base (~5 min)

Les techniques de base suffisent pour résoudre la plupart des puzzles classes “Facile”. Elles reposent sur un principe simple : quand il ne reste qu’une seule possibilité, on peut placer la valeur avec certitude.

3.1 Naked Singles (Singleton nu)

Principe : Si une cellule n’a qu’un seul candidat, ce candidat est forcement la valeur de cette cellule.

C’est la technique la plus simple et la plus intuitive. Quand on élimine suffisamment de candidats par les contraintes de ligne, colonne et bloc, il ne reste parfois qu’un seul choix possible.

\[\text{Si } |\text{Candidats}(r, c)| = 1 \Rightarrow \text{Placer}(r, c, \text{unique candidat})\]

3.2 Hidden Singles (Singleton cache)

Principe : Si une valeur n’apparait comme candidat que dans une seule cellule d’une unité (ligne, colonne ou bloc), alors cette cellule doit contenir cette valeur, même si elle a d’autres candidats.

\[\forall \text{unité } U, \forall v \in \{1..9\} : |\{c \in U : v \in \text{Candidats}(c)\}| = 1 \Rightarrow \text{Placer}(c, v)\]

Cette technique est plus puissante que les Naked Singles car elle peut trouver des placements même quand une cellule a plusieurs candidats.

Exercice : Compter les naked singles par difficulté

Objectif : Comptez combien de naked singles peuvent être trouves dans des puzzles de différentes difficultés.

Indice : Utilisez FindNakedSingles sur plusieurs puzzles et calculez la moyenne par difficulté.

// EXERCICE : Compter les naked singles par difficulte
public Dictionary<string, double> CountNakedSinglesByDifficulty()
{
    // TODO: Pour chaque difficulte, chargez les puzzles et comptez
    // le nombre moyen de naked singles trouves
    return null; // TODO etudiant
}
Console.WriteLine("Exercice a completer");
Exercice a completer
/// <summary>
/// Contient les techniques de resolution humaines.
/// Chaque technique retourne le nombre de placements ou eliminations effectues.
/// </summary>
public static class HumanTechniques
{
    /// <summary>
    /// Naked Singles : place les cellules qui n'ont qu'un seul candidat.
    /// Retourne le nombre de placements effectues.
    /// </summary>
    public static int ApplyNakedSingles(CandidateGrid cg)
    {
        int placements = 0;
        bool progress = true;
        
        while (progress)
        {
            progress = false;
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if (cg.Candidates[row, col] != null && cg.Candidates[row, col].Count == 1)
                    {
                        int value = cg.Candidates[row, col].First();
                        cg.PlaceValue(row, col, value);
                        placements++;
                        progress = true;
                    }
                }
            }
        }
        return placements;
    }
    
    /// <summary>
    /// Hidden Singles : pour chaque unite, si une valeur n'a qu'un seul emplacement possible,
    /// la placer dans cette cellule.
    /// Retourne le nombre de placements effectues.
    /// </summary>
    public static int ApplyHiddenSingles(CandidateGrid cg)
    {
        int placements = 0;
        
        // Parcourir toutes les unites (9 lignes + 9 colonnes + 9 blocs = 27 unites)
        foreach (var unit in SudokuGrid.AllNeighbours)
        {
            var cells = cg.GetUnitCells(unit);
            if (cells.Count == 0) continue;
            
            // Pour chaque valeur de 1 a 9
            for (int val = 1; val <= 9; val++)
            {
                // Trouver les cellules de cette unite qui ont val comme candidat
                var cellsWithVal = cells.Where(c => c.candidates.Contains(val)).ToList();
                
                if (cellsWithVal.Count == 1)
                {
                    var (row, col, _) = cellsWithVal[0];
                    if (cg.Grid.Cells[row, col] == 0) // Pas encore place
                    {
                        cg.PlaceValue(row, col, val);
                        placements++;
                    }
                }
            }
        }
        return placements;
    }
}

Console.WriteLine("Classe HumanTechniques definie (Naked Singles + Hidden Singles)");
Classe HumanTechniques definie (Naked Singles + Hidden Singles)

Test des techniques de base

Testons ces deux techniques sur un puzzle facile. Les puzzles faciles sont généralement resolubles uniquement avec Naked Singles et Hidden Singles.

// Test sur un puzzle facile
var easyPuzzle = (SudokuGrid)SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First().Clone();
var cg = new CandidateGrid(easyPuzzle);

display($"Puzzle facile initial : {cg.RemainingCells()} cellules vides");
display(cg.Summary());

int totalPlacements = 0;
int round = 0;
bool madeProgress = true;

while (madeProgress && !cg.IsSolved())
{
    madeProgress = false;
    round++;
    
    int ns = HumanTechniques.ApplyNakedSingles(cg);
    if (ns > 0)
    {
        display($"  Tour {round} - Naked Singles : {ns} placements");
        totalPlacements += ns;
        madeProgress = true;
    }
    
    int hs = HumanTechniques.ApplyHiddenSingles(cg);
    if (hs > 0)
    {
        display($"  Tour {round} - Hidden Singles : {hs} placements");
        totalPlacements += hs;
        madeProgress = true;
    }
}

display($"\nResultat : {(cg.IsSolved() ? "RESOLU" : "BLOQUE")} apres {totalPlacements} placements en {round} tours");
display($"{easyPuzzle}");
Puzzle facile initial : 36 cellules vides
Cellules non resolues: 36, Candidats totaux: 66, Moyenne: 1,8 candidats/cellule
  Tour 1 - Naked Singles : 36 placements

Resultat : RESOLU apres 36 placements en 1 tours
-------------------------------
| 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 | 
-------------------------------

Interprétation : Techniques de base

Observation : Les techniques de base (Naked Singles + Hidden Singles) suffisent généralement pour résoudre les puzzles de difficulté “Easy”. C’est conforme a la classification standard des puzzles de Sudoku.

Technique Quand l’utiliser Complexité cognitive
Naked Singles Chaque itération, en premier Très faible
Hidden Singles Après les Naked Singles Faible

Note : Les Hidden Singles sont souvent plus productifs que les Naked Singles car ils exploitent la contrainte d’unicité au sein d’une unité, même quand une cellule a plusieurs candidats.

Essayons maintenant sur un puzzle de difficulté moyenne pour voir les limites de ces techniques.

// Test sur un puzzle moyen : les techniques de base ne suffisent plus
var mediumPuzzle = (SudokuGrid)SudokuHelper.GetSudokus(SudokuDifficulty.Medium).First().Clone();
var cgMedium = new CandidateGrid(mediumPuzzle);

display($"Puzzle moyen initial : {cgMedium.RemainingCells()} cellules vides");

int totalMedium = 0;
bool progress = true;
while (progress && !cgMedium.IsSolved())
{
    progress = false;
    int ns = HumanTechniques.ApplyNakedSingles(cgMedium);
    int hs = HumanTechniques.ApplyHiddenSingles(cgMedium);
    totalMedium += ns + hs;
    progress = (ns + hs) > 0;
}

display($"Resultat avec techniques de base uniquement : {(cgMedium.IsSolved() ? "RESOLU" : "BLOQUE")}");
display($"Placements effectues : {totalMedium}, Cellules restantes : {cgMedium.RemainingCells()}");
display(cgMedium.Summary());
Puzzle moyen initial : 59 cellules vides
Resultat avec techniques de base uniquement : BLOQUE
Placements effectues : 11, Cellules restantes : 48
Cellules non resolues: 48, Candidats totaux: 169, Moyenne: 3,5 candidats/cellule

Interprétation : Limites des techniques de base

Comme on le voit, les techniques de base se bloquent sur les puzzles de difficulté moyenne. Il reste des cellules non résolues car aucune cellule n’a un seul candidat et aucune valeur n’est restreinte a une seule position dans ses unités. Il faut des techniques plus sophistiquées pour progresser.

C’est la que les techniques intermédiaires entrent en jeu : elles ne placent pas directement de valeurs, mais eliminent des candidats, ce qui peut débloquer les Naked Singles et Hidden Singles.

4. Techniques intermédiaires (~5 min)

Les techniques intermédiaires opèrent par élimination de candidats plutôt que par placement direct de valeurs. Elles identifient des patterns dans les candidats qui permettent de déduire que certaines valeurs sont impossibles dans certaines cellules.

4.1 Naked Pairs (Paires nues)

Principe : Si deux cellules dans une même unité contiennent exactement les mêmes deux candidats, alors ces deux valeurs sont “réservées” pour ces deux cellules. On peut les éliminer des autres cellules de l’unité.

Exemple : Si dans une ligne, les cellules A et B ont toutes deux les candidats {3, 7}, alors 3 et 7 seront forcement dans A et B. On peut éliminer 3 et 7 des candidats de toutes les autres cellules de cette ligne.

\[\text{Si } C_1 = C_2 = \{a, b\} \text{ dans unité } U \Rightarrow \forall c \in U \setminus \{C_1, C_2\} : \text{éliminer } a, b \text{ de } C_c\]

Ce principe se generalise aux Naked Triples (3 cellules, 3 candidats) et au-dela.

4.2 Locked Candidates (Candidats verrouilles)

Il existe deux variantes :

Pointing : Si dans un bloc 3x3, un candidat n’apparait que dans une seule ligne (ou colonne), alors ce candidat peut être élimine des autres cellules de cette ligne (ou colonne) en dehors du bloc.

Claiming : Si dans une ligne (ou colonne), un candidat n’apparait que dans un seul bloc, alors ce candidat peut être élimine des autres cellules de ce bloc en dehors de la ligne (ou colonne).

// Ajout des techniques intermediaires a la classe HumanTechniques
public static class HumanTechniquesIntermediate
{
    /// <summary>
    /// Naked Pairs : dans chaque unite, si 2 cellules ont exactement les memes 2 candidats,
    /// eliminer ces candidats des autres cellules de l'unite.
    /// Retourne le nombre d'eliminations effectuees.
    /// </summary>
    public static int ApplyNakedPairs(CandidateGrid cg)
    {
        int eliminations = 0;
        
        foreach (var unit in SudokuGrid.AllNeighbours)
        {
            var cells = cg.GetUnitCells(unit);
            
            // Chercher les cellules avec exactement 2 candidats
            var pairCells = cells.Where(c => c.candidates.Count == 2).ToList();
            
            for (int i = 0; i < pairCells.Count; i++)
            {
                for (int j = i + 1; j < pairCells.Count; j++)
                {
                    // Verifier si les deux cellules ont les memes candidats
                    if (pairCells[i].candidates.SetEquals(pairCells[j].candidates))
                    {
                        var pairValues = pairCells[i].candidates;
                        
                        // Eliminer ces valeurs des autres cellules de l'unite
                        foreach (var cell in cells)
                        {
                            if ((cell.row, cell.col) != (pairCells[i].row, pairCells[i].col) &&
                                (cell.row, cell.col) != (pairCells[j].row, pairCells[j].col))
                            {
                                foreach (int val in pairValues)
                                {
                                    if (cg.EliminateCandidate(cell.row, cell.col, val))
                                        eliminations++;
                                }
                            }
                        }
                    }
                }
            }
        }
        return eliminations;
    }
    
    /// <summary>
    /// Locked Candidates (Pointing) : si dans un bloc, un candidat n'est present
    /// que dans une seule ligne ou colonne, l'eliminer du reste de cette ligne/colonne.
    /// Retourne le nombre d'eliminations effectuees.
    /// </summary>
    public static int ApplyLockedCandidatesPointing(CandidateGrid cg)
    {
        int eliminations = 0;
        
        // Parcourir les 9 blocs 3x3
        for (int box = 0; box < 9; box++)
        {
            int startRow = (box / 3) * 3;
            int startCol = (box % 3) * 3;
            
            for (int val = 1; val <= 9; val++)
            {
                // Trouver les positions du candidat val dans ce bloc
                var positions = new List<(int row, int col)>();
                for (int r = startRow; r < startRow + 3; r++)
                    for (int c = startCol; c < startCol + 3; c++)
                        if (cg.Candidates[r, c] != null && cg.Candidates[r, c].Contains(val))
                            positions.Add((r, c));
                
                if (positions.Count < 2) continue;
                
                // Verifier si toutes les positions sont sur la meme ligne
                if (positions.All(p => p.row == positions[0].row))
                {
                    int row = positions[0].row;
                    // Eliminer val du reste de cette ligne (hors du bloc)
                    for (int c = 0; c < 9; c++)
                    {
                        if (c < startCol || c >= startCol + 3) // Hors du bloc
                        {
                            if (cg.EliminateCandidate(row, c, val))
                                eliminations++;
                        }
                    }
                }
                
                // Verifier si toutes les positions sont sur la meme colonne
                if (positions.All(p => p.col == positions[0].col))
                {
                    int col = positions[0].col;
                    // Eliminer val du reste de cette colonne (hors du bloc)
                    for (int r = 0; r < 9; r++)
                    {
                        if (r < startRow || r >= startRow + 3) // Hors du bloc
                        {
                            if (cg.EliminateCandidate(r, col, val))
                                eliminations++;
                        }
                    }
                }
            }
        }
        return eliminations;
    }
    
    /// <summary>
    /// Locked Candidates (Claiming) : si dans une ligne/colonne, un candidat n'est present
    /// que dans un seul bloc, l'eliminer du reste de ce bloc.
    /// Retourne le nombre d'eliminations effectuees.
    /// </summary>
    public static int ApplyLockedCandidatesClaiming(CandidateGrid cg)
    {
        int eliminations = 0;
        
        for (int val = 1; val <= 9; val++)
        {
            // Verifier chaque ligne
            for (int row = 0; row < 9; row++)
            {
                var cols = new List<int>();
                for (int c = 0; c < 9; c++)
                    if (cg.Candidates[row, c] != null && cg.Candidates[row, c].Contains(val))
                        cols.Add(c);
                
                if (cols.Count < 2) continue;
                
                // Verifier si toutes les colonnes sont dans le meme bloc
                int boxCol = cols[0] / 3;
                if (cols.All(c => c / 3 == boxCol))
                {
                    int startCol = boxCol * 3;
                    int startRow = (row / 3) * 3;
                    // Eliminer val du reste du bloc (hors de cette ligne)
                    for (int r = startRow; r < startRow + 3; r++)
                    {
                        if (r != row)
                        {
                            for (int c = startCol; c < startCol + 3; c++)
                            {
                                if (cg.EliminateCandidate(r, c, val))
                                    eliminations++;
                            }
                        }
                    }
                }
            }
            
            // Verifier chaque colonne
            for (int col = 0; col < 9; col++)
            {
                var rows = new List<int>();
                for (int r = 0; r < 9; r++)
                    if (cg.Candidates[r, col] != null && cg.Candidates[r, col].Contains(val))
                        rows.Add(r);
                
                if (rows.Count < 2) continue;
                
                // Verifier si toutes les lignes sont dans le meme bloc
                int boxRow = rows[0] / 3;
                if (rows.All(r => r / 3 == boxRow))
                {
                    int startRow = boxRow * 3;
                    int startCol = (col / 3) * 3;
                    // Eliminer val du reste du bloc (hors de cette colonne)
                    for (int r = startRow; r < startRow + 3; r++)
                    {
                        for (int c = startCol; c < startCol + 3; c++)
                        {
                            if (c != col)
                            {
                                if (cg.EliminateCandidate(r, c, val))
                                    eliminations++;
                            }
                        }
                    }
                }
            }
        }
        return eliminations;
    }
}

Console.WriteLine("Classe HumanTechniquesIntermediate definie (Naked Pairs + Locked Candidates Pointing/Claiming)");
Classe HumanTechniquesIntermediate definie (Naked Pairs + Locked Candidates Pointing/Claiming)

Interprétation : Techniques intermédiaires

Les techniques intermédiaires fonctionnent différemment des techniques de base :

Aspect Techniques de base Techniques intermédiaires
Action Placent des valeurs Eliminent des candidats
Effet Réduction directe des cellules vides Réduction indirecte (déblocage pour les techniques de base)
Complexité O(81) par passe O(81 * 9) par passe

L’enchainement typique est : 1. Appliquer les éliminations (Naked Pairs, Locked Candidates) 2. Reappliquer les techniques de base (Naked Singles, Hidden Singles) 3. Si progrès, recommencer au point 1

Note : Les Hidden Pairs (N valeurs restreintes aux mêmes N cellules dans une unité, éliminer les autres candidats de ces cellules) sont le dual des Naked Pairs mais ne sont pas implementes ici par souci de concision.

5. Technique avancée : X-Wing (~5 min)

Principe du X-Wing

Le X-Wing est une technique basee sur les lignes et colonnes. Le pattern est le suivant :

Si un candidat v n’apparait que dans exactement 2 colonnes dans 2 lignes différentes, et que ces 2 colonnes sont les mêmes dans les 2 lignes, alors v peut être élimine de toutes les autres cellules de ces 2 colonnes.

Ligne r1 : v possible en (r1, c1) et (r1, c2) uniquement
Ligne r2 : v possible en (r2, c1) et (r2, c2) uniquement
           => v est forcement dans les coins du rectangle
           => Eliminer v de (c1, autres lignes) et (c2, autres lignes)

Le même raisonnement s’applique en inversant lignes et colonnes.

Généralisation : Le Swordfish (3 lignes, 3 colonnes) et le Jellyfish (4 lignes, 4 colonnes) suivent le même principe avec plus de lignes/colonnes.

Exercice : Implémenter la technique Hidden Pair

Objectif : Implémentez la detection des Hidden Pairs : quand deux valeurs n’apparaissent que dans deux cellules d’une même unité, eliminez les autres candidats de ces cellules.

Étape 1 : Parcourez chaque unité et identifiez les valeurs qui n’apparaissent que 2 fois. Étape 2 : Verifiez si ces 2 valeurs partagent les mêmes 2 cellules.

// EXERCICE : Implementer la technique Hidden Pair
public List<((int, int) Cell1, (int, int) Cell2, HashSet<int> Pair)> FindHiddenPairs(int[,] candidatesGrid)
{
    // TODO: Trouvez les hidden pairs dans la grille de candidats
    // Retournez la liste des paires avec leurs positions et valeurs
    return null; // TODO etudiant
}
Console.WriteLine("Exercice a completer");
Exercice a completer
public static class HumanTechniquesAdvanced
{
    /// <summary>
    /// X-Wing : si un candidat v apparait dans exactement 2 colonnes pour 2 lignes,
    /// eliminer v des autres cellules de ces colonnes.
    /// Applique aussi la variante colonne (2 lignes dans 2 colonnes).
    /// Retourne le nombre d'eliminations effectuees.
    /// </summary>
    public static int ApplyXWing(CandidateGrid cg)
    {
        int eliminations = 0;
        
        for (int val = 1; val <= 9; val++)
        {
            // X-Wing sur les lignes
            eliminations += ApplyXWingOnRows(cg, val);
            
            // X-Wing sur les colonnes
            eliminations += ApplyXWingOnCols(cg, val);
        }
        
        return eliminations;
    }
    
    private static int ApplyXWingOnRows(CandidateGrid cg, int val)
    {
        int eliminations = 0;
        
        // Pour chaque ligne, trouver les colonnes ou val est candidat
        var rowPositions = new List<int>[9];
        for (int r = 0; r < 9; r++)
        {
            rowPositions[r] = new List<int>();
            for (int c = 0; c < 9; c++)
                if (cg.Candidates[r, c] != null && cg.Candidates[r, c].Contains(val))
                    rowPositions[r].Add(c);
        }
        
        // Chercher 2 lignes avec exactement les memes 2 colonnes
        for (int r1 = 0; r1 < 9; r1++)
        {
            if (rowPositions[r1].Count != 2) continue;
            
            for (int r2 = r1 + 1; r2 < 9; r2++)
            {
                if (rowPositions[r2].Count != 2) continue;
                
                if (rowPositions[r1][0] == rowPositions[r2][0] &&
                    rowPositions[r1][1] == rowPositions[r2][1])
                {
                    int c1 = rowPositions[r1][0];
                    int c2 = rowPositions[r1][1];
                    
                    // Eliminer val des colonnes c1 et c2 (hors lignes r1, r2)
                    for (int r = 0; r < 9; r++)
                    {
                        if (r != r1 && r != r2)
                        {
                            if (cg.EliminateCandidate(r, c1, val)) eliminations++;
                            if (cg.EliminateCandidate(r, c2, val)) eliminations++;
                        }
                    }
                }
            }
        }
        return eliminations;
    }
    
    private static int ApplyXWingOnCols(CandidateGrid cg, int val)
    {
        int eliminations = 0;
        
        // Pour chaque colonne, trouver les lignes ou val est candidat
        var colPositions = new List<int>[9];
        for (int c = 0; c < 9; c++)
        {
            colPositions[c] = new List<int>();
            for (int r = 0; r < 9; r++)
                if (cg.Candidates[r, c] != null && cg.Candidates[r, c].Contains(val))
                    colPositions[c].Add(r);
        }
        
        // Chercher 2 colonnes avec exactement les memes 2 lignes
        for (int c1 = 0; c1 < 9; c1++)
        {
            if (colPositions[c1].Count != 2) continue;
            
            for (int c2 = c1 + 1; c2 < 9; c2++)
            {
                if (colPositions[c2].Count != 2) continue;
                
                if (colPositions[c1][0] == colPositions[c2][0] &&
                    colPositions[c1][1] == colPositions[c2][1])
                {
                    int r1 = colPositions[c1][0];
                    int r2 = colPositions[c1][1];
                    
                    // Eliminer val des lignes r1 et r2 (hors colonnes c1, c2)
                    for (int c = 0; c < 9; c++)
                    {
                        if (c != c1 && c != c2)
                        {
                            if (cg.EliminateCandidate(r1, c, val)) eliminations++;
                            if (cg.EliminateCandidate(r2, c, val)) eliminations++;
                        }
                    }
                }
            }
        }
        return eliminations;
    }
}

Console.WriteLine("Classe HumanTechniquesAdvanced definie (X-Wing lignes + colonnes)");
Classe HumanTechniquesAdvanced definie (X-Wing lignes + colonnes)

Interprétation : X-Wing

Le X-Wing est la première technique qui raisonne sur plusieurs unités simultanément. Les techniques précédentes (Naked Singles, Hidden Singles, Naked Pairs, Locked Candidates) raisonnent unité par unité.

Technique Portee Type de pattern
Naked/Hidden Singles 1 unité Unicite
Naked Pairs 1 unité Exclusion mutuelle
Locked Candidates 2 unités (bloc + ligne/col) Intersection
X-Wing 2 lignes + 2 colonnes Rectangle

Pour aller plus loin : Les techniques Y-Wing et XYZ-Wing forment des chaînes de cellules bivalue. Le Y-Wing utilisé 3 cellules avec 2 candidats chacune, formant un “pivot” et deux “pinces”. Toute cellule visible par les deux pinces peut voir ses candidats reduits. Ces techniques sont trop complexes pour être détaillées ici mais suivent le même principe d’élimination par déduction logique.

6. Techniques expertes (apercu) (~3 min)

Les techniques suivantes sont mentionnees pour référence. Elles sont implementees dans le projet Sudoku.Human mais leur complexité dépasse le cadre de ce notebook.

6.1 Fish Patterns (Swordfish, Jellyfish)

Généralisation du X-Wing a N lignes/colonnes :

Pattern Dimension Description
X-Wing 2x2 2 lignes, 2 colonnes
Swordfish 3x3 3 lignes, 3 colonnes (candidat dans au plus 3 colonnes par ligne)
Jellyfish 4x4 4 lignes, 4 colonnes

Le principe est identique : si un candidat est restreint a au plus N colonnes dans N lignes, et que l’ensemble des colonnes est le même, on peut éliminer ce candidat des autres cellules de ces colonnes.

6.2 3D Medusa (Coloriage)

La 3D Medusa est une technique de coloriage (coloring). Elle construit un graphe ou les noeuds sont les candidats et les arêtes représentent les relations “si ce candidat est vrai, alors cet autre est faux” (conjugues). En alternant deux couleurs, on peut déduire des éliminations par contradiction.

6.3 Rectangles (Unique, Hidden, Avoidable)

Ces techniques exploitent le fait qu’un Sudoku bien pose a une solution unique. Si un pattern de candidats crée un “deadly pattern” (rectangle mortel) qui admettrait deux solutions, on peut éliminer les candidats qui y participent.

Unique Rectangle : 4 cellules aux coins d’un rectangle (dans 2 lignes, 2 colonnes, 2 blocs) avec les mêmes 2 candidats. Si ce pattern existe, il faut le casser pour preserver l’unicité de la solution.

7. Solveur humain complet (~4 min)

Nous assemblons maintenant toutes les techniques dans un solveur HumanSolver qui implémente ISudokuSolver. Le solveur :

  1. Initialise la grille de candidats
  2. Boucle : applique les techniques dans l’ordre de difficulté croissante
  3. Trace quelle technique a été utilisée a chaque étape
  4. Fallback : si aucune technique humaine ne progresse, utilisé le backtracking

Cette approche hybride garantit la résolution de tout puzzle valide, tout en privilegiant les techniques humaines tant que possible.

/// <summary>
/// Solveur de Sudoku imitant le raisonnement humain.
/// Applique les techniques de deduction logique avant de recourir au backtracking.
/// </summary>
public class HumanSolver : ISudokuSolver
{
    // Historique des techniques utilisees
    public List<(string Technique, int Count)> SolveLog { get; private set; } = new();
    
    // Indique si le backtracking a ete necessaire
    public bool UsedBacktracking { get; private set; } = false;
    
    /// <summary>
    /// Resout le Sudoku en appliquant les techniques humaines puis le backtracking si necessaire.
    /// </summary>
    public SudokuGrid Solve(SudokuGrid s)
    {
        SolveLog.Clear();
        UsedBacktracking = false;
        
        // Travailler sur une copie
        var grid = (SudokuGrid)s.Clone();
        var cg = new CandidateGrid(grid);
        
        // Appliquer les techniques humaines en boucle
        ApplyHumanTechniques(cg);
        
        // Si le puzzle n'est pas resolu, utiliser le backtracking
        if (!cg.IsSolved())
        {
            UsedBacktracking = true;
            SolveLog.Add(("Backtracking (fallback)", cg.RemainingCells()));
            BacktrackingSolve(grid);
        }
        
        // Copier le resultat dans la grille originale
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                s.Cells[r, c] = grid.Cells[r, c];
        
        return s;
    }
    
    /// <summary>
    /// Applique les techniques humaines de maniere iterative.
    /// A chaque progres, recommence depuis le debut (les techniques les plus simples).
    /// </summary>
    private void ApplyHumanTechniques(CandidateGrid cg)
    {
        bool progress = true;
        
        while (progress && !cg.IsSolved())
        {
            progress = false;
            
            // 1. Naked Singles
            int ns = HumanTechniques.ApplyNakedSingles(cg);
            if (ns > 0)
            {
                SolveLog.Add(("Naked Singles", ns));
                progress = true;
                continue; // Recommencer depuis le debut
            }
            
            // 2. Hidden Singles
            int hs = HumanTechniques.ApplyHiddenSingles(cg);
            if (hs > 0)
            {
                SolveLog.Add(("Hidden Singles", hs));
                progress = true;
                continue;
            }
            
            // 3. Naked Pairs
            int np = HumanTechniquesIntermediate.ApplyNakedPairs(cg);
            if (np > 0)
            {
                SolveLog.Add(("Naked Pairs (eliminations)", np));
                progress = true;
                continue;
            }
            
            // 4. Locked Candidates (Pointing)
            int lp = HumanTechniquesIntermediate.ApplyLockedCandidatesPointing(cg);
            if (lp > 0)
            {
                SolveLog.Add(("Locked Candidates - Pointing (eliminations)", lp));
                progress = true;
                continue;
            }
            
            // 5. Locked Candidates (Claiming)
            int lc = HumanTechniquesIntermediate.ApplyLockedCandidatesClaiming(cg);
            if (lc > 0)
            {
                SolveLog.Add(("Locked Candidates - Claiming (eliminations)", lc));
                progress = true;
                continue;
            }
            
            // 6. X-Wing
            int xw = HumanTechniquesAdvanced.ApplyXWing(cg);
            if (xw > 0)
            {
                SolveLog.Add(("X-Wing (eliminations)", xw));
                progress = true;
                continue;
            }
        }
    }
    
    /// <summary>
    /// Backtracking simple utilise en dernier recours.
    /// </summary>
    private bool BacktrackingSolve(SudokuGrid grid)
    {
        // Trouver la premiere cellule vide
        for (int row = 0; row < 9; row++)
        {
            for (int col = 0; col < 9; col++)
            {
                if (grid.Cells[row, col] == 0)
                {
                    foreach (int val in grid.GetAvailableNumbers(row, col))
                    {
                        grid.Cells[row, col] = val;
                        if (BacktrackingSolve(grid))
                            return true;
                        grid.Cells[row, col] = 0;
                    }
                    return false;
                }
            }
        }
        return true; // Toutes les cellules remplies
    }
    
    /// <summary>
    /// Affiche le journal de resolution.
    /// </summary>
    public string GetSolveReport()
    {
        var sb = new StringBuilder();
        sb.AppendLine("--- Journal de resolution ---");
        int step = 1;
        foreach (var (technique, count) in SolveLog)
        {
            sb.AppendLine($"  Etape {step++}: {technique} x{count}");
        }
        sb.AppendLine($"  Backtracking necessaire : {(UsedBacktracking ? "OUI" : "NON")}");
        sb.AppendLine($"  Total etapes : {SolveLog.Count}");
        return sb.ToString();
    }
}

Console.WriteLine("Classe HumanSolver definie (pipeline de techniques humaines avec fallback backtracking)");
Classe HumanSolver definie (pipeline de techniques humaines avec fallback backtracking)

Interprétation : Architecture du HumanSolver

Le HumanSolver suit un pattern classique de pipeline de stratégies :

Boucle principale
  |-> Naked Singles (basique)
  |-> Hidden Singles (basique)
  |-> Naked Pairs (intermédiaire)
  |-> Locked Candidates Pointing (intermédiaire)
  |-> Locked Candidates Claiming (intermédiaire)
  |-> X-Wing (avancé)
  |-> [Si bloque] Backtracking (fallback)

Le point clé est le continue après chaque progrès : des qu’une technique fait avancer la résolution, on recommence au début. Cela maximise l’utilisation des techniques simples (rapides) avant de passer aux techniques complexes (couteuses).

Le journal de résolution (SolveLog) permet d’analyser quelles techniques ont été necessaires pour chaque puzzle, ce qui est directement lie a la difficulté du puzzle.

Test du solveur humain complet

Testons le HumanSolver sur des puzzles de chaque difficulté et observons les techniques utilisees.

var humanSolver = new HumanSolver();

// Test sur puzzle facile
display("=== PUZZLE FACILE ===");
var easy = (SudokuGrid)SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First().Clone();
var easySolved = humanSolver.Solve(easy);
display($"Erreurs : {easySolved.NbErrors(SudokuHelper.GetSudokus(SudokuDifficulty.Easy).First())}");
display(humanSolver.GetSolveReport());

// Test sur puzzle moyen
display("\n=== PUZZLE MOYEN ===");
var medium = (SudokuGrid)SudokuHelper.GetSudokus(SudokuDifficulty.Medium).First().Clone();
humanSolver = new HumanSolver();
var mediumSolved = humanSolver.Solve(medium);
display($"Erreurs : {mediumSolved.NbErrors(SudokuHelper.GetSudokus(SudokuDifficulty.Medium).First())}");
display(humanSolver.GetSolveReport());

// Test sur puzzle difficile
display("\n=== PUZZLE DIFFICILE ===");
var hard = (SudokuGrid)SudokuHelper.GetSudokus(SudokuDifficulty.Hard).First().Clone();
humanSolver = new HumanSolver();
var hardSolved = humanSolver.Solve(hard);
display($"Erreurs : {hardSolved.NbErrors(SudokuHelper.GetSudokus(SudokuDifficulty.Hard).First())}");
display(humanSolver.GetSolveReport());
=== PUZZLE FACILE ===
Erreurs : 0
--- Journal de resolution ---
  Etape 1: Naked Singles x36
  Backtracking necessaire : NON
  Total etapes : 1

=== PUZZLE MOYEN ===
Erreurs : 0
--- Journal de resolution ---
  Etape 1: Hidden Singles x6
  Etape 2: Naked Singles x1
  Etape 3: Hidden Singles x3
  Etape 4: Hidden Singles x1
  Etape 5: Naked Pairs (eliminations) x9
  Etape 6: Locked Candidates - Pointing (eliminations) x17
  Etape 7: Naked Singles x19
  Etape 8: Hidden Singles x9
  Etape 9: Hidden Singles x6
  Etape 10: Naked Singles x14
  Backtracking necessaire : NON
  Total etapes : 10

=== PUZZLE DIFFICILE ===
Erreurs : 0
--- Journal de resolution ---
  Etape 1: Hidden Singles x3
  Etape 2: Locked Candidates - Pointing (eliminations) x21
  Etape 3: Naked Singles x6
  Etape 4: Hidden Singles x2
  Etape 5: Hidden Singles x2
  Etape 6: Naked Pairs (eliminations) x15
  Etape 7: Naked Singles x2
  Etape 8: Hidden Singles x4
  Etape 9: Naked Singles x45
  Backtracking necessaire : NON
  Total etapes : 9

Interprétation : Résultats du HumanSolver

Le journal de résolution ci-dessus montre quelles techniques sont mobilisées sur trois exemples (un par niveau) :

Difficulté Techniques utilisees (journal ci-dessus) Backtracking
Easy Naked Singles seuls Non
Medium Hidden Singles, Naked Singles, Naked Pairs, Locked Candidates Non
Hard Hidden Singles, Naked Singles, Naked Pairs, Locked Candidates Non

Sur ces trois grilles, les techniques humaines suffisent et le backtracking n’est jamais déclenché – y compris sur l’exemple “Hard”, résolu sans X-Wing.

Observation : ces exemples sont favorables. Sur l’ensemble du fichier de test (Sudoku_top95.txt, parmi les plus difficiles connus, cf. analyse statistique plus bas), une partie des puzzles Medium et Hard necessite tout de même le fallback backtracking, car le solveur n’implémente pas les techniques les plus avancées (Swordfish, 3D Medusa, Unique Rectangles).

Comparaison avec les autres solveurs

Comparons maintenant les performances du HumanSolver avec le BacktrackingDotNetSolver (le même algorithme que le notebook 1, redéfini inline plus bas pour éviter les conflits de type lies a l’import). Le solveur humain est conçu pour être compréhensible, pas nécessairement rapide. Voyons comment il se compare en termes de temps d’exécution.

/// <summary>
/// Solveur par backtracking pur (pour comparaison avec le HumanSolver).
/// Defini inline pour eviter les conflits de type lies a l'import de Sudoku-01.
/// </summary>
public class BacktrackingDotNetSolver : ISudokuSolver
{
    private int callCount = 0;

    public SudokuGrid Solve(SudokuGrid s)
    {
        callCount = 0;
        Search(s, 0, 0);
        Console.WriteLine($"BacktrackingDotNetSolver: {callCount} search calls");
        return s;
    }

    private bool Search(SudokuGrid s, int row, int col)
    {
        callCount++;
        if (row == 9) return true;
        if (col == 9) return Search(s, row + 1, 0);
        if (s.Cells[row, col] != 0) return Search(s, row, col + 1);

        for (int num = 1; num <= 9; num++)
        {
            if (IsValid(s, row, col, num))
            {
                s.Cells[row, col] = num;
                if (Search(s, row, col + 1)) return true;
                s.Cells[row, col] = 0;
            }
        }
        return false;
    }

    private bool IsValid(SudokuGrid s, int row, int col, int val)
    {
        for (int i = 0; i < 9; i++)
            if (s.Cells[row, i] == val || s.Cells[i, col] == val)
                return false;

        int startRow = 3 * (row / 3), startCol = 3 * (col / 3);
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (s.Cells[startRow + i, startCol + j] == val)
                    return false;

        return true;
    }
}

Console.WriteLine("Classe BacktrackingDotNetSolver definie (solveur de reference pour comparaison)");
Classe BacktrackingDotNetSolver definie (solveur de reference pour comparaison)

Configuration des solvers et benchmark comparatif des stratégies humaines.

var solvers = new List<(string Name, ISudokuSolver Solver)>
{
    ("HumanSolver", new HumanSolver()),
    ("BacktrackingDotNetSolver", new BacktrackingDotNetSolver())
};

var results = SudokuHelper.TestSolvers(solvers, numberOfSudokus: 10, timeLimitMilliseconds: 5000);

// Affichage des resultats
display("\nResultats de performance :");
foreach (var result in results)
{
    display($"{result.SolverName} | {result.Difficulty} | {result.Time:F1} ms | {result.SolvedCount}/10 | {result.Status}");
}
Running tests...
BacktrackingDotNetSolver: 122 search calls
BacktrackingDotNetSolver: 311 search calls
BacktrackingDotNetSolver: 477 search calls
BacktrackingDotNetSolver: 25565 search calls
BacktrackingDotNetSolver: 2544 search calls
BacktrackingDotNetSolver: 149 search calls
BacktrackingDotNetSolver: 92214 search calls
BacktrackingDotNetSolver: 4797 search calls
BacktrackingDotNetSolver: 137 search calls
BacktrackingDotNetSolver: 171377 search calls
BacktrackingDotNetSolver: 490304 search calls
BacktrackingDotNetSolver: 15387 search calls
BacktrackingDotNetSolver: 337036 search calls
BacktrackingDotNetSolver: 114216 search calls
BacktrackingDotNetSolver: 250684 search calls
BacktrackingDotNetSolver: 12779 search calls
BacktrackingDotNetSolver: 14171 search calls
BacktrackingDotNetSolver: 1474 search calls
BacktrackingDotNetSolver: 80027 search calls
BacktrackingDotNetSolver: 15893 search calls

Resultats de performance :
HumanSolver | Easy | 15,4 ms | 10/10 | Success
HumanSolver | Medium | 136,1 ms | 10/10 | Success
HumanSolver | Hard | 5457,8 ms | 4/10 | Disqualified
BacktrackingDotNetSolver | Easy | 209,4 ms | 10/10 | Success
BacktrackingDotNetSolver | Medium | 859,1 ms | 10/10 | Success
BacktrackingDotNetSolver | Hard | 4995,4 ms | 0/10 | Disqualified

Interprétation : Comparaison de performance

Solveur Forces Faiblesses
HumanSolver Explicable, traçable, pédagogique ; rapide par élagage de candidats Limite aux puzzles resolubles par techniques humaines (sinon fallback backtracking)
Backtracking Simple, robuste (résout toute grille valide) Force brute, non explicable ; plus lent ici sur Easy/Medium

Contrairement a ce qu’on pourrait croire, le HumanSolver est plus rapide que ce backtracking de référence sur les puzzles Easy et Medium (cf. benchmark ci-dessus : HumanSolver quasi-instantanee contre quelques centaines de ms pour le backtracking en Easy/Medium) : l’élimination de candidats elague fortement l’arbre de recherche avant tout retour arriere. Sur les puzzles Hard les plus durs, les deux solveurs sont disqualifies (4/10, time-out), le HumanSolver restant tout de même un peu plus rapide. Son avantage majeur n’est cependant pas la vitesse mais le fait que chaque étape est explicable : on sait exactement pourquoi une valeur a été placee ou un candidat élimine.

Note : Dans les applications reelles (générateurs de puzzles, tutoriels interactifs), la capacite a tracer le raisonnement est plus importante que la vitesse brute. C’est ce qui permet de classer les puzzles par difficulté et d’aider les joueurs a progresser.

Suite — analyse statistique par difficulté : analysons plus en détail les techniques utilisees sur un ensemble de puzzles pour comprendre la distribution des techniques necessaires par niveau de difficulté.

Exercice : Mesurer le taux de résolution par stratégies humaines

Objectif : Déterminez quel pourcentage de puzzles peut être résolu uniquement par stratégies humaines (sans backtracking), par difficulté.

Indice : Utilisez HumanSolver et comptez les puzzles résolus sans atteindre le backtracking.

// EXERCICE : Mesurer le taux de resolution par strategies humaines
public Dictionary<string, double> MeasureHumanSolveRate()
{
    // TODO: Pour chaque difficulte, testez les puzzles et comptez
    // combien sont resolus uniquement par strategies humaines
    return null; // TODO etudiant
}
Console.WriteLine("Exercice a completer");
Exercice a completer
// Analyse des techniques utilisees sur un echantillon de puzzles
void AnalyzeTechniques(SudokuDifficulty difficulty, int count)
{
    var puzzles = SudokuHelper.GetSudokus(difficulty).Take(count).ToList();
    var techniqueCounts = new Dictionary<string, int>();
    int backtrackCount = 0;
    
    foreach (var puzzle in puzzles)
    {
        var solver = new HumanSolver();
        // Cree une nouvelle grille a partir des cellules pour eviter le conflit de type
        var grid = new SudokuGrid();
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                grid.Cells[i, j] = puzzle.Cells[i, j];
        solver.Solve(grid);
        
        if (solver.UsedBacktracking) backtrackCount++;
        
        foreach (var (technique, _) in solver.SolveLog)
        {
            var baseName = technique.Split('(')[0].Trim();
            if (!techniqueCounts.ContainsKey(baseName))
                techniqueCounts[baseName] = 0;
            techniqueCounts[baseName]++;
        }
    }
    
    display($"\n=== {difficulty} ({count} puzzles) ===");
    foreach (var kvp in techniqueCounts.OrderByDescending(x => x.Value))
    {
        display($"  {kvp.Key}: {kvp.Value} utilisations ({100.0 * kvp.Value / puzzles.Count:F0}% des puzzles)");
    }
    display($"  Backtracking necessaire : {backtrackCount}/{count} puzzles ({100.0 * backtrackCount / count:F0}%)");
}

AnalyzeTechniques(SudokuDifficulty.Easy, 20);
AnalyzeTechniques(SudokuDifficulty.Medium, 10);
AnalyzeTechniques(SudokuDifficulty.Hard, 10);

=== Easy (20 puzzles) ===
  Naked Singles: 38 utilisations (190% des puzzles)
  Hidden Singles: 26 utilisations (130% des puzzles)
  Naked Pairs: 3 utilisations (15% des puzzles)
  Locked Candidates - Pointing: 2 utilisations (10% des puzzles)
  Locked Candidates - Claiming: 1 utilisations (5% des puzzles)
  X-Wing: 1 utilisations (5% des puzzles)
  Backtracking necessaire : 0/20 puzzles (0%)

=== Medium (10 puzzles) ===
  Hidden Singles: 18 utilisations (180% des puzzles)
  Naked Singles: 11 utilisations (110% des puzzles)
  Backtracking: 7 utilisations (70% des puzzles)
  Locked Candidates - Pointing: 6 utilisations (60% des puzzles)
  Naked Pairs: 4 utilisations (40% des puzzles)
  Locked Candidates - Claiming: 2 utilisations (20% des puzzles)
  Backtracking necessaire : 7/10 puzzles (70%)

=== Hard (10 puzzles) ===
  Hidden Singles: 28 utilisations (280% des puzzles)
  Naked Singles: 14 utilisations (140% des puzzles)
  Locked Candidates - Pointing: 12 utilisations (120% des puzzles)
  Backtracking: 6 utilisations (60% des puzzles)
  Naked Pairs: 4 utilisations (40% des puzzles)
  Locked Candidates - Claiming: 2 utilisations (20% des puzzles)
  Backtracking necessaire : 6/10 puzzles (60%)

Interprétation : Distribution des techniques

Cette analyse révèle la signature de difficulté de chaque niveau :

  • Easy : Principalement Naked Singles et Hidden Singles. Aucun backtracking necessaire (0 %).
  • Medium : Apparition des Naked Pairs et Locked Candidates, en plus des singles. Le backtracking devient fréquent (~70 % des puzzles) faute de techniques plus avancées.
  • Hard : Usage intensif des mêmes techniques de base et intermédiaires (Hidden Singles ~280 %, Locked Candidates ~120 %, Naked Pairs ~40 % d’utilisations par puzzle). Le X-Wing n’est presque jamais déclenché (≈5 % sur Easy, 0 % sur Medium/Hard) ; le backtracking reste élevé (~60 %, du même ordre qu’en Medium) car il faudrait des techniques expertes (Swordfish, 3D Medusa) pour l’éviter.

Conclusion : Le nombre et la complexité des techniques necessaires constituent une mesure naturelle de la difficulté d’un puzzle. C’est d’ailleurs ainsi que les générateurs de puzzles classifient leurs grilles.

Exercice : Stratégies humaines avancées

Exercice 1 : Suivi détaillé des techniques

Instrumentez le solveur pour afficher, pour chaque puzzle résolu, quelles techniques ont été utilisees et combien de fois chacune a été appliquee. Comparez les statistiques entre puzzles Easy, Medium et Hard.

Exercice 2 : Implémentation du Swordfish

Implémentez la technique Swordfish en generalisant le X-Wing a 3 lignes et 3 colonnes.

Rappel : Le Swordfish est une généralisation du X-Wing : un chiffre candidat qui apparait dans exactement 2 ou 3 colonnes de chacune de 3 lignes, et toujours dans les mêmes 3 colonnes. Alors ce chiffre peut être élimine de toutes les autres cellules de ces 3 colonnes.

Code à compléter dans la cellule suivante

// Squelette pour le Swordfish
public static int ApplySwordfish(CandidateGrid cg)
{
    // TODO: Implementer le Swordfish (generalisation du X-Wing a 3 lignes/colonnes)
    return 0;
}

Console.WriteLine("Squelette ApplySwordfish defini (TODO etudiant : generalisation du X-Wing)");
Squelette ApplySwordfish defini (TODO etudiant : generalisation du X-Wing)

Exercice : Solveur Hybride avec Techniques Expertes

Objectif :

Enrichissez le solveur hybride fourni dans le notebook avec des techniques de niveau expert. Le solveur actuel s’arrête au X-Wing. Votre objectif est d’ajouter :

  1. Swordfish : Généralisation du X-Wing a 3 lignes et 3 colonnes
  2. Hidden Pairs en blocs : Adapter la technique Hidden Pairs pour les blocs 3x3 (pas seulement les lignes/colonnes)
  3. Solveur amélioré : Intégrer ces techniques dans le pipeline existant

Interface a implémenter

Code à compléter dans la cellule suivante

Critère de succès

Votre solveur doit : - Résoudre plus de puzzles “Hard” sans recourir au backtracking - Afficher les techniques utilisees et leur frequence d’application

public interface IHumanTechniqueExpert
{
    int ApplySwordfish(CandidateGrid cg);
    int ApplyHiddenPairsInBlocks(CandidateGrid cg);
}

Console.WriteLine("Interface IHumanTechniqueExpert definie (Swordfish + Hidden Pairs en blocs)");
Interface IHumanTechniqueExpert definie (Swordfish + Hidden Pairs en blocs)

Conclusion

Résumé des apprentissages

Ce notebook a présenté une approche de résolution de Sudoku basee sur les techniques humaines de déduction logique. Nous avons implémente 6 techniques (Naked Singles, Hidden Singles, Naked Pairs, Locked Candidates Pointing/Claiming, X-Wing) et les avons combinées dans un solveur hybride.

Technique implementee Type Action Difficulté cible
Naked Singles Basique Placement Easy
Hidden Singles Basique Placement Easy
Naked Pairs Intermédiaire Élimination Medium
Locked Candidates (Pointing) Intermédiaire Élimination Medium
Locked Candidates (Claiming) Intermédiaire Élimination Medium
X-Wing Avance Élimination Hard
Backtracking (fallback) Dernier recours Exploration Expert

Points clés

  1. Les techniques humaines sont hiérarchiques : on commence par les plus simples et on monte en complexité uniquement quand on est bloque
  2. Élimination vs placement : les techniques avancées eliminent des candidats, ce qui deblocke les techniques basiques
  3. La difficulté d’un puzzle se mesure par la technique la plus avancée necessaire pour le résoudre sans backtracking
  4. Le backtracking comme filet de securite : un solveur humain incomplet (sans toutes les 13 techniques) peut toujours résoudre en dernier recours via le backtracking

Perspectives

Les techniques humaines offrent un avantage majeur sur la force brute : chaque étape est explicable. Cette propriété est essentielle pour les applications pédagogiques (tutoriels interactifs) et pour la génération de puzzles de difficulté contrôlée.

Note : Le projet Sudoku.Human implémente les 13 techniques dans 23 fichiers C#, offrant une couverture complète des patterns de résolution humaine.

Voir aussi : - CSP-2-Consistance - Propagation de contraintes - Sudoku-07-Norvig - Propagation de Norvig

Retour au sommaire : Index Sudoku

// A COMPLETER : Solveur hybride avec techniques expertes

public class ExpertHumanStrategySolver : ISudokuSolver
{
    // Compteurs de techniques appliquees
    private int _swordfishCount = 0;
    private int _hiddenPairsBlockCount = 0;

    /// <summary>
    /// Applique la technique Swordfish : elimine un candidat present dans
    /// exactement 2-3 colonnes de 3 lignes, toujours dans les memes colonnes.
    /// </summary>
    public int ApplySwordfish(CandidateGrid cg)
    {
        // TODO : Implementer le Swordfish
        // Pour chaque candidat (1-9) :
        //   1. Trouver les lignes ou ce candidat apparait dans 2 ou 3 colonnes
        //   2. Chercher 3 telles lignes qui partagent exactement les memes 2-3 colonnes
        //   3. Eliminer le candidat de toutes les autres cellules de ces colonnes
        return 0;
    }

    /// <summary>
    /// Applique la technique Hidden Pairs dans les blocs 3x3.
    /// </summary>
    public int ApplyHiddenPairsInBlocks(CandidateGrid cg)
    {
        // TODO : Adapter la logique Hidden Pairs pour les 9 blocs 3x3
        // Pour chaque bloc :
        //   1. Trouver deux candidats qui n'apparaissent que dans exactement 2 cellules du bloc
        //   2. Eliminer tous les autres candidats de ces 2 cellules
        return 0;
    }

    /// <summary>
    /// Resout le Sudoku avec le pipeline complet incluant les techniques expertes.
    /// </summary>
    public SudokuGrid Solve(SudokuGrid s)
    {
        // TODO : Integrer les nouvelles techniques dans le pipeline
        // Ordre suggere :
        //   1. NakedSingles -> 2. HiddenSingles -> 3. NakedPairs ->
        //   4. LockedCandidates -> 5. XWing -> 6. Swordfish ->
        //   7. HiddenPairsInBlocks -> 8. Backtracking si necessaire
        return s;
    }
}

// Test : Comparer les performances du solveur ameliore
// string hardPuzzle = "800000000003600000070090200060005030004070010030010060020000035000900040000800006";
// var solver = new ExpertHumanStrategySolver();
// var grid = SudokuGrid.ParseGrid(hardPuzzle);
// var solved = solver.Solve(grid);
// Console.WriteLine(solved.IsSolved() ? "Resolu sans backtracking !" : "Backtracking utilise");

Console.WriteLine("Classe ExpertHumanStrategySolver definie (TODO etudiant : Swordfish + Hidden Pairs + pipeline)");
Classe ExpertHumanStrategySolver definie (TODO etudiant : Swordfish + Hidden Pairs + pipeline)
Retour au sommet