Logique du Sudoku

Le Sudoku est souvent décrit comme un jeu de logique, mais « utiliser la logique » reste une formule vague tant que l’on ne décompose pas les déductions en éléments plus précis.

À tout moment d’une résolution, la grille contient des informations sur ce qui est :

• déjà vrai ;
• encore possible ;
• impossible ;
• réservé à certaines cases ou unités ;
• conditionnellement vrai si un autre candidat est faux.

Une technique de Sudoku est utile parce qu’elle transforme ces informations en une preuve.

Cette preuve produit généralement l’un de deux résultats pratiques :

placement — un chiffre doit aller dans une case ;

ou :

élimination — un chiffre ne peut pas aller dans une case.

Du Singleton nu à une chaîne avancée, toutes les techniques peuvent être comprises comme des façons particulières de prouver l’une de ces deux affirmations.

Que signifie « logique » au Sudoku ?

Dans ces Guides, une déduction est logique lorsque sa conclusion découle de contraintes et de prémisses explicitement connues, et non d’un choix arbitraire.

Les contraintes de base du Sudoku classique sont :

• chaque chiffre apparaît une seule fois dans chaque ligne ;
• une seule fois dans chaque colonne ;
• une seule fois dans chaque bloc.

Certaines techniques avancées peuvent utiliser une prémisse supplémentaire clairement annoncée, par exemple :

ce puzzle est vérifié comme ayant exactement une solution.

L’important est que la prémisse soit connue et que la conclusion en découle nécessairement.

Une déduction longue n’est donc pas moins logique qu’un Single. À l’inverse, un placement effectué avec beaucoup de confiance mais sans preuve reste une supposition.

Quatre formes récurrentes d’information au Sudoku

Beaucoup de techniques peuvent être ramenées à quatre types d’information.

1. Valeur forcée

Un chiffre est prouvé comme occupant une case précise.

Exemples :

• Full House / Last Digit ;
• Singleton nu ;
• Singleton caché ;
• placement obtenu après une élimination avancée.

Une valeur forcée est l’information la plus directe : la case est résolue.

2. Valeur interdite

Un candidat est prouvé impossible dans une case.

Exemples :

• Locked Candidates ;
• Paire nue ;
• X-Wing ;
• XY-Wing ;
• chaîne dont les extrémités éliminent une cible.

Une élimination ne résout pas nécessairement la case immédiatement, mais elle réduit l’espace logique du puzzle et peut provoquer un Single plus tard.

3. Réservation

Une réservation affirme qu’un ensemble de chiffres doit occuper un ensemble de cases, sans préciser encore quelle affectation exacte sera utilisée.

Une Paire nue {2,7} dans deux cases d’une même unité réserve par exemple 2 et 7 à ces deux cases.

Cette information permet d’éliminer 2 et 7 ailleurs dans l’unité, même si l’on ne sait pas laquelle des deux cases contiendra 2.

4. Implication

Une implication exprime une relation conditionnelle entre états de candidats.

Par exemple :

A faux → B vrai

ou :

A vrai → B faux

Les Strong Links, Weak Links, X-Chains, XY-Chains et AIC sont des langages de plus en plus riches pour relier ces implications jusqu’à une conclusion utile.

Les candidats modélisent l’incertitude

Un candidat n’est pas une prédiction ni une probabilité.

Il signifie seulement :

ce chiffre est encore compatible avec les informations actuellement connues pour cette case.

Si une case contient {2,5,8}, les trois chiffres ne sont pas « presque vrais ». Ils représentent trois possibilités encore légales.

Une technique élimine certaines possibilités ou prouve qu’une seule d’entre elles doit être vraie.

Cette distinction est fondamentale pour comprendre la résolution avancée : on raisonne sur des états possibles, pas sur des intuitions de plausibilité.

« Légal » est plus faible que « résolu »

Un candidat peut être légal sans être la solution de la case.

