[Raisonnement en chaîne ①] Bases : Liens forts et faibles
Le raisonnement en chaîne (Chain) est le cadre théorique fondamental des techniques avancées de Sudoku. Presque toutes les techniques d'élimination avancées — du simple X-Wing aux AICs complexes — peuvent être comprises et décrites par le raisonnement en chaîne. Cet article explore les deux concepts les plus fondamentaux du raisonnement en chaîne : les liens forts et les liens faibles.
Qu'est-ce qu'une chaîne ?
Au Sudoku, une chaîne (Chain) est une séquence de connexions formées entre candidats par certaines relations logiques. Imaginez : si nous pouvons établir des relations de raisonnement comme « si A est vrai, alors B est vrai/faux » entre candidats et relier ces relations ensemble, nous formons une chaîne.
L'essence d'une chaîne est la propagation logique : partant d'un point, à travers une série de déductions logiques, on arrive à une conclusion. Cette conclusion est typiquement utilisée pour :
- Déterminer qu'un candidat doit être vrai (confirmer le placement)
- Déterminer qu'un candidat doit être faux (éliminer le candidat)
Pour comprendre les chaînes, nous devons d'abord comprendre les unités de base qui forment les chaînes : les liens (Links). Les liens décrivent la relation logique entre deux candidats, divisés en liens forts et liens faibles selon la force de la relation.
Lien fort (Strong Link)
Un lien fort existe entre deux candidats A et B si et seulement si : exactement l'un de A et B est vrai, et l'autre est faux.
Autrement dit, si A est faux alors B doit être vrai, et si A est vrai alors B doit être faux (mutuellement exclusifs et complets).
Notation : A = B ou A ═══ B (double ligne)
Sources des liens forts
Les liens forts peuvent provenir des situations suivantes :
1. Lien fort dans une cellule bi-valeur
Quand une cellule n'a que deux candidats, un lien fort existe entre ces deux candidats.
Logique : Si 4 est faux, la cellule doit être 7 ; si 7 est faux, la cellule doit être 4.
Les cellules bi-valeur sont la source la plus courante de liens forts car elles sont intuitives : la cellule contient soit ce nombre, soit l'autre.
2. Lien fort d'une paire conjuguée
Quand un chiffre n'apparaît que dans deux positions au sein d'une unité (ligne, colonne ou bloc), un lien fort existe entre ce candidat à ces deux positions. Cette relation s'appelle une paire conjuguée.
Logique : La ligne 5 doit avoir un 3. Si R5C2 n'est pas 3, R5C8 doit être 3 ; et vice versa.
Les deux extrémités d'un lien fort de paire conjuguée sont le même chiffre à des positions différentes, pas des chiffres différents à la même position. C'est fondamentalement différent des liens forts dans les cellules bi-valeur.
3. Lien fort groupé
Plus généralement, quand un groupe de candidats et un autre groupe satisfont la relation « exactement un groupe est vrai », un lien fort existe. Cela sera couvert dans les techniques avancées et discuté en détail dans le troisième article de cette série.
Propriétés fondamentales des liens forts
- Exactement un vrai : Exactement une extrémité d'un lien fort est vraie, l'autre est fausse
- Faux propage vrai : Si une extrémité est fausse, l'autre doit être vraie
- Vrai propage faux : Si une extrémité est vraie, l'autre doit être fausse
Lien faible (Weak Link)
Un lien faible existe entre deux candidats A et B si et seulement si : si A est vrai, alors B doit être faux.
Autrement dit, au plus l'un de A et B est vrai (les deux peuvent être faux, mais les deux ne peuvent pas être vrais).
Notation : A - B ou A ─── B (ligne simple)
Sources des liens faibles
Les liens faibles ont également plusieurs sources :
1. Lien faible entre candidats différents dans la même cellule
Dans la même cellule, un lien faible existe entre deux candidats différents quelconques.
Logique : Une cellule ne peut contenir qu'un seul nombre. Si 1 est placé, ce ne peut pas être 5.
2. Lien faible entre mêmes candidats dans la même unité
Dans la même unité (ligne, colonne ou bloc), des liens faibles existent par paires entre toutes les positions du même candidat.
Logique : Un chiffre ne peut apparaître qu'une fois dans un bloc. Si R1C7 est 6, alors R2C8 et R3C9 ne peuvent pas être 6.
Comparés aux liens forts, les liens faibles sont plus omniprésents. En fait, les règles de base du Sudoku (pas de chiffres répétés dans une ligne, colonne ou bloc ; un chiffre par cellule) définissent essentiellement un grand nombre de relations de liens faibles.
Propriétés fondamentales des liens faibles
- Au plus un vrai : Au plus une extrémité d'un lien faible est vraie
- Vrai propage faux : Si une extrémité est vraie, l'autre doit être fausse
- Peuvent être tous deux faux : Les deux extrémités peuvent être fausses simultanément (différent des liens forts !)
Comparaison des liens forts et faibles
Comprendre la différence entre liens forts et faibles est la clé pour maîtriser le raisonnement en chaîne. Résumons avec un tableau comparatif :
| Propriété | Lien fort | Lien faible |
|---|---|---|
| Propriété principale | Exactement un vrai, un faux | Au plus un vrai |
| Propagation logique | Faux → Vrai, Vrai → Faux | Vrai → Faux |
| Peuvent être tous deux vrais | ✗ Non | ✗ Non |
| Peuvent être tous deux faux | ✗ Non | ✓ Oui |
| Notation | ═══ (double ligne) ou = | ─── (ligne simple) ou - |
| Sources courantes | Cellules bi-valeur, Paires conjuguées | Même cellule chiffres différents, Même unité même chiffre |
Cas spécial : Les liens forts sont aussi des liens faibles
Voici un concept important à comprendre : les liens forts sont souvent aussi des liens faibles.
Perspective lien fort : Si 4 est faux, 7 doit être vrai → Lien fort existe
Perspective lien faible : Si 4 est vrai, 7 doit être faux → Lien faible existe aussi
Conclusion : Ces deux candidats ont à la fois un lien fort et un lien faible !
Perspective lien fort : Si 3 en R5C2 est faux, 3 en R5C8 doit être vrai → Lien fort existe
Perspective lien faible : Si 3 en R5C2 est vrai, 3 en R5C8 doit être faux (même ligne ne peut avoir deux 3) → Lien faible existe aussi
Conclusion : Les paires conjuguées satisfont aussi les conditions de lien fort et faible !
Quand deux candidats satisfont la relation « exactement un vrai, un faux » (ni les deux vrais, ni les deux faux), ils ont à la fois un lien fort et un lien faible. C'est la relation de lien la plus « forte » et très utile dans la construction de chaînes.
Astuce mémoire : Les cellules bi-valeur et les paires conjuguées ont toujours à la fois des liens forts et faibles.
Le concept de « voir »
Dans le raisonnement en chaîne, le concept de « voir » (see) est fréquemment utilisé. Comprendre « voir » est crucial pour identifier les relations de lien.
Le candidat A « voit » le candidat B signifie qu'il existe un lien faible entre A et B.
Si A est vrai, alors B doit être faux — A peut « éliminer » B.
Les relations « voir » existent entre :
- Candidats différents dans la même cellule
- Même candidat dans la même ligne
- Même candidat dans la même colonne
- Même candidat dans le même bloc
Ce concept sera fréquemment utilisé lors de la discussion des applications de chaînes, comme « les candidats qui peuvent être vus par les deux extrémités peuvent être éliminés ».
Pourquoi distinguer les liens forts et faibles est-il si important ?
La distinction entre liens forts et faibles est la pierre angulaire du raisonnement en chaîne. Leurs différences déterminent :
Les liens forts permettent d'inférer « vrai » à partir de « faux » ; les liens faibles permettent d'inférer « faux » à partir de « vrai ». Le raisonnement en chaîne utilise ces deux directions de propagation différentes pour construire des déductions logiques complexes.
Lors de la construction de chaînes, vous devez identifier correctement si chaque étape est un lien fort ou faible pour garantir un raisonnement correct. Traiter incorrectement un lien faible comme un lien fort conduit à des conclusions erronées.
De nombreuses techniques apparemment différentes (comme X-Wing, Skyscraper, XY-Wing, etc.) sont essentiellement des chaînes avec des motifs spécifiques. Comprendre les liens forts et faibles permet de comprendre ces techniques dans un cadre unifié.
Prochaines étapes
Cet article a présenté les deux concepts les plus fondamentaux du raisonnement en chaîne : les liens forts et les liens faibles. Avec ces concepts compris, nous pouvons commencer à apprendre comment les combiner pour construire des chaînes complètes.
Dans le prochain article, nous discuterons :
- Comment alterner liens forts et faibles pour construire des chaînes
- Règles de propagation des états vrai/faux dans les chaînes
- L'approche de « coloration » dans le raisonnement en chaîne
- Méthodes pour tirer des conclusions des extrémités de chaîne
- Glossaire Sudoku - Référence rapide pour les termes utilisés dans cet article
- Technique XY-Wing - Application pratique du raisonnement en chaîne
- Technique XY-Chain - Application étendue des chaînes de cellules bi-valeur