Les stratégies de résolution du Sudoku

Le Sudoku se résout entièrement par la logique : aucune grille bien construite ne nécessite de deviner. Tout l'art consiste à appliquer, du plus simple au plus sophistiqué, un répertoire de techniques qui permettent soit de placer un chiffre avec certitude, soit d'éliminer des candidats pour faire progresser le raisonnement.

Cet article les passe en revue par ordre croissant de difficulté. Un rappel de vocabulaire utile : on appelle candidat un chiffre encore possible dans une case donnée, et unité une ligne, une colonne ou une boîte (le carré de 3×3). Chaque chiffre de 1 à 9 doit apparaître exactement une fois dans chaque unité.

1. Les techniques de placement direct

Ce sont les premières à employer : elles placent directement un chiffre.

Le candidat unique (Naked Single)

Une case ne contient plus qu'un seul candidat possible : on l'y inscrit sans hésiter. C'est la situation la plus élémentaire. Elle survient lorsque les huit autres chiffres sont déjà présents dans la ligne, la colonne ou la boîte de cette case.

Exemple : si une case voit déjà les chiffres 1, 2, 3, 4, 5, 6, 7 et 9 dans ses unités, le seul candidat restant est le 8.

Le placement forcé (Hidden Single)

Un chiffre n'a plus qu'une seule case possible dans une unité, même si cette case admet par ailleurs plusieurs candidats. Le chiffre y est forcé.

Exemple : dans une boîte, le chiffre 7 ne peut tenir que dans une seule case parce que toutes les autres cases libres « voient » déjà un 7 sur leur ligne ou leur colonne. Peu importe que cette case ait encore d'autres candidats : le 7 y est obligatoire, puisqu'il doit bien figurer quelque part dans la boîte.

Le Hidden Single est sans doute la technique la plus rentable du débutant, car elle débloque énormément de grilles faciles à intermédiaires.

2. Les interactions ligne / colonne / boîte

Ces techniques n'inscrivent rien directement mais éliminent des candidats, ce qui finit par créer des candidats uniques ailleurs.

Le pointage (Pointing Pair / Pointing Triple)

Dans une boîte, si tous les candidats d'un chiffre donné sont alignés sur une même ligne (ou une même colonne), alors ce chiffre devra forcément se placer sur cette ligne à l'intérieur de la boîte. On peut donc l'éliminer de cette ligne partout ailleurs, hors de la boîte.

Exemple : dans une boîte, le 4 n'est candidat que dans deux cases, toutes deux situées sur la même ligne. Le 4 de cette boîte occupera donc cette ligne — on supprime le candidat 4 de toutes les autres cases de cette ligne dans les deux autres boîtes traversées.

La réduction de boîte (Box/Line Reduction, ou « claiming »)

C'est l'inverse du pointage. Dans une ligne (ou colonne), si tous les candidats d'un chiffre sont confinés à une seule boîte, alors ce chiffre devra se placer dans cette ligne au sein de cette boîte. On l'élimine donc des autres cases de la boîte.

Exemple : sur une ligne, le 9 n'est candidat que dans trois cases, toutes appartenant à la même boîte. On peut alors retirer le candidat 9 des six autres cases de cette boîte.

3. Les groupes nus et cachés

Ces techniques exploitent des ensembles de cases qui « se réservent » un groupe de chiffres.

La paire nue (Naked Pair)

Deux cases d'une même unité contiennent exactement les deux mêmes candidats, et seulement ceux-là. Ces deux chiffres leur sont donc réservés : ils occuperont ces deux cases, dans un ordre ou dans l'autre. On peut alors éliminer ces deux candidats de toutes les autres cases de l'unité partagée.

Exemple : sur une ligne, deux cases ne contiennent que {3, 8}. Le 3 et le 8 occuperont ces deux cases. On supprime donc 3 et 8 de toutes les autres cases de la ligne.

Le triplet nu et le quadruplet nu (Naked Triple / Quad)

Généralisation de la paire. Trois cases d'une unité ne contiennent, au total, que trois candidats distincts (chaque case n'a pas besoin de les avoir tous les trois). Ces trois chiffres leur sont réservés et peuvent être éliminés du reste de l'unité. Le quadruplet étend le principe à quatre cases et quatre candidats.

Exemple de triplet : trois cases d'une colonne contiennent respectivement {2, 5}, {5, 7} et {2, 7}. À elles trois, elles n'utilisent que {2, 5, 7}. On élimine ces trois chiffres des autres cases de la colonne.

La paire cachée (Hidden Pair)