Les règles locales nous disent souvent seulement qu’un chiffre n’est pas encore interdit.

Pour le placer, il faut une preuve plus forte :

• tous les autres candidats de la case sont éliminés ;
• ou toutes les autres positions du chiffre dans une unité sont éliminées ;
• ou une structure avancée force cette valeur.

Confondre « je peux mettre 7 ici » avec « 7 doit être ici » est une forme classique de supposition.

Raisonnement centré sur la case

Une recherche case d’abord demande :

quelles valeurs peuvent encore occuper cette case ?

C’est la perspective naturelle des :

• Singles nus ;
• cases bivalues ;
• XY-Wings ;
• XY-Chains ;
• nombreux raisonnements ALS.

On observe directement le jeu de candidats d’une case et les relations créées par sa taille ou sa composition.

Raisonnement centré sur le chiffre

Une recherche chiffre d’abord demande :

où ce chiffre peut-il encore aller ?

Cette perspective est centrale pour :

• Singles cachés ;
• Scanning ;
• Crosshatching ;
• Locked Candidates ;
• Fish ;
• Strong Links ;
• Coloration simple ;
• X-Chains.

Le même puzzle devient souvent beaucoup plus lisible lorsqu’on alterne les perspectives case d’abord et chiffre d’abord.

Raisonnement centré sur l’unité

Une recherche unité d’abord examine une ligne, une colonne ou un bloc comme un système de contraintes.

On peut demander :

• quels chiffres manquent ?
• quelles cases peuvent les recevoir ?
• quels candidats sont réservés à un sous-ensemble de cases ?
• quelles interactions existent avec une unité voisine ?

Cette perspective relie les techniques élémentaires aux sous-ensembles et aux intersections bloc-ligne.

Logique locale et logique distribuée

Les déductions du Sudoku diffèrent aussi par la distance sur laquelle l’information doit circuler.

Déductions locales

Une déduction locale se lit dans une zone limitée :

• une case ;
• une unité ;
• une intersection ;
• un petit groupe de cases.

Singles, Paires et Locked Candidates sont souvent locaux.

Déductions distribuées

Une déduction distribuée relie plusieurs zones de la grille.

Exemples :

• Fish couvrant plusieurs lignes et colonnes ;
• Wings reliant pivot et pinces ;
• Coloration sur un réseau de conjugaisons ;
• Chains et AIC passant par plusieurs unités.

La logique n’est pas différente dans sa nature. Il faut simplement conserver davantage d’informations intermédiaires.

Le comptage est l’une des idées les plus profondes du Sudoku

Une grande partie des techniques repose sur un principe simple : un certain nombre de chiffres doit tenir dans un certain nombre de positions.

Comptage des sous-ensembles

Si N chiffres sont confinés à N cases d’une unité, ces cases sont réservées à ces chiffres.

Les Naked/Hidden Pair, Triple et Quad sont des versions directes de ce principe.

Comptage des sous-ensembles cachés

Un Hidden Subset renverse le point de vue : ce sont les positions d’un groupe de chiffres qui sont limitées à N cases, même si ces cases affichent d’autres candidats.

Ces autres candidats peuvent alors être supprimés.

Comptage des Fish

Un Fish transporte la même idée entre deux familles d’unités.

Si les candidats d’un chiffre dans N lignes de base sont entièrement couverts par N colonnes, le chiffre doit occuper ces colonnes à travers les lignes de base. Les copies extérieures dans les colonnes de couverture peuvent être éliminées.

X-Wing, Swordfish et Jellyfish ne sont donc pas des formes magiques différentes : ils appliquent le même comptage à des tailles croissantes.

Les liens forts et faibles sont un langage d’implication

Les liens permettent de transformer la structure des candidats en phrases logiques courtes.

Lien faible

Pour A et B :

A vrai → B faux

Les deux ne peuvent pas être vrais en même temps.

