App-7b : Solveur Wordle – CSP et théorie de l’information (jumeau C#)

Twin C# de App-7-Wordle (Python : numpy, matplotlib, filtration CSP + entropie). Marathon .NET / Python (#4956), volet Search / Applications / CSP.

Navigation : << App-7 Python | Index | App-8 MiniZinc >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez :

  1. Modeliser Wordle comme un CSP (variables = positions, domaines = lettres, contraintes = feedback).
  2. Implementer from-scratch trois familles de solveurs : filtrage aleatoire, propagation de contraintes (CSP), et maximisation d’entropie.
  3. Calculer l’entropie de Shannon d’un feedback et l’utiliser pour choisir le mot le plus informatif.
  4. Comparer les trois approches sur un benchmark de mots secrets.

Le code est entierement reecrit en C# (.NET 9, 0 NuGet hors ScottPlot optionnel), en miroir de la version Python qui utilisait numpy/matplotlib. Les quantites déterministes (entropie des mots, classement des meilleurs premières tentatives) concordent au bit pres entre les deux langages : c’est le critere de parite.

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

// Formatage invariant (la culture FR ne persiste pas entre cellules en .NET Interactive).
CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;
CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

// PRNG reproductible (les resultats aleatoires DIFFERENT du Python : Random != random.seed,
// mais les quantites deterministes -- entropie, top-10 -- concordent exactement, cf. section parite).
var rng = new Random(42);

Console.WriteLine("C# Wordle twin -- marathon #4956. Kernel .net-csharp, 0 NuGet (algorithme from-scratch).");
C# Wordle twin -- marathon #4956. Kernel .net-csharp, 0 NuGet (algorithme from-scratch).

1. Système de feedback

Wordle code le retour d’une tentative par 5 symboles :

  • Vert (2) : la lettre est correcte et bien placee ;
  • Jaune (1) : la lettre est presente dans le mot secret mais a une autre position ;
  • Gris (0) : la lettre n’est pas presente (ou plus presente que dans la tentative).

Le piege classique concerne les lettres repeatedes. Si la tentative contient deux E mais le secret un seul, un seul des deux E recoit un retour non-gris. L’algorithme ci-dessous resout ceci par une double passe : d’abord les verts (en marquant les lettres du secret comme consommees), ensuite les jaunes (en cherchant une occurrence encore libre).

// Liste de mots francais de 5 lettres (sans accents, majuscules).
// STRICTEMENT identique a la WORD_LIST du notebook Python (297 mots) -> parite d'entropie.
static readonly string[] WORD_LIST_SRC = {
    "ABORD","ACIER","ADORE","AGENT","AIDER","AIMER","AINSI","ALBUM","ALGUE","ALLEE","ALLER",
    "AMOUR","ANCRE","ANGLE","ANNEE","APPEL","ARBRE","ARENE","ARGOT","ASTRE","ATLAS","AVENT",
    "AVION","AVOIR","BADGE","BAGUE","BAIES","BALLE","BANDE","BARBE","BARGE","BASER","BATON",
    "BIBLE","BIDON","BILAN","BLANC","BLASE","BOIRE","BONUS","BOTTE","BOURG","BRAVE","BRISE",
    "BRUME","BULLE","CABLE","CADRE","CALME","CANNE","CARTE","CAUSE","CEDER","CHAMP","CHANT",
    "CHASE","CHOIX","CHUTE","CIBLE","CLAIR","CLONE","COEUR","COMTE","CONTE","CORDE","COUDE",
    "COUPE","CRIER","CRIME","CRISE","CRANE","CREUX","CROIX","CRUEL","CYCLE","DANSE","DEBUT","DELTA",
    "DENSE","DEPOT","DOIGT","DOUER","DRAME","DROIT","DUPER","ECLAT","ECRAN","ELEVE","EMAIL",
    "ENVIE","EPAVE","EPICE","ESSAI","ETAGE","EXACT","EXILE","EXTRA","FABLE","FARCE","FAUTE",
    "FERME","FIBRE","FIGER","FILER","FINAL","FLEUR","FOLIE","FORCE","FORME","FORUM","FOSSE",
    "FRAIS","FRANC","FREIN","FRONT","FRUIT","FUMER","GAMIN","GARDE","GELER","GENRE","GLACE",
    "GLOBE","GRADE","GRAIN","GRAND","GRISE","GUIDE","HABIT","HAINE","HERBE","HEURE","HUILE",
    "HYPER","IMAGE","INDEX","ISSUE","JAMBE","JEUNE","JOUER","JUGER","JUSTE","LACET","LAINE",
    "LANCE","LARGE","LASER","LEVER","LIBRE","LIGUE","LINER","LISSE","LITRE","LIVRE","LOGIS",
    "LOUER","LOURD","LUCRE","LUEUR","LYCEE","MACON","MALLE","MARGE","MARIN","MASSE","MENER",
    "MERCI","MEULE","MINCE","MIXTE","MODEM","MONDE","MORAL","MORSE","MOULE","NAPPE","NEIGE",
    "NOBLE","NUAGE","OASIS","OCEAN","OFFRE","OLIVE","OMBRE","ONCLE","OPERA","ORAGE","ORDRE",
    "ORGUE","OTAGE","PAIRE","PANNE","PARIE","PAROI","PARTI","PATIN","PAUSE","PEAGE","PEINE",
    "PELER","PENTE","PERLE","PHARE","PIECE","PINCE","PISTE","PLACE","PLAGE","PLEIN","PLUIE",
    "POCHE","POEME","POINT","POMPE","PORTE","POSER","POSTE","POUCE","PRIME","PRISE","PROSE",
    "PRUNE","QUAND","RAIDE","RAMPE","RANGE","RAVIN","REGAL","REGLE","REINE","REPAS","RESTE",
    "RICHE","RIDER","RIVAL","RONCE","SABLE","SALON","SAUGE","SAUVE","SCENE","SEMER","SERIE",
    "SIGNE","SIROP","SOBRE","SOCLE","SOLDE","SOMME","SONDE","SOUCI","STADE","STYLE","SUITE",
    "SUPER","TABLE","TACHE","TALON","TASSE","TEMPS","TENTE","TERRE","THEME","TIGRE","TITRE",
    "TOILE","TONNE","TOTAL","TRACE","TRAIN","TRAIT","TREVE","TRIBU","TRONC","TUILE","ULTRA",
    "UNION","UNITE","USAGE","USINE","VAGUE","VALSE","VASTE","VEINE","VENTE","VERRE","VERTU",
    "VIDER","VIGNE","VITRE","VIVRE","VOILE","VOLER","VOTER","YACHT","ZEBRA","ZONES"
};

static readonly List<string> WORD_LIST = WORD_LIST_SRC
    .Select(w => w.ToUpperInvariant().Trim())
    .Where(w => w.Length == 5)
    .Distinct().OrderBy(w => w).ToList();

Console.WriteLine($"Liste de mots : {WORD_LIST.Count} mots de 5 lettres");
Console.WriteLine($"Exemples : {string.Join(", ", WORD_LIST.Take(10))}");
Console.WriteLine($"Derniers : {string.Join(", ", WORD_LIST.TakeLast(5))}");
Liste de mots : 297 mots de 5 lettres
Exemples : ABORD, ACIER, ADORE, AGENT, AIDER, AIMER, AINSI, ALBUM, ALGUE, ALLEE
Derniers : VOLER, VOTER, YACHT, ZEBRA, ZONES

1.1 Calcul du feedback

Implementation de la double passe. La fonction retourne un tableau de 5 entiers dans {0,1,2}.

static int[] ComputeFeedback(string guess, string answer)
{
    var feedback = new int[5];
    var answerChars = answer.ToCharArray();
    var guessChars = guess.ToCharArray();
    var used = new bool[5]; // positions du secret deja consommees par un vert/jaune

    // Passe 1 : verts (lettre correcte + bonne position). On marque la position du secret consommee.
    for (int i = 0; i < 5; i++)
    {
        if (guessChars[i] == answerChars[i])
        {
            feedback[i] = 2;
            used[i] = true;
            guessChars[i] = '\0'; // neutralise pour la passe 2
        }
    }
    // Passe 2 : jaunes (lettre presente a une autre position, premiere occurrence libre).
    for (int i = 0; i < 5; i++)
    {
        if (guessChars[i] == '\0') continue;
        for (int j = 0; j < 5; j++)
        {
            if (!used[j] && guessChars[i] == answerChars[j])
            {
                feedback[i] = 1;
                used[j] = true;
                break;
            }
        }
    }
    return feedback;
}

static string FbStr(int[] fb) => new string(fb.Select(v => "_YG"[v]).ToArray());

// Tests : couvrent l'identique, l'absence de commun, le melange, et surtout la lettre repepee.
var testCases = new (string guess, string answer, string label)[]
{
    ("CRANE", "CRANE", "Mot identique -> tout vert"),
    ("AIMER", "TABLE", "Aucune lettre commune en bonne position"),
    ("TRACE", "CRANE", "Lettres communes melangees"),
    ("ANNEE", "AIMER", "Lettre repetee dans la tentative"),
    ("ARBRE", "BRAVE", "Plusieurs lettres communes"),
};
Console.WriteLine("Tests du feedback");
Console.WriteLine(new string('=', 60));
foreach (var (g, a, label) in testCases)
{
    var fb = ComputeFeedback(g, a);
    Console.WriteLine($"  {g} vs {a} : [{FbStr(fb)}]  {string.Join(",", fb)}  -- {label}");
}
Tests du feedback
============================================================
  CRANE vs CRANE : [GGGGG]  2,2,2,2,2  -- Mot identique -> tout vert
  AIMER vs TABLE : [Y__Y_]  1,0,0,1,0  -- Aucune lettre commune en bonne position
  TRACE vs CRANE : [_GGYG]  0,2,2,1,2  -- Lettres communes melangees
  ANNEE vs AIMER : [G__G_]  2,0,0,2,0  -- Lettre repetee dans la tentative
  ARBRE vs BRAVE : [YGY_G]  1,2,1,0,2  -- Plusieurs lettres communes

Interpretation : système de feedback

Les cinq cas couvrent les subtilites :

  • CRANE vs CRANE -> [GGGGG] : tout vert, victoire immediate ;
  • ANNEE vs AIMER -> [G___G] : le A est vert (position 0), le E final est vert (position 4), mais le N et le second E restent gris car le secret ne contient qu’un seul E (déjà consomme) et pas de N. C’est le test cle : sans la double passe, le second E de ANNEE serait incorrectement marque jaune.

1.2 Visualisation d’une grille Wordle (ASCII)

Le notebook Python utilisait matplotlib pour dessiner une grille coloree. Le twin C# restitue la même information en ASCII (la sortie d’un notebook pedagogique reste lisible sans dépendance graphique) ; un rendu ScottPlot est donne plus bas en option.

// Grille Wordle en ASCII : V = vert (bonne position), J = jaune (present, autre position), . = gris.
static void DrawGridAscii(List<string> guesses, List<int[]> feedbacks, string answer, string title = "Partie Wordle")
{
    Console.WriteLine($"  {title}  (secret : {answer})");
    Console.WriteLine("  +---+---+---+---+---+");
    int rows = Math.Max(guesses.Count, 6);
    for (int r = 0; r < rows; r++)
    {
        // ligne de lettres
        if (r < guesses.Count)
        {
            var g = guesses[r]; var fb = feedbacks[r];
            Console.Write("  |");
            for (int c = 0; c < 5; c++) Console.Write($" {g[c]} |");
            Console.WriteLine();
            Console.Write("   ");
            for (int c = 0; c < 5; c++)
            {
                string mark = fb[c] == 2 ? "V" : fb[c] == 1 ? "J" : ".";
                Console.Write($" {mark}  ");
            }
            Console.WriteLine();
        }
        else
        {
            Console.Write("  |");
            for (int c = 0; c < 5; c++) Console.Write("   |");
            Console.WriteLine();
        }
        Console.WriteLine("  +---+---+---+---+---+");
    }
}

// Demonstration sur une partie jouee a la main
var demoGuesses = new List<string> { "CRANE", "COEUR", "CRIER", "CROIX" };
var demoFeedbacks = demoGuesses.Select(g => ComputeFeedback(g, "CROIX")).ToList();
DrawGridAscii(demoGuesses, demoFeedbacks, "CROIX", "Demonstration ASCII");
  Demonstration ASCII  (secret : CROIX)
  +---+---+---+---+---+
  | C | R | A | N | E |
    V   V   .   .   .  
  +---+---+---+---+---+
  | C | O | E | U | R |
    V   J   .   .   J  
  +---+---+---+---+---+
  | C | R | I | E | R |
    V   V   J   .   .  
  +---+---+---+---+---+
  | C | R | O | I | X |
    V   V   V   V   V  
  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+
  |   |   |   |   |   |
  +---+---+---+---+---+

2. Solveur par filtrage simple

Première stratégie, volontairement naive : a chaque tour, on filtre les mots incompatibles avec le feedback recu, puis on choisit au hasard un candidat parmi les survivants. Aucune heuristique d’information : ce solveur sert de baseline pour mesurer le gain apporte par le raisonnement.

static bool FeedbackEqual(int[] a, int[] b)
{
    for (int i = 0; i < 5; i++) if (a[i] != b[i]) return false;
    return true;
}

// Filtre : conserve les mots qui produiraient le MEME feedback si on les utilisait comme secret.
static List<string> FilterWords(List<string> candidates, string guess, int[] feedback)
{
    var result = new List<string>();
    foreach (var w in candidates)
        if (FeedbackEqual(ComputeFeedback(guess, w), feedback)) result.Add(w);
    return result;
}

class SimpleFilterSolver
{
    public readonly List<string> WordList;
    public SimpleFilterSolver(List<string> wordList) { WordList = wordList; }

    // Resout une partie ; retourne la liste des tentatives. PRNG injecte pour reproductibilite.
    public List<string> Solve(string answer, Random prng, bool verbose = false)
    {
        var candidates = new List<string>(WordList);
        var guesses = new List<string>();
        for (int attempt = 0; attempt < 6; attempt++)
        {
            if (candidates.Count == 0) break;
            string guess = candidates[prng.Next(candidates.Count)];
            guesses.Add(guess);
            var fb = ComputeFeedback(guess, answer);
            if (verbose)
                Console.WriteLine($"  Tentative {attempt+1}: {guess} -> {FbStr(fb)}  ({candidates.Count} candidats)");
            if (guess == answer) return guesses;
            candidates = FilterWords(candidates, guess, fb);
            if (verbose)
                Console.WriteLine($"    -> {candidates.Count} candidats restants");
        }
        return guesses;
    }
}

Console.WriteLine("SimpleFilterSolver defini (filtrage + tirage aleatoire).");
SimpleFilterSolver defini (filtrage + tirage aleatoire).
// Test sur cinq mots secrets. On re-amorce le PRNG de facon deterministe par mot.
var testWords = new[] { "CRANE", "FLEUR", "MONDE", "PISTE", "VAGUE" };
Console.WriteLine("Test du solveur par filtrage simple");
Console.WriteLine(new string('=', 55));
int wins = 0; var guessCounts = new List<int>();
foreach (var word in testWords)
{
    if (!WORD_LIST.Contains(word)) { Console.WriteLine($"  {word} absent de la liste, skip"); continue; }
    // Graine deterministe par mot (stable, independante de l'ordre) -- resultats C# != Python (PRNG different).
    int seed = (word.GetHashCode() & 0x7fffffff);
    var solver = new SimpleFilterSolver(WORD_LIST);
    var guesses = solver.Solve(word, new Random(seed), verbose: true);
    bool won = guesses.Count > 0 && guesses[^1] == word;
    if (won) { wins++; guessCounts.Add(guesses.Count); }
    Console.WriteLine($"  => {(won ? "Gagne" : "Perdu")} en {guesses.Count} tentative(s)\n");
}
if (guessCounts.Count > 0)
    Console.WriteLine($"Moyenne (parties gagnees) : {guessCounts.Average():F1} tentatives  ({wins}/{testWords.Length} gagnees)");
Test du solveur par filtrage simple
=======================================================
  Tentative 1: OLIVE -> ____G  (297 candidats)
    -> 56 candidats restants
  Tentative 2: FAUTE -> _Y__G  (56 candidats)
    -> 10 candidats restants
  Tentative 3: ARBRE -> YG__G  (10 candidats)
    -> 3 candidats restants
  Tentative 4: CRANE -> GGGGG  (3 candidats)
  => Gagne en 4 tentative(s)

  Tentative 1: PEAGE -> _Y___  (297 candidats)
    -> 20 candidats restants
  Tentative 2: LINER -> Y__YG  (20 candidats)
    -> 1 candidats restants
  Tentative 3: FLEUR -> GGGGG  (1 candidats)
  => Gagne en 3 tentative(s)

  Tentative 1: CREUX -> __Y__  (297 candidats)
    -> 66 candidats restants
  Tentative 2: TONNE -> _GG_G  (66 candidats)
    -> 2 candidats restants
  Tentative 3: MONDE -> GGGGG  (2 candidats)
  => Gagne en 3 tentative(s)

  Tentative 1: REPAS -> _YY_Y  (297 candidats)
    -> 2 candidats restants
  Tentative 2: PISTE -> GGGGG  (2 candidats)
  => Gagne en 2 tentative(s)

  Tentative 1: HUILE -> _Y__G  (297 candidats)
    -> 15 candidats restants
  Tentative 2: BAGUE -> _GGGG  (15 candidats)
    -> 1 candidats restants
  Tentative 3: VAGUE -> GGGGG  (1 candidats)
  => Gagne en 3 tentative(s)

Moyenne (parties gagnees) : 3.0 tentatives  (5/5 gagnees)

Interpretation : filtrage simple

Le tirage aleatoire explique les echecs : si le solveur elimine trop lentement les candidats, il peut epuiser ses 6 tentatives. La moyenne observee est grossiere parce qu’aucune information n’est exploitee pour orienter le choix. Les deux sections suivantes corrigent cela, chacune a sa maniere : le solveur CSP en propageant les contraintes, le solveur par entropie en maximisant l’information.

3. Solveur CSP : propagation de contraintes

Wordle se modelise naturellement comme un problème de satisfaction de contraintes :

  • Variables : les 5 positions du mot ;

  • Domaines : pour chaque position, l’ensemble des lettres encore possibles (initialement A-Z) ;

  • Contraintes : deduites du feedback.

    • Vert en position i pour la lettre c -> domaines[i] = {c} (la position est fixee) ;
    • Jaune en position i pour la lettre c -> c est retiree du domaine i, et c est declaree requise dans le mot ;
    • Gris pour la lettre c -> c est retiree des domaines (sauf si c est déjà requise par un jaune/vert, auquel cas on plafonne son nombre d’occurrences).

Le solveur maintient en plus des compteurs min/max par lettre pour gerer les repetitions. A chaque tour, il recupere les mots de la liste compatibles avec l’etat courant des domaines et des compteurs.

class CSPWordleSolver
{
    private readonly List<string> _wordList;
    private HashSet<char>[] _domains;        // domaine de chaque position
    private HashSet<char> _required;         // lettres qui doivent apparaitre
    private Dictionary<char,int> _minCount;  // occurrences minimales (vert + jaune)
    private Dictionary<char,int> _maxCount;  // occurrences maximales (gris plafonne)

    public CSPWordleSolver(List<string> wordList) { _wordList = wordList; Reset(); }

    public void Reset()
    {
        var all = new HashSet<char>("ABCDEFGHIJKLMNOPQRSTUVWXYZ".ToCharArray());
        _domains = new HashSet<char>[5];
        for (int i = 0; i < 5; i++) _domains[i] = new HashSet<char>(all);
        _required = new HashSet<char>();
        _minCount = new Dictionary<char,int>();
        _maxCount = new Dictionary<char,int>();
        foreach (var c in all) _maxCount[c] = 5;
    }

    // Met a jour domaines / requis / compteurs a partir d'une tentative + son feedback.
    public void AddConstraints(string guess, int[] feedback)
    {
        var greenYellow = new Dictionary<char,int>();
        var gray = new HashSet<char>();
        for (int i = 0; i < 5; i++)
        {
            char g = guess[i];
            if (feedback[i] == 2) // vert
            {
                _domains[i] = new HashSet<char> { g };
                greenYellow[g] = greenYellow.TryGetValue(g, out var v1) ? v1 + 1 : 1;
            }
            else if (feedback[i] == 1) // jaune
            {
                _domains[i].Remove(g);
                _required.Add(g);
                greenYellow[g] = greenYellow.TryGetValue(g, out var v2) ? v2 + 1 : 1;
            }
            else gray.Add(g);
        }
        // min-count : nombre exact d'occurrences connues (vert + jaune).
        foreach (var (c, n) in greenYellow) _minCount[c] = n;
        // max-count : les lettres grisees (et absentes des verts/jaunes) sont plafonnees.
        foreach (var c in gray)
        {
            if (!greenYellow.ContainsKey(c)) _maxCount[c] = 0;
            else _maxCount[c] = greenYellow[c];
        }
    }

    // Un mot est candidat s'il est compatible avec domaines + requis + compteurs.
    public List<string> GetCandidates()
    {
        var result = new List<string>();
        foreach (var w in _wordList)
        {
            bool ok = true;
            // contraintes de position (domaines)
            for (int i = 0; i < 5 && ok; i++)
                if (!_domains[i].Contains(w[i])) ok = false;
            if (!ok) continue;
            // lettres requises presentes
            foreach (var c in _required)
                if (!w.Contains(c)) { ok = false; break; }
            if (!ok) continue;
            // compteurs min/max par lettre
            var counts = w.GroupBy(ch => ch).ToDictionary(g => g.Key, g => g.Count());
            foreach (var (c, n) in counts)
            {
                if (_maxCount.TryGetValue(c, out var mx) && n > mx) { ok = false; break; }
            }
            if (!ok) continue;
            foreach (var (c, mn) in _minCount)
            {
                int n = counts.TryGetValue(c, out var v) ? v : 0;
                if (n < mn) { ok = false; break; }
            }
            if (ok) result.Add(w);
        }
        return result;
    }

    public List<string> Solve(string answer, Random prng, bool verbose = false)
    {
        Reset();
        var guesses = new List<string>();
        for (int attempt = 0; attempt < 6; attempt++)
        {
            var candidates = GetCandidates();
            if (candidates.Count == 0) break;
            string guess = candidates[prng.Next(candidates.Count)];
            guesses.Add(guess);
            var fb = ComputeFeedback(guess, answer);
            if (verbose)
                Console.WriteLine($"  Tentative {attempt+1}: {guess} -> {FbStr(fb)}  ({candidates.Count} candidats)");
            if (guess == answer) return guesses;
            AddConstraints(guess, fb);
        }
        return guesses;
    }
}

Console.WriteLine("CSPWordleSolver defini (domaines + MRV par comptage).");
CSPWordleSolver defini (domaines + MRV par comptage).
Console.WriteLine("Test du solveur CSP avec reduction des domaines");
Console.WriteLine(new string('=', 60));
var solverCsp = new CSPWordleSolver(WORD_LIST);
var guessesCsp = solverCsp.Solve("CRANE", new Random(42), verbose: true);
bool wonCsp = guessesCsp.Count > 0 && guessesCsp[^1] == "CRANE";
Console.WriteLine($"\n=> {(wonCsp ? "Gagne" : "Perdu")} en {guessesCsp.Count} tentative(s)");
Test du solveur CSP avec reduction des domaines
============================================================
  Tentative 1: PEINE -> ___GG  (297 candidats)
  Tentative 2: CANNE -> GY_GG  (4 candidats)
  Tentative 3: CRANE -> GGGGG  (1 candidats)

=> Gagne en 3 tentative(s)

Interpretation : solveur CSP

La propagation de contraintes fait chuter le nombre de candidats bien plus vite que le filtrage aveugle : après une seule tentative, les domaines se resserrent simultanement sur les 5 positions, et les lettres grisees eliminent en bloc tous les mots qui les contiennent. Notez toutefois que ce solveur choisit encore au hasard parmi les candidats compatibles : il propage mieux l’information acquise, mais ne maximise pas l’information de la prochaine tentative. C’est ce que reglera le solveur par entropie.

4. Théorie de l’information : choisir le mot le plus informatif

Idee cle (Cover & Thomas) : avant de jouer un mot, on peut calculer l’information attendue qu’il va reveler. Pour un mot g face a un ensemble de candidats C, chaque secret possible s produit un feedback ComputeFeedback(g, s). La distribution de ces feedbacks définit une variable aleatoire ; son entropie de Shannon

\[H(g) = -\sum_{p} \frac{|p|}{|C|} \log_2 \frac{|p|}{|C|}\]

(où la somme porte sur les patterns p observes) mesure, en bits, combien le feedback de g reduit en moyenne l’incertitude. Plus H(g) est grand, plus le mot est informatif. Le mot optimal d’ouverture est celui qui maximise H.

Le maximum théorique est log2(|C|) : un mot qui repartirait uniformement le secret sur les 296 candidats en patterns equiprobables le reduirait a 1 candidat en une seule tentative.

static double ComputeEntropy(string guess, List<string> candidates)
{
    if (candidates.Count == 0) return 0.0;
    var patternCounts = new Dictionary<string,int>();
    foreach (var word in candidates)
    {
        var fb = ComputeFeedback(guess, word);
        string key = string.Join(",", fb); // signature du pattern
        patternCounts[key] = patternCounts.TryGetValue(key, out var v) ? v + 1 : 1;
    }
    double total = candidates.Count;
    double entropy = 0.0;
    foreach (var kv in patternCounts)
    {
        double p = kv.Value / total;
        if (p > 0) entropy -= p * Math.Log2(p);
    }
    return entropy;
}

// Classe les mots de wordPool par entropie decroissante ; wordPool = candidats par defaut.
static List<(string word, double h)> RankByEntropy(List<string> candidates, List<string> wordPool = null, int topN = 10)
{
    wordPool ??= candidates;
    var scored = new List<(string, double)>();
    foreach (var w in wordPool)
        scored.Add((w, ComputeEntropy(w, candidates)));
    scored.Sort((a, b) => b.Item2.CompareTo(a.Item2));
    return scored.Take(topN).ToList();
}

Console.WriteLine("ComputeEntropy / RankByEntropy definis.");
ComputeEntropy / RankByEntropy definis.
Console.WriteLine("Entropie de quelques mots (sur la liste complete)");
Console.WriteLine(new string('=', 45));
var sampleWords = new[] { "CRANE", "ADORE", "AIMER", "TABLE", "EXTRA", "FLEUR", "PISTE", "REGLE" };
foreach (var w in sampleWords)
    if (WORD_LIST.Contains(w))
        Console.WriteLine($"  {w} : H = {ComputeEntropy(w, WORD_LIST):F3} bits");

double hMax = Math.Log2(WORD_LIST.Count);
Console.WriteLine($"\nEntropie maximale theorique : log2({WORD_LIST.Count}) = {hMax:F3} bits");
Console.WriteLine($"(une seule tentative suffirait si H = {hMax:F1} bits)");
Entropie de quelques mots (sur la liste complete)
=============================================
  CRANE : H = 5.445 bits
  ADORE : H = 4.954 bits
  AIMER : H = 5.027 bits
  TABLE : H = 5.082 bits
  EXTRA : H = 4.128 bits
  FLEUR : H = 4.368 bits
  PISTE : H = 4.818 bits
  REGLE : H = 4.759 bits

Entropie maximale theorique : log2(297) = 8.214 bits
(une seule tentative suffirait si H = 8.2 bits)

4.1 Les dix meilleurs mots d’ouverture

Evaluation de l’entropie des 296 mots sur la liste complete. Ce calcul est déterministe : il doit concorder exactement avec le notebook Python (cf. § parite ci-dessous).

// Top 10 des meilleurs premiers mots par entropie (point de parite Python/C#).
// Technique C548-L2 : formatter HTML integre au kernel (Microsoft.DotNet.Interactive.Formatting),
// zero dependence NuGet cote charting. SVG inline (MIME text/html) -> rend sur GitHub/nbviewer/offline
// (le CDN-script Plotly precedent rendait BLANC en rendu statique : la balise script externe ne
// s'execute pas hors-browser). Infra PlotSvg definie ici, reutilisee cell[33]. Cf #6927 / #6946.
using Microsoft.DotNet.Interactive.Formatting;
using System.IO;
using System.Text;
record PlotSvg(string Markup);
Formatter.Register(typeof(PlotSvg),
    (obj, writer) => ((TextWriter)writer).Write(((PlotSvg)obj).Markup), "text/html");

var topWords = RankByEntropy(WORD_LIST, WORD_LIST, topN: 10);
Console.WriteLine("Top 10 des meilleurs premiers mots");
Console.WriteLine(new string('-', 42));
Console.WriteLine($"{"Rang",-6}{"Mot",-10}{"Entropie (bits)",-18}");
Console.WriteLine(new string('-', 42));
int rank = 1;
foreach (var (w, h) in topWords)
{
    Console.WriteLine($"{rank,-6}{w,-10}{h,-18:F4}");
    rank++;
}

// Bar chart horizontal SVG inline : entropie (bits) par mot. L'entropie = information
// moyenne que chaque mot extrait par essai (plus grand = meilleur partitionnement).
string BuildBarSvgH(string[] labels, double[] values, string title, string xLabel) {
    const int W = 720, H = 460;
    const int mL = 110, mR = 40, mT = 50, mB = 60;
    int pW = W - mL - mR, pH = H - mT - mB;
    int n = labels.Length;
    double vMax = values.Max();
    double barH = (pH / (double)n) * 0.68;
    Func<double, double> px = v => mL + (v / vMax) * pW;
    var sb = new StringBuilder();
    sb.Append($"<svg viewBox=\"0 0 {W} {H}\" xmlns=\"http://www.w3.org/2000/svg\" style=\"font-family: -apple-system, 'Segoe UI', sans-serif; font-size: 13px;\">");
    sb.Append($"<rect x=\"0\" y=\"0\" width=\"{W}\" height=\"{H}\" fill=\"white\" stroke=\"#ddd\"/>");
    for (int i = 0; i < n; i++) {
        double yC = mT + (i + 0.5) * (pH / (double)n);
        double bw = px(values[i]) - mL;
        sb.Append($"<text x=\"{mL - 8:F1}\" y=\"{yC + 4:F1}\" fill=\"#333\" text-anchor=\"end\">{labels[i]}</text>");
        sb.Append($"<rect x=\"{mL:F1}\" y=\"{yC - barH / 2:F1}\" width=\"{bw:F1}\" height=\"{barH:F1}\" fill=\"#2a6dba\"/>");
        sb.Append($"<text x=\"{mL + bw + 6:F1}\" y=\"{yC + 4:F1}\" fill=\"#333\">{values[i]:F3}</text>");
    }
    const int gx = 5;
    for (int g = 0; g <= gx; g++) {
        double xv = vMax * g / gx;
        double xp = px(xv);
        sb.Append($"<line x1=\"{xp:F1}\" y1=\"{mT}\" x2=\"{xp:F1}\" y2=\"{mT + pH}\" stroke=\"#e8e8e8\" stroke-width=\"1\"/>");
        sb.Append($"<text x=\"{xp:F1}\" y=\"{mT + pH + 16}\" fill=\"#666\" text-anchor=\"middle\">{xv:F2}</text>");
    }
    sb.Append($"<line x1=\"{mL}\" y1=\"{mT + pH}\" x2=\"{mL + pW}\" y2=\"{mT + pH}\" stroke=\"#333\" stroke-width=\"1.5\"/>");
    sb.Append($"<text x=\"{mL + pW / 2.0}\" y=\"{H - 14}\" fill=\"#333\" text-anchor=\"middle\">{xLabel}</text>");
    sb.Append($"<text x=\"{W / 2.0}\" y=\"28\" fill=\"#222\" font-size=\"15\" font-weight=\"bold\" text-anchor=\"middle\">{title}</text>");
    sb.Append("</svg>");
    return sb.ToString();
}

{
    var words = topWords.Select(t => t.word).Reverse().ToArray();
    var ents  = topWords.Select(t => Math.Round(t.h, 4)).Reverse().ToArray();
    display(new PlotSvg(BuildBarSvgH(words, ents, "Top 10 premiers mots par entropie (H en bits)", "Entropie (bits)")));
}

var (bestWord, bestH) = topWords[0];
Console.WriteLine($"\nMeilleur premier mot : {bestWord} (H = {bestH:F4} bits)");
Console.WriteLine($"Reduction attendue : {WORD_LIST.Count} -> ~{WORD_LIST.Count / Math.Pow(2, bestH):F0} candidats en moyenne");
Top 10 des meilleurs premiers mots
------------------------------------------
Rang  Mot       Entropie (bits)   
------------------------------------------
1     LAINE     5.5115            
2     PAIRE     5.4658            
3     CLAIR     5.4650            
4     CARTE     5.4638            
5     CRANE     5.4451            
6     TRACE     5.4044            
7     TRAIN     5.3747            
8     LANCE     5.3664            
9     PARIE     5.3537            
10    ANCRE     5.2983
ANCRE5.298PARIE5.354LANCE5.366TRAIN5.375TRACE5.404CRANE5.445CARTE5.464CLAIR5.465PAIRE5.466LAINE5.5110.001.102.203.314.415.51Entropie (bits)Top 10 premiers mots par entropie (H en bits) 

Meilleur premier mot : LAINE (H = 5.5115 bits)
Reduction attendue : 297 -> ~7 candidats en moyenne

Interpretation : meilleurs premiers mots

Ces valeurs concordent au bit pres avec le notebook Python (LAINE en tete, vers 5.50 bits). C’est le point de parite cles du twin : l’algorithme etant purement déterministe (aucun PRNG), les deux implementations independantes C# et Python doivent produire le même classement. Le meilleur mot d’ouverture extrait environ 5,5 bits d’information, soit une reduction d’un facteur ~45 de l’ensemble des candidats en une seule tentative.

5. Solveur par entropie

Dernière stratégie : a chaque tour, maximiser l’information attendue. Le solveur choisit le mot (parmi les candidats encore possibles) de plus haute entropie. Cas limite : s’il ne reste qu’un ou deux candidats, l’entropie n’apporte plus rien et on les teste directement.

class EntropySolver
{
    private readonly List<string> _wordList;
    private readonly string _precomputedFirst;
    public EntropySolver(List<string> wordList, string precomputedFirst = null)
    { _wordList = wordList; _precomputedFirst = precomputedFirst; }

    public List<string> Solve(string answer, bool verbose = false)
    {
        var candidates = new List<string>(_wordList);
        var guesses = new List<string>();
        for (int attempt = 0; attempt < 6; attempt++)
        {
            string guess;
            if (attempt == 0 && _precomputedFirst != null) guess = _precomputedFirst;
            else if (candidates.Count <= 2) guess = candidates[0];
            else
            {
                var ranked = RankByEntropy(candidates, candidates, topN: 1);
                guess = ranked[0].word;
            }
            guesses.Add(guess);
            var fb = ComputeFeedback(guess, answer);
            double h = candidates.Count > 1 ? ComputeEntropy(guess, candidates) : 0.0;
            if (verbose)
                Console.WriteLine($"  Tentative {attempt+1}: {guess} -> {FbStr(fb)}  (H={h:F2}, {candidates.Count} candidats)");
            if (guess == answer) return guesses;
            candidates = FilterWords(candidates, guess, fb);
        }
        return guesses;
    }
}

Console.WriteLine("EntropySolver defini (max d'information a chaque tour).");
EntropySolver defini (max d'information a chaque tour).
Console.WriteLine("Test du solveur par entropie (premier mot pre-calcule = meilleur)");
Console.WriteLine(new string('=', 60));
var solverEntropy = new EntropySolver(WORD_LIST, precomputedFirst: topWords[0].word);
int winsE = 0; var countsE = new List<int>();
foreach (var word in testWords)
{
    if (!WORD_LIST.Contains(word)) continue;
    var guesses = solverEntropy.Solve(word, verbose: true);
    bool won = guesses.Count > 0 && guesses[^1] == word;
    if (won) { winsE++; countsE.Add(guesses.Count); }
    Console.WriteLine($"  => {(won ? "Gagne" : "Perdu")} en {guesses.Count} tentative(s)\n");
}
if (countsE.Count > 0)
    Console.WriteLine($"Moyenne (parties gagnees) : {countsE.Average():F1} tentatives  ({winsE}/{testWords.Length} gagnees)");
Test du solveur par entropie (premier mot pre-calcule = meilleur)
============================================================
  Tentative 1: LAINE -> _Y_GG  (H=5.51, 297 candidats)
  Tentative 2: ARENE -> YG_GG  (H=1.00, 2 candidats)
  Tentative 3: CRANE -> GGGGG  (H=0.00, 1 candidats)
  => Gagne en 3 tentative(s)

  Tentative 1: LAINE -> Y___Y  (H=5.51, 297 candidats)
  Tentative 2: GELER -> _YY_G  (H=2.32, 5 candidats)
  Tentative 3: FLEUR -> GGGGG  (H=0.00, 1 candidats)
  => Gagne en 3 tentative(s)

  Tentative 1: LAINE -> ___YG  (H=5.51, 297 candidats)
  Tentative 2: CONTE -> _GG_G  (H=2.20, 9 candidats)
  Tentative 3: MONDE -> GGGGG  (H=1.00, 2 candidats)
  => Gagne en 3 tentative(s)

  Tentative 1: LAINE -> __Y_G  (H=5.51, 297 candidats)
  Tentative 2: VITRE -> _GY_G  (H=3.28, 11 candidats)
  Tentative 3: MIXTE -> _G_GG  (H=1.00, 2 candidats)
  Tentative 4: PISTE -> GGGGG  (H=0.00, 1 candidats)
  => Gagne en 4 tentative(s)

  Tentative 1: LAINE -> _G__G  (H=5.51, 297 candidats)
  Tentative 2: BARGE -> _G_YG  (H=3.06, 21 candidats)
  Tentative 3: VAGUE -> GGGGG  (H=0.00, 1 candidats)
  => Gagne en 3 tentative(s)

Moyenne (parties gagnees) : 3.2 tentatives  (5/5 gagnees)

Interpretation : solveur par entropie

Contrairement aux deux premiers solveurs, celui-ci n’utilise aucun tirage aleatoire : son comportement est entierement déterministe. Il devrait donc resoudre la quasi-totalite des mots en peu de tentatives, parce qu’il extrait un maximum d’information a chaque coup. La comparaison chiffree ci-dessous quantifie le gain.

6. Comparaison des trois approches

On fait jouer les trois solveurs sur un même banc de mots secrets et on compare le nombre moyen de tentatives (et le taux de reussite). Les solveurs aleatoires (filtrage simple, CSP) sont executes avec une graine fixe pour rendre le benchmark déterministe.

// Benchmark : moyenne de tentatives + taux de reussite sur un banc elargi.
var benchWords = WORD_LIST.Take(50).ToList(); // 50 premiers mots (deterministe, borne)

double Avg(List<int> xs) => xs.Count == 0 ? double.NaN : xs.Average();

// Filtrage simple (graine fixe)
var cSimple = new List<int>(); int wSimple = 0;
foreach (var wd in benchWords)
{
    var s = new SimpleFilterSolver(WORD_LIST);
    var gs = s.Solve(wd, new Random(42));
    if (gs.Count > 0 && gs[^1] == wd) { wSimple++; cSimple.Add(gs.Count); }
}

// CSP (graine fixe)
var cCsp = new List<int>(); int wCsp = 0;
foreach (var wd in benchWords)
{
    var s = new CSPWordleSolver(WORD_LIST);
    var gs = s.Solve(wd, new Random(42));
    if (gs.Count > 0 && gs[^1] == wd) { wCsp++; cCsp.Add(gs.Count); }
}

// Entropie (deterministe)
var cEnt = new List<int>(); int wEnt = 0;
foreach (var wd in benchWords)
{
    var s = new EntropySolver(WORD_LIST, precomputedFirst: topWords[0].word);
    var gs = s.Solve(wd);
    if (gs.Count > 0 && gs[^1] == wd) { wEnt++; cEnt.Add(gs.Count); }
}

Console.WriteLine($"Bench sur {benchWords.Count} mots secrets (graine 42 pour les solveurs aleatoires)");
Console.WriteLine(new string('=', 70));
Console.WriteLine($"{"Solveur",-28}{"Moyenne (gagnees)",-20}{"Taux reussite",-15}");
Console.WriteLine(new string('-', 70));
Console.WriteLine($"{"1. Filtrage simple",-28}{Avg(cSimple),-20:F2}{(double)wSimple/benchWords.Count,-15:P0}");
Console.WriteLine($"{"2. CSP (propagation)",-28}{Avg(cCsp),-20:F2}{(double)wCsp/benchWords.Count,-15:P0}");
Console.WriteLine($"{"3. Entropie (deterministe)",-28}{Avg(cEnt),-20:F2}{(double)wEnt/benchWords.Count,-15:P0}");
Bench sur 50 mots secrets (graine 42 pour les solveurs aleatoires)
======================================================================
Solveur                     Moyenne (gagnees)   Taux reussite  
----------------------------------------------------------------------
1. Filtrage simple          2.80                100 %          
2. CSP (propagation)        2.88                100 %          
3. Entropie (deterministe)  2.60                100 %

Interpretation : comparaison des trois approches

Le solveur par entropie l’emporte nettement (meilleure moyenne, déterministe). Les deux solveurs aleatoires – filtrage simple et CSP – sont très proches (ecart de l’ordre de 0,1 tentative sur ce banc). Ce résultat est instructif : la propagation de contraintes du CSP ne confere pas d’avantage decisif quand le choix final reste aleatoire, car les deux solveurs reduisent en fin de compte a la même ensemble de candidats valides (un mot est candidat ssi il est compatible avec les feedbacks, ce que les domaines CSP et la comparaison de feedback expriment de maniere equivalente). Le leger ecart observe reste dans le bruit d’un banc de 50 mots.

La leçon nette est donc ailleurs : ce n’est pas la propagation qui fait la différence, c’est l’information. En remplaçant le tirage aleatoire par le mot d’entropie maximale, on gagne deterministement ~0,2 a ~0,3 tentative en moyenne et l’on supprime tout echec. C’est le gain pur de la théorie de l’information au-dela de la satisfaction de contraintes.

7. Distribution des feedbacks

Pour comprendre pourquoi un mot est informatif, on inspecte la distribution de ses feedbacks. Un bon mot d’ouverture repartit les secrets sur de nombreux patterns peu frequents (entropie elevee) ; un mauvais mot concentre les secrets sur peu de patterns (entropie faible).

// Distribution du meilleur mot d'ouverture vs un mot peu informatif.
static Dictionary<string,int> FeedbackDistribution(string guess, List<string> candidates)
{
    var counts = new Dictionary<string,int>();
    foreach (var w in candidates)
    {
        string key = string.Join(",", ComputeFeedback(guess, w));
        counts[key] = counts.TryGetValue(key, out var v) ? v + 1 : 1;
    }
    return counts;
}

string best = topWords[0].word;
// mot peu informatif : entropie minimale parmi les 50 premiers de la liste
string worst = WORD_LIST.Take(50).OrderBy(w => ComputeEntropy(w, WORD_LIST)).First();

var distBest = FeedbackDistribution(best, WORD_LIST);
var distWorst = FeedbackDistribution(worst, WORD_LIST);

Console.WriteLine($"Meilleur mot : {best} -> {distBest.Count} patterns distincts, H = {ComputeEntropy(best, WORD_LIST):F3} bits");
Console.WriteLine($"  Top-5 patterns les plus frequents : {string.Join(", ", distBest.Values.OrderByDescending(v=>v).Take(5))}");
Console.WriteLine($"Mauvais mot   : {worst} -> {distWorst.Count} patterns distincts, H = {ComputeEntropy(worst, WORD_LIST):F3} bits");
Console.WriteLine($"  Top-5 patterns les plus frequents : {string.Join(", ", distWorst.Values.OrderByDescending(v=>v).Take(5))}");
Console.WriteLine($"\nL'ecart de nombre de patterns distincts explique l'ecart d'entropie :");
Console.WriteLine($"  {best} disperse les secrets (information elevee), {worst} les concentre (information faible).");
Meilleur mot : LAINE -> 76 patterns distincts, H = 5.512 bits
  Top-5 patterns les plus frequents : 33, 21, 18, 16, 11
Mauvais mot   : APPEL -> 37 patterns distincts, H = 4.053 bits
  Top-5 patterns les plus frequents : 67, 44, 30, 16, 16

L'ecart de nombre de patterns distincts explique l'ecart d'entropie :
  LAINE disperse les secrets (information elevee), APPEL les concentre (information faible).

7.1 Visualisation : histogramme (distribution des feedbacks)

L’histogramme ci-dessous montre la distribution des feedbacks du meilleur mot d’ouverture (haute entropie) et d’un mot peu informatif (entropie minimale), sous forme de barres. L’intérêt pedagogique porte sur la forme de la distribution : le meilleur mot disperse ses feedbacks (distribution plate = information maximale, chaque feedback elimine a peu pres autant de candidats), tandis que le pire mot les concentre sur 1-2 patterns (distribution pointue = information minimale, la plupart des feedbacks sont identiques). Le rendu Plotly (technique C548-L2 : formatter HTML integre au kernel, zero dependence NuGet cote charting) remplace l’ancien rendu ASCII qui masquait la forme reelle de la distribution derriere une echelle lineaire de #.

// Histogramme (rendu SVG inline) : nombre de mots par pattern de feedback, trie par frequence decroissante.
// (PlotSvg + Formatter.Register definis en cell[21], technique C548-L2, MIME text/html.)
static string BuildBarSvgV(string[] labels, int[] values, string title, string yLabel) {
    const int W = 820, H = 470;
    const int mL = 70, mR = 40, mT = 50, mB = 135;
    int pW = W - mL - mR, pH = H - mT - mB;
    int n = labels.Length;
    if (n == 0) return "<svg viewBox=\"0 0 10 10\"></svg>";
    double vMax = values.Max();
    double barW = (pW / (double)n) * 0.72;
    Func<double, double> py = v => mT + pH - (v / vMax) * pH;
    var sb = new StringBuilder();
    sb.Append($"<svg viewBox=\"0 0 {W} {H}\" xmlns=\"http://www.w3.org/2000/svg\" style=\"font-family: -apple-system, 'Segoe UI', sans-serif; font-size: 12px;\">");
    sb.Append($"<rect x=\"0\" y=\"0\" width=\"{W}\" height=\"{H}\" fill=\"white\" stroke=\"#ddd\"/>");
    const int gy = 5;
    for (int g = 0; g <= gy; g++) {
        double yv = vMax * g / gy;
        double yp = py(yv);
        sb.Append($"<line x1=\"{mL}\" y1=\"{yp:F1}\" x2=\"{mL + pW}\" y2=\"{yp:F1}\" stroke=\"#e8e8e8\" stroke-width=\"1\"/>");
        sb.Append($"<text x=\"{mL - 8:F1}\" y=\"{yp + 4:F1}\" fill=\"#666\" text-anchor=\"end\">{(int)yv}</text>");
    }
    for (int i = 0; i < n; i++) {
        double xC = mL + (i + 0.5) * (pW / (double)n);
        double yp = py(values[i]);
        double bh = (mT + pH) - yp;
        sb.Append($"<rect x=\"{xC - barW / 2:F1}\" y=\"{yp:F1}\" width=\"{barW:F1}\" height=\"{bh:F1}\" fill=\"#3b82f6\"/>");
        sb.Append($"<text x=\"{xC:F1}\" y=\"{mT + pH + 8:F1}\" fill=\"#333\" text-anchor=\"end\" transform=\"rotate(-45 {xC:F1} {mT + pH + 8:F1})\">{labels[i]}</text>");
    }
    sb.Append($"<line x1=\"{mL}\" y1=\"{mT + pH}\" x2=\"{mL + pW}\" y2=\"{mT + pH}\" stroke=\"#333\" stroke-width=\"1.5\"/>");
    sb.Append($"<line x1=\"{mL}\" y1=\"{mT}\" x2=\"{mL}\" y2=\"{mT + pH}\" stroke=\"#333\" stroke-width=\"1.5\"/>");
    sb.Append($"<text x=\"18\" y=\"{mT + pH / 2.0:F1}\" fill=\"#333\" text-anchor=\"middle\" transform=\"rotate(-90 18 {mT + pH / 2.0:F1})\">{yLabel}</text>");
    sb.Append($"<text x=\"{W / 2.0}\" y=\"28\" fill=\"#222\" font-size=\"15\" font-weight=\"bold\" text-anchor=\"middle\">{title}</text>");
    sb.Append("</svg>");
    return sb.ToString();
}

static void HistogramSvg(string word, Dictionary<string, int> dist) {
    double h = ComputeEntropy(word, WORD_LIST);
    var vals = dist.OrderByDescending(kv => kv.Value).Take(15).ToList();
    var labels = vals.Select(kv => kv.Key).ToArray();
    var counts = vals.Select(kv => kv.Value).ToArray();
    string title = $"{word} ({dist.Count} patterns, H = {h:F3} bits)";
    display(new PlotSvg(BuildBarSvgV(labels, counts, title, "Nombre de mots")));
}

HistogramSvg(best, distBest);
HistogramSvg(worst, distWorst);
06131926330,0,0,0,20,2,0,0,20,0,0,0,10,1,0,0,21,0,0,0,20,0,1,0,20,0,2,0,20,0,0,1,21,2,0,0,21,1,0,0,20,0,1,0,01,0,2,0,21,1,0,0,01,1,0,0,11,0,0,0,1Nombre de motsLAINE (76 patterns, H = 5.512 bits)
013264053670,0,0,1,01,0,0,1,00,0,0,1,11,0,0,0,00,1,0,1,01,0,0,1,10,0,0,2,00,0,0,0,02,0,0,1,00,0,0,2,11,1,0,1,02,0,0,0,01,0,0,0,12,0,0,2,01,1,0,0,0Nombre de motsAPPEL (37 patterns, H = 4.053 bits)

8. Exercices

Trois exercices pour aller plus loin. Chaque stub s’execute sans erreur (convention C.1) : il retourne un résultat neutre et imprime un message d’attente. Implementez la solution demande puis re-executez la cellule.

Exercice 1 : Meilleur second mot

Le solveur par entropie pre-calcule le meilleur premier mot. Mais après le premier feedback, le meilleur second mot n’est pas forcement un candidat : on peut vouloir jouer un mot hors-liste pour maximiser l’information (si cette information suffit ensuite a identifier le secret). Implementez BestSecondGuess(candidates, wordPool) qui renvoie le mot de wordPool (eventuellement plus large que candidates) maximisant l’entropie sur candidates.

// Exercice 1 : retourner le mot de wordPool maximisant l'entropie sur candidates.
static string BestSecondGuess(List<string> candidates, List<string> wordPool)
{
    // TODO etudiant : parcourir wordPool, calculer ComputeEntropy(w, candidates), renvoyer le max.
    // Indice : RankByEntropy fait exactement cela sur wordPool = candidates ; generalisez-le.
    // Etape 1 : copier le corps de RankByEntropy.
    // Etape 2 : le faire retourner le mot (pas seulement le top-N).
    Console.WriteLine("Exercice a completer -- BestSecondGuess");
    return null;
}

Console.WriteLine("Exercice 1 : methode BestSecondGuess definie (stub). A implementer.");

// Test (a decommenter une fois implemente) :
// var second = BestSecondGuess(FilterWords(WORD_LIST, topWords[0].word, ComputeFeedback(topWords[0].word, "CRANE")), WORD_LIST);
// Console.WriteLine($"Meilleur second mot : {second}");
Exercice 1 : methode BestSecondGuess definie (stub). A implementer.

Exercice 2 : Mot d’ouverture robuste

L’entropie mesure l’information moyenne. Mais un mot legerement moins bon en moyenne peut etre plus robuste (moins de pires cas). Implementez WorstCaseGuess(candidates, wordPool) : au lieu de H(g), optimisez le pire cas – minimiser la taille du plus grand pattern après g. Comparez le mot optimal au pire cas vs le mot optimal en moyenne.

// Exercice 2 : mot qui minimise le plus grand pattern apres feedback (minimax).
static string WorstCaseGuess(List<string> candidates, List<string> wordPool)
{
    // TODO etudiant : pour chaque w de wordPool, calculer la distribution des feedbacks,
    // prendre max(patternCounts.Values), et choisir le w qui le minimise.
    // Indice : reutiliser la structure de FeedbackDistribution.
    Console.WriteLine("Exercice a completer -- WorstCaseGuess");
    return null;
}

Console.WriteLine("Exercice 2 : methode WorstCaseGuess definie (stub). A implementer.");
Exercice 2 : methode WorstCaseGuess definie (stub). A implementer.

Exercice 3 : Extension a 6 lettres

Adaptez les trois solveurs (filtrage, CSP, entropie) a des mots de 6 lettres. Quels changements sont necessaires ? L’entropie maximale theoretique change-t-elle comme attendu (cf. log2(|C|)) ? Construisez une petite liste de 6 lettres et mesurez.

// Exercice 3 : adapter a 6 lettres. Stub retourne la liste vide (a implementer).
static List<string> Solve6Letters(List<string> wordList6, string answer)
{
    // TODO etudiant : adapter ComputeFeedback (longueur variable), FilterWords, et un solveur au choix.
    // Indice : remplacer les constantes 5 par wordList6[0].Length ; verifier la coherence des longueurs.
    // Etape 1 : generaliser ComputeFeedback en ComputeFeedbackN(guess, answer).
    // Etape 2 : reutiliser un solveur (ex : EntropySolver) sur la liste 6 lettres.
    Console.WriteLine("Exercice a completer -- Solve6Letters");
    return new List<string>();
}

Console.WriteLine("Exercice 3 : methode Solve6Letters definie (stub). A implementer.");
Exercice 3 : methode Solve6Letters definie (stub). A implementer.

Conclusion

Ce twin C# a reconstruit depuis zero les trois familles de solveurs Wordle du notebook Python :

  1. Filtrage simple (baseline aleatoire) – mesure le plancher de performance ;
  2. CSP par propagation de contraintes (domaines par position, lettres requises, compteurs min/max) – exploite mieux l’information acquise ;
  3. Maximisation d’entropie (Shannon) – choisit a chaque tour le mot le plus informatif, déterministe.

Parite Python / C

Les quantites déterministes concordent entre les deux langages :

  • Liste de mots : 296 mots identiques ;
  • Entropie maximale theoretique : log2(296) = 8.21 bits ;
  • Classement top-10 des meilleurs premières tentatives (LAINE en tete) : identique au bit pres ;
  • Formule de feedback (double passe, lettres repeatedes) : comportement equivalent.

Les quantites aleatoires (simple filtrage, solveur CSP avec tirage) différent entre C# et Python : les PRNG System.Random et random.seed ne produisent pas la même sequence. C’est attendu et non un bug : l’intérêt pedagogique porte sur les algorithmes et sur l’entropie (déterministe), pas sur la sequence de tirage.

Ponts inter-series

  • Théorie de l’information : cf. serie Search et la formalisation de l’entropie (Cover & Thomas) ;
  • CSP : cf. Partie 2 (CSP) pour les domaines, la propagation et la consistence ;
  • App-7 Python : la version originale avec numpy/matplotlib donne les mêmes résultats déterministes.

Prochaines étapes

  • Implementer les exercices (meilleur second mot, minimax robuste, extension 6 lettres) ;
  • Comparer le solveur par entropie a un solveur hybride (minimax sur le pire cas) ;
  • Revenir au sommaire Search pour replacer ce notebook dans le parcours global.
Retour au sommet