Symétrique de la paire nue. Deux chiffres n'apparaissent, dans toute une unité, que dans les deux mêmes cases (parmi d'autres candidats). Ces deux chiffres y sont donc enfermés : on peut supprimer tous les autres candidats de ces deux cases, ne gardant que la paire.

Exemple : dans une boîte, les chiffres 1 et 6 ne sont candidats que dans deux cases (qui contiennent par ailleurs 1, 6, 4, 9...). Ces deux cases accueilleront 1 et 6 ; on supprime donc le 4, le 9 et tout le reste de ces deux cases.

Triplets et quadruplets cachés existent aussi, sur le même principe, mais sont rares et difficiles à repérer.

4. Les techniques de poisson (basées sur des alignements)

Ces techniques portent des noms imagés et travaillent sur la géométrie d'un seul chiffre à travers la grille.

Le X-Wing

On considère un seul chiffre. On cherche deux lignes dans lesquelles ce chiffre n'est candidat que dans deux cases chacune, et où ces cases occupent les deux mêmes colonnes. Les quatre cases forment alors un rectangle.

Le raisonnement : dans chacune des deux lignes, le chiffre ira dans l'une ou l'autre colonne. Quelle que soit la combinaison, les deux colonnes contiendront ce chiffre exactement une fois via ces lignes. On peut donc éliminer ce chiffre de ces deux colonnes partout ailleurs (dans les autres lignes).

Exemple : le 5 n'est candidat, sur la ligne 2, que dans les colonnes C et G ; et sur la ligne 7, lui aussi seulement dans les colonnes C et G. Le 5 occupera donc la colonne C sur l'une des deux lignes et la colonne G sur l'autre. On supprime le candidat 5 de toutes les autres cases des colonnes C et G.

Le X-Wing fonctionne symétriquement : on peut partir de deux colonnes partageant deux lignes, et éliminer alors sur les lignes.

Le Swordfish

C'est un X-Wing élargi à trois lignes et trois colonnes. Un chiffre est candidat dans trois lignes, réparti sur les mêmes trois colonnes (chaque ligne n'a pas besoin d'avoir les trois — deux suffisent, du moment que l'ensemble se limite à trois colonnes). On élimine alors ce chiffre des trois colonnes ailleurs. Le Jellyfish pousse encore le motif à quatre lignes et quatre colonnes.

5. Les chaînes et techniques avancées

Réservées aux grilles « expert » et « diabolique », elles enchaînent des déductions conditionnelles.

Le XY-Wing

Trois cases à deux candidats forment une chaîne. Une case « pivot » contient {X, Y}. Elle voit deux autres cases : l'une contient {X, Z}, l'autre {Y, Z}. Quel que soit le chiffre placé dans le pivot, l'une des deux ailes finira par valoir Z. Toute case vue à la fois par les deux ailes ne peut donc pas contenir Z : on l'y élimine.

Le XYZ-Wing

Variante du précédent où le pivot contient trois candidats {X, Y, Z} et voit deux cases {X, Z} et {Y, Z}. Toute case voyant les trois à la fois perd le candidat Z.

Les chaînes de couleurs (Simple Coloring)

On colorie en deux teintes alternées les cases liées par un chiffre n'ayant que deux emplacements possibles dans une unité (« lien fort »). En suivant la chaîne, on détecte des contradictions : si deux cases de même couleur se voient, cette couleur est fausse, et toutes les cases de l'autre couleur reçoivent le chiffre.

Les chaînes forcées et le Nishio

Techniques les plus lourdes : on suppose temporairement une valeur dans une case et on en déroule les conséquences. Si elles mènent à une contradiction (deux fois le même chiffre dans une unité, ou une case sans candidat), l'hypothèse est fausse. À la frontière du « tâtonnement raisonné », elles sont souvent considérées comme un dernier recours.

Tableau récapitulatif

Conseils de méthode

Aborder une grille de manière ordonnée fait gagner beaucoup de temps. On commence toujours par épuiser les placements directs (candidats uniques et placements forcés), qui suffisent pour les grilles faciles. Quand la grille se bloque, on note tous les candidats de chaque case au crayon, puis on cherche les interactions ligne/boîte et les groupes nus ou cachés. Les techniques de poisson et les chaînes ne s'imposent que sur les grilles les plus difficiles, et toujours après avoir épuisé les méthodes plus simples — il est inutile de chercher un X-Wing tant qu'un placement forcé reste disponible.

Enfin, un principe d'or : une bonne grille de Sudoku a une solution unique et se résout sans deviner. Si tu te sens obligé de tenter au hasard, c'est généralement qu'une technique logique t'a échappé.