Cela se produit par exemple entre deux occurrences du même chiffre dans des cases qui se voient, ou entre deux candidats différents d’une même case.

Lien fort

Pour A et B :

A faux → B vrai

Un exemple fréquent est la paire conjuguée : un chiffre ne possède que deux positions dans une unité.

Au moins l’une doit être vraie.

Comprendre les deux directions évite de traiter à tort tout lien comme une relation « exactement un des deux ».

Les chaînes transforment les implications en preuve

Une chaîne relie plusieurs implications jusqu’à ce que ses extrémités produisent une conclusion.

Le cœur logique n’est pas :

« tous ces candidats sont vrais dans cet ordre ».

Mais :

« si cet état est faux, cela force le suivant vrai ; s’il est vrai, cela force un autre faux ; et ainsi de suite ».

Une X-Chain limite cette logique à un seul chiffre. Une XY-Chain s’appuie sur des cases bivalues. Une AIC généralise le langage à plusieurs types de liens.

La chaîne est utile uniquement lorsque le chemin finit par prouver une élimination, un placement ou une contradiction pertinente.

La contradiction est une méthode de preuve

Une contradiction logique consiste à montrer qu’une hypothèse conduit nécessairement à un état impossible.

Par exemple, supposer qu’un candidat A est vrai peut conduire à :

• deux mêmes chiffres dans une unité ;
• une case sans aucun candidat ;
• un chiffre sans aucune position possible dans une unité ;
• ou une contradiction avec une prémisse explicitement admise.

Dans ce cas, A est faux.

La contradiction n’est pas du hasard si chaque étape de la conséquence est forcée.

Une preuve directe et une preuve par contradiction peuvent exprimer la même logique

La même déduction peut parfois être présentée de plusieurs façons.

Une chaîne peut dire directement :

au moins une des deux extrémités doit être vraie, donc la cible qui voit les deux est fausse.

Une autre explication peut supposer la cible vraie et montrer qu’elle force les deux extrémités fausses, ce qui est impossible.

Les deux descriptions peuvent être équivalentes.

Ce qui compte n’est pas le style narratif, mais la validité des implications.

Un motif valide ne produit pas toujours un coup utile

Repérer correctement une Paire, un Fish ou une chaîne ne garantit pas qu’il existe une élimination à effectuer.

Un motif peut être présent mais déjà sans cible extérieure.

Cette distinction est importante dans un moteur de résolution humain :

• reconnaissance du motif ;
• vérification des conditions ;
• calcul des effets ;
• application uniquement si l’effet est réel.

Un motif sans élimination n’est pas une erreur, seulement une structure actuellement non productive.

La cascade de dépendances

Une seule déduction peut déclencher une chaîne d’effets beaucoup plus simple que la technique qui l’a produite.

Une élimination avancée peut :

1. réduire une case à un Singleton nu ;
2. ce placement supprime des candidats chez ses peers ;
3. un chiffre n’a plus qu’une position dans un bloc ;
4. ce Singleton caché crée un Locked Candidate ;
5. la grille revient à une phase simple.

Cette cascade explique pourquoi il est utile, après chaque coup avancé, de refaire les recherches élémentaires au lieu d’enchaîner immédiatement une nouvelle technique complexe.

Les solveurs de correction et les solveurs de style humain répondent à des questions différentes

Deux types d’outils peuvent analyser la même grille sans poursuivre le même objectif.

Solveur complet / compteur de solutions

Un solveur complet cherche à répondre à des questions comme :

• la grille a-t-elle au moins une solution ?
• combien de solutions possède-t-elle ?
• quelle est la grille solution ?

Backtracking, Algorithm X ou DLX peuvent être très efficaces pour cela.

Ils n’ont pas besoin d’imiter l’ordre de raisonnement d’un joueur humain.

Analyseur de style humain

Un analyseur humain cherche plutôt :

• quelle technique identifiable s’applique maintenant ?
• quelle est la prochaine déduction expliquable ?
• quelle difficulté humaine représente le chemin de résolution ?

Il privilégie la pédagogie et les preuves nommées plutôt que la seule obtention rapide d’une solution.

L’unicité est une prémisse supplémentaire

Les règles classiques n’imposent pas à elles seules qu’un puzzle de départ ait exactement une solution.

Les techniques comme Unique Rectangle ou BUG+1 utilisent donc une information supplémentaire :

ce puzzle a été vérifié comme unique.

Cette prémisse est parfaitement exploitable lorsqu’elle est connue, mais elle doit rester visible conceptuellement.

Une déduction d’unicité n’est pas la même chose qu’une simple conséquence locale de ligne, colonne ou bloc.

La logique n’impose pas un ordre universel de techniques

Deux joueurs peuvent résoudre la même position par des chemins différents et rester tous les deux parfaitement logiques.

L’un peut voir :

• un Fish ;

l’autre :

• une chaîne plus courte ;

et un troisième :

• une interaction locale créée par une autre élimination préalable.

Il n’existe pas nécessairement une seule « prochaine technique correcte ».

Un bon ordre de recherche est une stratégie d’efficacité et d’apprentissage, pas une loi du Sudoku.

Un modèle compact de résolution logique

On peut résumer une grande partie de la résolution en six étapes répétées :

1. mettre à jour l’état — placements, candidats, unités ;
2. repérer une contrainte ou relation exploitable ;
3. formuler la preuve — comptage, réservation, implication ou contradiction ;
4. produire l’effet — placement ou élimination ;
5. propager les conséquences ;
6. recommencer avec les techniques les plus simples devenues disponibles.

Ce modèle relie les Singles les plus élémentaires aux raisonnements avancés sans les présenter comme deux univers séparés.

FAQ

L’élimination d’un candidat est-elle un vrai coup de Sudoku ?

Oui. Une élimination est une déduction logique complète : elle prouve qu’une valeur est impossible dans une case. Elle peut ne pas placer immédiatement un chiffre, mais elle réduit l’espace des solutions possibles.

Les techniques avancées utilisent-elles d’autres règles du Sudoku ?

La plupart utilisent les mêmes contraintes classiques de manière plus distribuée. Les techniques d’unicité sont l’exception notable : elles ajoutent explicitement la prémisse que le puzzle possède une seule solution.

La contradiction est-elle la même chose que deviner ?

Non. Une contradiction est logique lorsque l’hypothèse est utilisée comme outil de preuve et que toutes ses conséquences sont forcées. Deviner consiste à choisir une possibilité sans preuve et à poursuivre comme si elle était vraie.

Pourquoi deux solveurs peuvent-ils trouver deux prochains coups différents ?

Une grille peut contenir plusieurs déductions valides simultanément. Les solveurs peuvent aussi utiliser des ordres de recherche, des vocabulaires ou des familles de techniques différents.

Tout motif valide produit-il une élimination ?

Non. Une structure peut satisfaire la définition d’un motif sans avoir de cible extérieure actuellement éliminable.

La logique du Sudoku se résume-t-elle aux éliminations ?

Non. Elle inclut placements, réservations, implications, contradictions et parfois des prémisses supplémentaires explicites. Les éliminations n’en sont qu’une forme de résultat.

Utiliser un solveur informatique reste-t-il « logique » ?

Cela dépend du solveur et de la question. Un analyseur de techniques humaines peut produire des preuves logiques nommées. Un solveur par backtracking peut trouver la solution correctement sans fournir le même chemin pédagogique.

Que faut-il apprendre ensuite ?

Pour approfondir ce langage, lisez Faut-il deviner au Sudoku ?, Sudoku et mathématiques, Comment résoudre un Sudoku et le Guide sur les Chaînes. Ensemble, ils relient contraintes, preuve humaine et méthodes de résolution plus générales.