Résolution de casse-têtes/Résolution du sudoku

Ce chapitre se propose de présenter, selon une perspective synthétique et logique (donc en les justifiant), l'ensemble des techniques régulièrement utilisées dans la résolution d'un sudoku classique (de dimensions 9 × 9), quel qu'en soit le niveau de difficultés.

Exemple de sudoku facile

L'animation (cases avec fond jaune) reproduit le déroulement chronologique de la solution

Concrètement, ces techniques ne seront pas présentées « à plat » mais par ordre de complexité croissante, et en rapprochant ces techniques entre elles selon leur filiation éventuelle, leur points communs et leurs différences ; par ailleurs, chacune sera exposée de façon aussi visuelle que possible et avec des exemples (au moins un) toujours complets (grilles entières), illustrés et commentés.

En pratique, on peut estimer qu'au moins 99 % des sudokus proposés dans les périodiques et les revues spécialisées peuvent être résolus à l'aide des seules techniques présentées ici, du moins à condition de ne commettre ni erreur ni omission ...

Nota : selon l'avis de la majorité des "puristes", l'approche par hypothèse (ou « backtracking » en anglais) n'est pas une démarche purement logique (en raison de la nécessité d'un choix fait au hasard entre plusieurs hypothèses) ; c'est pourquoi cette méthode, malgré son indéniable efficacité (on peut à juste titre la qualifier d'« heuristique »), n'est pas traitée ici !

Exemple de grille de sudoku

La grille ci-dessous est un exemple de sudoku d'un niveau de difficulté assez grand ...

État initial : remarquer que les 29 données initiales sont écrites sur un fond bleu pâle ...

Cela permet, dans la solution finale, de les distinguer des 52 valeurs déduites par raisonnement, écrites sur un fond jaune pâle.

Solution finale de la grille présentée :
on vérifie d'une part que chaque ligne, chaque colonne et chaque pavé de 3 x 3 cases contient bien 9 cases dans lesquelles figure l'un des neuf chiffres de 1 à 9, d'autre part que chaque chiffre figure une fois et une seule dans chaque ligne, chaque colonne et chaque pavé !

L'explicitation de la résolution de ce sudoku est donnée ici !

Vocabulaire et notations générales utilisés

Pour faciliter la compréhension des techniques de résolution des sudokus, il est nécessaire de préciser le vocabulaire qu'il convient d'utiliser pour décrire la structure et le contenu d'une grille de sudoku.

• Les lignes sont appelées A,B,C,D,E,F,G,H et J (le "I" est évité car, avec certaines polices de caractères et notamment la police standard utilisée par Wikipédia, on risque de le confondre - dans les explications - avec la lettre minuscule "l") : A est la première ligne, J la dernière. • Les colonnes sont appelées a, b, c, d, e, f, g, h, et j, de gauche à droite.

• Pour désigner une case, on donne d'abord la ligne puis la colonne : par exemple Fa (dans la grille-exemple présentée dans l'introduction la case Fa contenait un 3) • Les neuf grands "pavés" d'une grille de sudoku contiennent 3 fois 3 cases ; ils sont désignés par Xx, Xy, Xz (première rangée), puis Yx, Yy, Yz (seconde rangée) et enfin Zx, Zy et ZZ (dernière rangée). On appelle "bloc" un ensemble de 3 pavés contigus et alignés. Par exemple, le bloc X réunit les pavés Xx, Xy et Xz, et le bloc z réunit les pavés Xz, Yz et Zz. • Un chiffre que l'on peut inscrire à coup sûr dans une case s'appelle la "valeur" de cette case (ce peut être soit une valeur initiale, soit une valeur découverte ultérieurement, par déduction logique). • Les chiffres susceptibles d'occuper une case s'appellent les "candidats" de cette case ; en principe, il y a toujours plusieurs candidats, car un candidat unique peut (et doit) être immédiatement transformé en "valeur" ! • Lorsqu'une grille contient n valeurs initiales, la solution de la grille consiste à trouver la valeur des 81-n valeurs inconnues. La résolution d'une grille consiste donc à découvrir les 81-n étapes qui conduisent logiquement à la solution finale.

Le vocabulaire particulier qui sert à nommer les divers types de raisonnements sera expliqué ci-dessous, au fur et à mesure que seront exposées les techniques correspondantes.
On trouvera également, en fin de document, un glossaire reprenant l'ensemble du vocabulaire et des notions nécessaires à la compréhension des différentes techniques de résolution, ainsi qu'un petit lexique anglo-français contenant l'équivalent anglais d'un certain nombre d'expressions.

Suggestions pour la notation chronologique de la solution des sudokus

Il est conseillé, lorsque l'on veut résoudre un sudoku, de noter (sous forme abrégée mais suffisamment explicite) les différentes étapes de la résolution et, pour les plus délicates d'entre elles, les raisonnements qui ont servi à la solution. En effet, au cas où l'on commettrait une erreur (de raisonnement ou d'étourderie), erreur qui se traduit (le plus souvent quelques étapes plus tard) par une impossibilité logique, cette précaution permet de revenir en arrière, de comprendre l'erreur commise et de la corriger !

Pour noter de façon concise et sans ambiguïté les raisonnements utilisés dans le déroulement, étape après étape, du processus de résolution d'un sudoku, il est donc commode d'utiliser certaines conventions dont voici les principales (d'autres conventions de notation, correspondant aux techniques les plus élaborées, seront indiquées plus loin):

Pour dire qu'une certaine case contient une valeur connue, on fait suivre la désignation de la case par le chiffre de cette valeur : par exemple Fa3 Pour dire qu'une case n'est pas encore remplie mais qu'elle peut encore, à un moment donné, être susceptible de contenir certaines valeurs, on fait suivre la désignation de la case par les chiffres correspondant à ces candidats (en principe écrits dans l'ordre croissant) : par exemple Fa124 La notation abrégée "?Fa:Fa3" doit être lue ainsi : "Qu'y a-t-il sur la case Fa ? Réponse : l'examen de toutes les possibilités actuelles montre que ce ne peut être qu'un 3 !" La notation abrégée "4F?:Fa4" doit être lue ainsi : "Où peut-on placer un 4 sur la ligne F ? Réponse : l'examen de toutes les possibilités actuelles montre que ce ne peut être que sur la case Fa !" De même la notation abrégée "4a?:Fa4" doit être lue ainsi : "Où peut-on placer un 4 sur la colonne a ? Réponse : l'examen de toutes les possibilités actuelles montre que ce ne peut être que sur la case Fa !" La notation abrégée "4Yx?:/a" doit être lue ainsi : "Où peut-on placer un 4 dans le pavé Yx ? Réponse : l'examen de toutes les cases possibles de ce pavé montre qu'elles sont toutes situées sur la colonne a !" La notation abrégée "4A?:/Yx" doit être lue ainsi : "Où peut-on placer un 4 sur la ligne A ? Réponse : l'examen de toutes les cases possibles de cette ligne montre qu'elles sont toutes situées dans le pavé Yx !"

Voici, à titre d'exemple, la solution (rédigée en notation condensée) de la première grille présentée dans ce document (chaque tiret " - " précédé et suivi d'une espace indique le début d'une étape nouvelle) :

Fd1 - Eh7 - Fc8 - Ej5 - Dg3 - Jc1 - Ha7 - 4c?:Bc4 - 3c?:Ac3 - 7c?:Cc7 - Ag7 - Be7 - paire nue 26 en Fg-Gg d'où 2 exclu en Cg, reste Cg9 - Ca5 - Ce2 - Ba9 - 6Yy?:/f d'où 6 exclus en Hf ; paire camouflée 48 en Hg-Jg d'où 6 exclus en Hg ; paire camouflée 59 en Hh-Jh d'où 6 exclus en Hh ; 3e?:/Zy d'où 3 exclus en Hd-Hf ; paire nue 68 en Ab-Bb d'où 6 exclus en Hb ; paire camouflée 36 en He-Hj d'où 15 exclus en He ; trio nu (incomplet) 356 en Ge-He-Je d'où 5 exclu en Ae, reste Ae1 !!! - Aj6 - Bb6 - Ab8 - Bj1 - Bh2 - Af9 - Ad5 - Fh6 - Fg2 - Gg6 - Gc5 - Dc6 - Df2 - Db5 - Ea4 - Eb2 - Hb4 - Ja6 - Ed3 - Ef6 - Bd8 - Bf3 - Ge3 - Gj2 - Hj3 - Hf1 - Jf8 - Jd2 - Hd9 - Jg4 - Hg8 - He6 - Je5 - Jh9 - Hh5 !
Les expressions "paire camouflée", "paire nue" et "trio nu" qui apparaissent ci-dessus dans la partie colorée en brun seront expliquées plus loin ...
On remarquera que l'étape qui a conduit à trouver Ae1 est particulièrement longue et délicate !

Principes de résolution

• En principe la seule règle qu'il convient de garder toujours à l'esprit est la suivante : toutes les cases doivent être remplies par un chiffre de 1 à 9 ; les neuf cases de chacune des 9 lignes doivent contenir, dans un ordre quelconque, chacun des chiffres de 1 à 9 et il en est de même pour les 9 colonnes, ainsi que pour les 9 pavés. • Toutes les autres règles (et elles sont assez nombreuses) en découlent ... La résolution d'un sudoku se fait généralement en 2 phases :

• Dans la première phase, on fait "visuellement" un certain nombre de constatations et de raisonnements très simples ("techniques simples") qui permettent de remplir directement certaines cases ; si le sudoku proposé n'est pas particulièrement difficile, on pourra le résoudre complètement sans avoir à passer à la phase suivante ...
• Dans la seconde phase, on est contraint, pour aller plus loin dans la résolution du problème, de raisonner, au moins pour quelques-unes des étapes restantes de la résolution, sur les candidats des cases encore non résolues.

Classification des sudokus et niveaux de difficulté

Contrairement à une opinion largement répandue, la difficulté d'un sudoku n'est pas nécessairement liée au faible nombre de valeurs initiales (toutefois cette liaison est statistiquement assez fréquente).

• Les sudokus les plus faciles peuvent être résolus, comme on vient de le dire, sans avoir à passer par la seconde phase ; en revanche, les plus difficiles ne peuvent se passer de l'examen des candidats possibles. Toutefois, il arrive très souvent qu'au cours de la seconde phase, seules quelques étapes (rarement plus de trois) nécessitent réellement d'examiner attentivement les candidats des cases non résolues, la majorité des autres étapes pouvant généralement être réalisées en ne faisant appel qu'aux "techniques simples".
• Les sudokus les plus ardus sont ceux pour lesquels les étapes les plus difficiles de la seconde phase nécessitent plusieurs raisonnements successifs avant de découvrir une nouvelle "valeur" avec laquelle on peut remplir une case supplémentaire, la difficulté de ces étapes étant d'autant plus grande que ces raisonnements sont, soit plus nombreux (voir l'exemple donné ci-dessus), soit basés sur des techniques plus complexes !

Il convient aussi de mentionner la classification suivante :

Type 1 : les sudokus de ce type ne comportent aucune solution Type 2 : les sudokus de ce type en comportent plusieurs Type 3 : les sudokus de ce type (heureusement rarissimes) sont ceux dont la solution est unique mais ne peut être découverte à l'aide d'aucune des techniques de raisonnement rigoureux connues jusqu'à présent : ils requièrent pour leur résolution l'utilisation de programmes informatiques qui parcourent l'ensemble des possibilités (la rencontre d'une impossibilité - "cul-de-sac" - oblige à revenir en arrière au dernier choix "arbitraire" réalisé) Type 4 : ce type comprend tous les autres sudokus ! Signalons en passant qu'il existe parmi les sudokus de ce type un sous-type particulier (et assez fréquent), celui des sudokus qu'on peut dire "redondants" car leurs données contiennent au moins une case dont la connaissance de la valeur n'est pas nécessaire à la résolution du problème (car elle peut être déduite de la valeur des autres cases).

Il est convenu généralement que les sudokus de type 1 et 2 sont invalides et que les sudokus de type 3 sont sans intérêt (sauf pour les amateurs de l'extrême qui voudraient s'en inspirer pour tenter de mettre au point un nouveau type de méthode de résolution ...).
Dans la suite de cet article, il ne sera donc question que des sudokus de type 4 (redondants ou non).
Dans l'exposé des différentes techniques, nous commencerons par trois techniques "simples", puis nous aborderons trois techniques "élaborées" pour terminer par deux techniques "extrêmes" (la dernière d'entre elles étant déclinée en cinq variantes ...).

Trois techniques simples

Les techniques simples sont les techniques qui peuvent être mises en œuvre sans avoir besoin de recourir à l'examen exhaustif de tous les candidats de toutes les cases non remplies.
Il en existe trois grandes catégories :

• L'élimination directe
• La recherche des valeurs uniques
• L'élimination indirecte

Élimination directe

(ou recherche d'un candidat "solitaire camouflé") On procède en quatre temps :

a : pour une valeur donnée v (par exemple la valeur 4 dans le premier exemple - exemple 01a - présenté ci-dessous), on repère (en vert clair dans les trois exemples qui vont suivre) toutes les cases qui contiennent cette valeur ; b : on "barre" mentalement toutes les cases vides de toutes les régions (ligne, colonne ou pavé) qui contiennent cette valeur v (cases colorées en vert sombre dans les trois exemples qui vont suivre) ; c : on cherche s'il existe une région qui contient une case vide et non barrée (case colorée en jaune dans les trois exemples ci-dessous) ; d : si c'est le cas et si cette case est unique, on inscrit la valeur v (que dans le jargon du sudoku on appelle un "solitaire camouflé") dans la case trouvée.

Distinguons quelques types de cas :

• Dans les cas les plus courants, on travaille "par bloc" et la région qui intervient à l'étape c est un pavé dont deux lignes (ou deux colonnes) du bloc ont été barrées ; il reste, sur les cases du pavé appartenant à la ligne (colonne) non barrée, une seule case vide qui peut être accompagnée :
  • soit d'une case déjà remplie et d'une case barrée car appartenant à une colonne barrée (ligne), comme dans l'exemple 01a ;
  • soit de deux cases occupées, ce qui correspond, comme dans l'exemple 01b, à l'un des cas les plus évidents (donc faciles à repérer).
    
• Les cas où, comme dans l'exemple 01c, la région de l'étape c est une ligne ou une colonne sont moins faciles à repérer.
• Enfin, les cas où l'on dispose, pour une valeur donnée, de 8 cases contenant déjà la valeur v sont les plus simples car on est sûr de trouver sans peine la neuvième case qui manque !

Voici donc trois exemples d'élimination directe.
D'abord un exemple courant (illustré par trois images successives, correspondant respectivement aux étapes -a, puis -b et -c, et enfin -d expliquées ci-dessus) :

exemple 01a - étape a		exemple 01a - étapes b et c
exemple 01a : ici on travaille dans les lignes A et B du bloc X, et avec la colonne g		exemple 01a - étape d

... ensuite, un exemple particulièrement facile :

exemple 01b : ici l'examen du seul bloc Z nous permet d'attribuer la valeur 8 à la case Gg

exemple 01b

... et enfin un dernier exemple, moins immédiat :

exemple 01c : les lignes barrées C, F et G ne laissent en colonne a qu'une case libre, la case Ha, à laquelle on va donc pouvoir attribuer la valeur 5

exemple 01c

Recherche des valeurs uniques

(ou recherche d'un candidat "solitaire nu")

Cette recherche consiste à examiner si, pour une case donnée (la case Cd dans l'exemple 02a ci-dessous), il n'y aurait pas une seule valeur possible (valeur unique, encore appelée "solitaire nu", par opposition aux solitaires "camouflés" que nous avons rencontrés dans la technique précédente).
Pour cela, il suffit :

de repérer toutes les cases déjà remplies dans le "voisinage" de la case étudiée (on appelle "voisinage" d'une case la ligne, la colonne et le pavé auxquels la case appartient) de compter le nombre de ces cases remplies et si l'on en trouve 8 (et à condition que l'on n'ait pas fait d'erreur !), d'attribuer à la case étudiée la valeur qui ne fait pas partie des 8 valeurs déjà inscrites.

exemple 02a : Ici la valeur qu'il convient de placer dans la case (sur fond jaune) Cd est un 9, puisque toutes les autres valeurs existent déjà dans le "voisinage" de Cd (le 1 en Cg, le 2 en Bd, le 3 en Fd, le 4 en Af, le 5 en Cj, le 6 en Ad, le 7 en Jd et le 8 en Cc).

exemple 02a

Cette technique est la plus simple à comprendre mais elle est plus lourde à mettre en œuvre que la précédente, puisqu'en principe, elle devrait être envisagée pour toutes les cases restant vides.
En pratique, il est assez judicieux, du moins dans un premier temps (c'est-à-dire tant que l'on ne rencontre pas de difficulté à continuer d'avancer dans la résolution du sudoku), de n'envisager cette technique que dans les régions où le nombre de valeurs renseignées est déjà assez élevé (d'abord 7, puis 6 ou à la rigueur 5).
Notons que si une région (ligne, colonne ou pavé) possède déjà 8 valeurs renseignées (situation qui ne se produit que fort rarement au début de la résolution d'un sudoku, mais est au contraire très fréquente en fin de résolution), la valeur à attribuer à la dernière case vide est évidente, comme dans l'exemple qui suit :

exemple 02b : Voici un exemple (rare après seulement 2 étapes de résolution qui ont conduit à placer d'abord un 7 en Af puis un 6 en Cf ...) dans lequel il est évident que, sur la colonne f, il faut placer le 2 manquant dans la seule case vide Ef.

exemple 02b

Élimination indirecte

Il s'agit d'une extension de la première méthode (élimination directe en quatre temps - a - b - c et - d) dans laquelle le "temps - b" est complété par l' éventuelle élimination de cases supplémentaires (quand elle est possible).
Voici donc les quatre "temps" de cette méthode :

a : pour une valeur donnée v (la valeur 1 dans le premier exemple 03a ci-dessous), on repère toutes les cases qui contiennent cette valeur ; b : on barre mentalement toutes les cases vides de toutes les régions contenant cette valeur et, si l'on a repéré 2 ou 3 cases vides alignées faisant partie d'un même pavé et dont on est sûr que l'une d'entre elles contient la valeur étudiée (il n'est pas nécessaire de savoir laquelle !), on barre aussi les cases vides alignées avec celles-ci qui sont situées en dehors du pavé (il s'agit donc d'une technique avec "localisation imprécise") ! Si c'est possible, on répète la manœuvre - b, comme dans l'exemple 03c (quatrième image) ! c : on cherche s'il existe une région qui contient une case vide et non barrée  ; d : si c'est le cas et si cette case est unique, on inscrit la valeur v dans la case trouvée.

Voici un premier exemple :

exemple 03a - étape a exemple 03a - étape b exemple 03a (décrit en 4 images successives) explication détaillée  : dans la troisième image, on a entouré en rouge les 2 cases vides Eg et Fg du pavé Yz qui permettent d'étendre les suppressions à la case Gg, et l'on constate alors que dans le pavé Zz (ou encore sur la ligne G), seule la case Gj (en jaune) reste libre : elle seule peut donc recevoir la valeur 1 ! exemple 03a - étape c exemple 03a - étape d

Voici un second exemple (pour lequel on a seulement illustré l'étape b) :

exemple 03b : Ici, on travaille encore avec la valeur 1. Les cases vides Ee et Ef du pavé Yy permettent d'étendre les suppressions aux cases Eb et Ej et l'on constate alors que, dans le pavé Yz (ou sur la colonne j), seule la case Fj (en jaune) reste libre et peut donc se voir attribuer la valeur 1 !

exemple 03b

Voici enfin un troisième exemple (plus complexe car il illustre un cas de doublement de la phase - b et qui, à ce titre, mérite d'être illustré par 4 images successives) :

exemple 04a - étape a exemple 03a - étape b exemple 03c (décrit en 4 images successives) explication détaillée : ici on travaille avec la valeur 8 ; dans la troisième image, on a entouré en rouge les 2 cases vides alignées Bg et Bj du pavé Xz qui permettent, sur la même ligne B, d'étendre les suppressions à la case Bb , ce qui entraîne que, dans le pavé Xx, il ne reste plus que 2 cases vides, les cases Ac et Cc qui sont entourées en rouge sur la quatrième image ; comme celles-ci sont alignées sur la colonne c, on peut alors supprimer la case Jc de la même colonne, ce qui entraîne que, dans le pavé Zx, seule la case Ga (en jaune) reste libre : elle seule peut donc recevoir la valeur 8 ! exemple 03c - étape c exemple 03c - étape d

Cette méthode d'élimination indirecte est en général considérée comme un cas particulier de la méthode des régions dominantes. Ce point de vue est assez discutable car elle ne nécessite pas, pour sa mise en œuvre, de procéder à l'identification fastidieuse des "candidats" de toutes les cases non renseignée.

La méthode d'élimination indirecte, facile et plus rapide à mettre en œuvre que la méthode de recherche des valeurs uniques, est d'un grand intérêt car elle permet :

• dans bien des cas : de résoudre complètement un sudoku sans avoir à passer aux techniques de phase 2 qui requièrent obligatoirement le recours à l'identification des "candidats" ;
• assez souvent : de découvrir un "solitaire" (nu ou camouflé) qui avait échappé à l'attention ...

Trois techniques élaborées

L'ensemble des techniques élaborées se range dans trois grandes catégories :

- les régions dominantes

- les groupes nus

- les groupes camouflés

Mais avant d'aborder en détail ces techniques élaborées, il faut observer que la différence fondamentale qui existe entre les techniques simples et les autres (qu'elles soient "élaborées" ou "complexes"), c'est que les premières ont pour objet de déterminer directement la valeur d'une des cases du sudoku, tandis que l'objectif - plus modeste - des autres techniques n'est que de supprimer un ou plusieurs candidats d'une ou plusieurs cases, même si cela n'aboutit pas immédiatement à l'attribution d'une valeur à une case.

Pour pouvoir utiliser une technique élaborée, il est donc nécessaire d'identifier les candidats des cases encore non résolues.

Identification préalable des candidats

Pour ce faire, il faut, pour chaque case examinée, procéder en trois temps : dresser mentalement la liste des 9 candidats potentiels (de 1 à 9) puis, en examinant (exhaustivement !) l'ensemble des cases du "voisinage" de la case étudiée, éliminer de cette case les chiffres qui correspondent à la valeur d'une case déjà résolue du voisinage, et enfin noter les candidats restants.

Voici, à titre illustratif, ce que cela donne dans le cas de certains des exemples déjà rencontrés (01a, 01b, 01c et 02a) :

candidats de l'exemple 01a : L'examen des candidats des cases du pavé Xz montre que seule la case Ch présente le candidat 4 (solitaire dit "camouflé" car il n'est pas le seul candidat de la case Ch)

exemple 01a - candidats

candidats de l'exemple 01b : Les candidats des cases du pavé Zz montrent que seule la case Gg présente le candidat 8 (solitaire camouflé)

exemple 01b - candidats

candidats de l'exemple 01c : Les candidats des cases de la colonne a montrent que seule la case Ha présente le candidat 5 (solitaire camouflé)

exemple 01c - candidats

candidats de l'exemple 02a : La case Cd ne présente qu'un seul candidat, le 9 (solitaire dit "nu")

exemple 02a - candidats

Régions dominantes

Les techniques basées sur la notion de région dominante sont fondées sur la généralisation de l'évidence suivante :

"Lorsque qu'une valeur est attribuée à une case, elle peut aussitôt être effacée de la liste des candidats des cases de tout son voisinage."

En voici le principe.
Si l'on constate, en travaillant sur un candidat fixé et en ne s'intéressant qu'aux cases non résolues dont la liste des candidats contient ce candidat (on fait abstraction des autres cases), que les cases d'une région R1 (région "dominante") font toutes partie d'une autre région R2 (région "dominée"), alors on peut supprimer le candidat pour toutes les cases de R2 qui ne font pas partie de R1 ! (Pour justifier ces suppressions, il suffit d'observer que, quelle que soit la case de la région R1 dont la valeur sera égale au candidat fixé, les cases de son voisinage comprendront toujours les cases de la région R2 qui possèdent ce candidat ; on peut donc supprimer ce candidat pour toutes ces cases).

Dans ce type de situation, l'une des 2 régions (R1 ou R2) est un pavé, l'autre étant une région "mince", c'est-à-dire une ligne ou une colonne (on verra que, parmi les techniques extrêmes, on peut définir une technique -celle des réseaux s'inspirant du même principe mais mettant en œuvre des lignes et des colonnes).

Donnons deux exemples :

exemple 04a : Ici, pour le candidat 6, la région "dominante" R1 est le pavé Yy et la région "dominée" R2 est la colonne e ; le 6 peut donc être retiré des candidats des cases Be et Ge (ensuite, le 6 de la case Gd devient un "solitaire camouflé" de la ligne G et Gd prend donc la valeur 6)

exemple 04a

exemple 04b : Ici, pour le candidat 8, la région R1 est la ligne A et la région R2 est le pavé Xx ; le 8 peut donc être retiré des candidats des cases Ba, Bb, Bc et Ca (ensuite, le 3 de la case Bc devient un "solitaire nu" de la ligne B et Bc prend donc la valeur 3 )

exemple 04b

Groupes nus

Les techniques basées sur les groupes nus constituent une généralisation de la méthode de recherche des valeurs uniques ("solitaires nus").

Le principe consiste ici à repérer si, dans une même région, un groupe de n cases non résolues ne serait pas tel que, si l'on rassemble mentalement la liste des candidats de ces n cases (en ne comptabilisant chaque chiffre identique qu'une seule fois), cette liste comprend n chiffres et pas davantage ! Si n vaut 2, on parle de "paire nue" ; si n vaut 3, on parle de "trio nu" et si n vaut 4, de "quatuor nu". Une fois que l'on a repéré un groupe nu dans une région, on peut, pour toutes les cases de cette région qui ne font pas partie du groupe, éliminer de leurs candidats les chiffres figurant dans la liste de n chiffres (les cases du groupe ont donc l' "exclusivité" des candidats de la liste). Lorsque n est supérieur à 2, il arrive fréquemment qu'au moins une des cases du groupe n'ait pas comme candidats l'ensemble des chiffres de la liste : on parle alors de groupe (trio ou quatuor) "incomplet", mais cela n'enlève rien à la validité de la manœuvre d'élimination.

Voici quelques exemples :

exemple 05a : Le groupe des 2 cases Ce et Ge de la colonne e forme une paire nue dont les candidats sont 78 ; on peut donc éliminer les candidats 7 et le 8 des autres cases de la colonne e (le 8 de la case Fe et les 7 et 8 des cases Ae, De et Je) (la suite est délicate ... et il faut un très long raisonnement faisant appel à des techniques extrêmes pour établir que ... la case Je présente la valeur 9 !)

exemple 05a

exemple 05b : Le groupe des 2 cases Eg et Eh de la ligne E forme une paire nue dont les candidats sont 24 ; on peut donc éliminer notamment le candidat 2 de Ed (ce qui fait apparaître en colonne d un 2 solitaire camouflé à la case Fd) et le 4 de Ee... Mais le même groupe nu appartient aussi au pavé Yz, ce qui permet d'autres éliminations : le 4 de Dj (ce qui crée en ligne D un 4 solitaire camouflé à la case De) et le 2 de Fj ...

exemple 05b

exemple 05b (suite) : La même configuration présente le groupe de 3 cases Bd, Be et Bf de la ligne B qui forme un trio nu dont les candidats sont 379 (trio "incomplet" car seul Be présente l'ensemble des 3 candidats) ; on peut donc éliminer les candidats 3 et 7 de Ba. Le même groupe appartient aussi au pavé Xy, mais il n'en résulte aucune élimination car les autres cases du pavé sont déjà renseignées !

exemple 05b - suite

exemple 05c : Le groupe des 3 cases Ea, Eb et Fc du pavé Yx forme un trio nu dont les candidats sont 189 (trio incomplet) ; on peut donc éliminer le candidat 8 de Da et les candidats 1 et 9 de Fa. Il apparaît alors sur la ligne D une paire nue 26 en Da et Dh, ce qui entraîne l'exclusion des candidats 2 et 6 de la case Dg qui ne conserve plus qu'un candidat "solitaire nu" valant 8 !

exemple 05c

exemple 05d : Le groupe des 4 cases Da, Db, Ec et Fc du pavé Yx forme un quatuor nu dont les candidats sont 3459 (quatuor incomplet) ; on peut donc éliminer (outre le candidat 5 des cases Ea et Eb) le candidat 3 et 9 de la case Ea, ce qui fait apparaître en colonne a un solitaire camouflé 3 à la case Ga.

exemple 05d

exemple 05e : Le groupe des 4 cases Ja, Jf, Jg et Jh de la ligne J forme un quatuor nu (incomplet) dont les candidats sont 3478 ; on peut donc éliminer, outre les candidats 4 et 8 de la case Jd, les candidats 7 et 8 de la case Jj où apparaît un candidat 5 solitaire nu.

exemple 05e

Groupes camouflés

Les techniques basées sur les "groupes camouflés" constituent une généralisation de la méthode d'élimination directe qui recherche les "solitaires camouflés".
(la méthode vue précédemment - celle basée sur les groupes nus - constituait quant à elle une généralisation de la méthode de recherche des valeurs uniques ou "solitaires nus")

Le principe consiste ici à repérer si, dans une même région, un groupe de n cases non résolues et une liste de n chiffres distincts ne seraient pas tels que : - les cases qui ont parmi leurs candidats l'un des chiffres de la liste font toutes partie du groupe de n cases ; - les cases de la région qui ne font pas partie du groupe n'ont aucun de leurs candidats qui appartienne à la liste de n chiffres. Si n vaut 2, on parle de "paire camouflée" ; si n vaut 3, on parle de "trio camouflé" et si n vaut 4, de "quatuor camouflé". Une fois que l'on a repéré un groupe camouflé dans une région, on peut, pour toutes les cases de ce groupe, éliminer tous les candidats qui ne figurent pas dans la liste de n chiffres. Ainsi, à la fin de l'opération, le groupe camouflé se trouve transformé en un groupe "nu" (ce qui peut éventuellement permettre de nouvelles éliminations si le groupe appartient aussi à une seconde région) ! Lorsque n est supérieur à 2, il arrive fréquemment qu'au moins une des cases du groupe n'ait pas comme candidats l'ensemble des chiffres de la liste : on parle alors de groupe (trio ou quatuor) "incomplet", mais cela n'enlève rien à la validité de la manœuvre d'élimination.

Autant le repérage des solitaires camouflés est facile (et plus facile que celui des solitaires nus), autant le repérage des groupes camouflés est délicat (bien plus que celui des groupes nus de même effectif n) : le repérage des paires camouflées est assez délicat, celui des trios camouflés est très difficile ; quant à celui des quatuors camouflés, il exige des qualités et des efforts d'attention extrêmes ... Heureusement, les problèmes qui exigent le repérage de trios (et surtout de quatuors) camouflés sont fort rares !

Voici deux exemples :

exemple 06a : Le groupe de 2 cases Jd et Je de la ligne J forme une paire camouflée dont les candidats sont 29 ; on peut donc éliminer (outre les candidat 4, 5 et 8 de la case Jd) le candidat 5 et surtout le candidat 7 de la case Je, ce qui fait apparaître en colonne e un solitaire camouflé 7 à la case De. Remarquons que la paire camouflée appartient aussi au pavé Zy et que, devenue une paire nue de ce pavé, elle permet d'éliminer encore le candidat 9 des cases Hd et He

exemple 06a

exemple 06b : Le groupe de 3 cases Af, Gf et Jf de la colonne f forme un trio camouflé (incomplet) dont les candidats sont 124  ; on peut donc éliminer (outre les candidats 8 et 9 des cases Af et Gf, et les candidats 3 et 8 de la case Jf) le candidat 7 de la case Gf, ce qui fait apparaître dans le pavé Zy un solitaire camouflé 7 à la case Gd. nota : dans l'image ci-contre, les candidats qui figurent sont déjà, contrairement à l'habitude prise pour les autres images, le résultat d'éliminations particulières (basées successivement sur un trio nu incomplet 349 dans le pavé Zx et une paire camouflée 39 à la ligne H) !

exemple 06b

Nous ne présentons pas d'exemple de quatuors camouflés car ceux-ci sont vraiment rarissimes ! En outre, il est exceptionnel qu'un sudoku présentant une configuration de quatuor camouflé nécessite de faire appel à cette technique pour résoudre le problème ... !

Deux techniques extrêmes

Les techniques extrêmes n'interviennent que très exceptionnellement au début de la résolution d'un sudoku !

Nous ne nous intéresserons qu'aux deux catégories de techniques extrêmes les plus utiles :
- les réseaux
- les différentes variantes de coloriage

Techniques basées sur les réseaux

Ces techniques constituent, comme les techniques (déjà vues) basées sur les régions dominantes, une généralisation de l'affirmation :
"Lorsque qu'une valeur est attribuée à une case, elle peut aussitôt être effacée de la liste des candidats des cases de tout son voisinage".

Ces techniques qui font appel à la notion d'ensemble dominant sont basées sur le principe suivant (rappelons que nous désignons par région "mince" une ligne ou une colonne mais pas un pavé).

Si l'on constate, en travaillant sur un candidat fixé et en ne s'intéressant qu'aux cases non résolues dont la liste des candidats contient ce candidat (on fait abstraction des autres cases), que les cases d'un ensemble E1 de n régions minces (ensemble "dominant") font toutes partie d'un autre ensemble E2 de n régions minces (ensemble "dominé"), alors on peut supprimer le candidat pour toutes les cases de E2 qui ne font pas partie de E1 ! (la justification de ces suppressions est analogue - en plus complexe toutefois - à celle que nous avons donnée pour les techniques basées sur les régions dominantes). Dans ce type de techniques, l'un des ensembles (E1 ou E2) est toujours un ensemble de lignes, l'autre étant un ensemble de colonnes (contrairement à ce que nous avons vu dans les régions dominantes, les ensembles de pavés sont ici exclus !). Lorsque n est supérieur à 2 , il est possible (et c'est même assez fréquent) qu'un réseau d'ordre n soit "incomplet", c'est-à-dire que certaines des cases situées aux intersections de l'ensemble dominant et de l'ensemble dominé n'aient pas parmi leurs candidats le candidat étudié (ou qu'elles soient déjà résolues). Comme pour les groupes camouflés ou pour les groupes nus, ceci n'invalide pas les possibilités d'élimination.

Selon la valeur de n, les auteurs de langue anglaise parlent de "X-Wing" lorsque n vaut 2, de "Swordfish" lorsque n vaut 3, de "Jellyfish" lorsque n vaut 4 ou même de "Squirmbag" lorsque n vaut 5 (ce qui est tout à fait superflu car un sudoku de 9 x 9 = 81 cases qui présente un Squirmbag peut toujours être résolu en considérant le Jellyfish "complémentaire" !).
En français, il est préférable de s'exprimer plus simplement en parlant de réseau d'ordre n, ou encore, sous forme abrégée, de réseau-II, réseau-III ou réseau-IV !

Voici trois exemples :

exemple 07a : Ici on a, pour le candidat 8, un réseau d'ordre II : les 2 lignes F et J en constituent l'ensemble E1 (dominant) et les colonnes a et j l'ensemble E2 ; en effet, les deux lignes F et J ont toutes leurs candidats 8 situés à l'une des cases placées à l'intersection avec les colonnes a et j ; on peut donc éliminer les candidats 8 des cases de l'ensemble E2 qui ne font pas partie de l'ensemble E1 (donc en Ha et Dj ).

exemple 07a

exemple 07b : Ici on a, pour le candidat 8, un réseau d'ordre III : les 3 lignes B, E et G en constituent l'ensemble E1 et les colonnes a, b et g l'ensemble E2 ; noter que le réseau est incomplet puisque les cases Eb et Ga ne présentent pas le candidat 8, mais ceci n'empêche en rien d'éliminer les candidats 8 des cases Hg et Ja, ce qui fait apparaître en Ja un 2 solitaire nu.

exemple 07b

exemple 07c : Ici on a, pour le candidat 2, un réseau d'ordre IV : les 4 colonnes c, d, f et g en constituent l'ensemble E1 et les lignes A, C, G et J l'ensemble E2 (noter que ce réseau est complet ce qui est assez rare pour un réseau d'ordre IV) ; on peut donc éliminer les candidats 2 des cases Aa, Ab, Aj, Ga, Gj, Ja, Jb et Jj ; mais il faut encore faire une longue suite de raisonnements ... pour aboutir à un 9 solitaire nu à la case Ej !

exemple 07c

Techniques basées sur le coloriage

Avant d'exposer dans le détail chacune des diverses techniques de coloriage, commençons par présenter un certain nombre de notions et de principes généraux : techniques, liens, jeux de couleurs, principe d'interdiction et principe d'élimination.

Principes généraux et vocabulaire

Les différentes techniques

Il existe 5 techniques faisant appel au principe du coloriage ; les voici, classées par ordre de difficulté croissante :

• le coloriage simple,
• le coloriage multiple,
• le bi-coloriage,
• le coloriage mixte et
• le coloriage généralisé.

Les trois sortes de liens

Toutes ces techniques tirent parti de la présence de trois sortes de relations particulières entre deux cases "voisines" :

• les "liens simples",
• les "liens forts" ou
• les "liens faibles".

• On parle de "lien simple" entre 2 cases d'une même région lorsque ces 2 cases possèdent un candidat commun, et qu'aucune des autres cases de cette région ne possède ce candidat. • On parle de "lien de paires" lorsque, dans une même région, 2 cases possèdent exactement deux candidats et que l'un (au moins) de ces deux candidats leur est commun. Plus précisément, on parle : - de "lien fort" si le candidat commun d'un lien de paires n'appartient à aucune autre case de la région ; - et de "lien faible" si, au contraire, le candidat commun du lien de paires appartient aussi à (au moins) une autre case de la région. Remarque : 2 cases liées entre elles par un "lien simple" peuvent très bien être liées également par un "lien fort" ; il suffit pour cela que les 2 cases ne possèdent que 2 candidats ; en revanche, un "lien simple" et un "lien faible" ne peuvent pas concerner les 2 mêmes cases ! Le coloriage simple et le coloriage multiple n'utilisent que des "liens simples" (tous relatifs au même candidat) ; le bi-coloriage n'utilise que des "liens de paires" ("forts" ou "faibles"), le coloriage mixte utilise indifféremment les trois sortes de liens et enfin le coloriage généralisé n'utilise que les liens simples et les liens forts.

Jeux de couleurs

Les cinq techniques de coloriage sont toutes basées sur les 2 notions de couple et de jeu de couleurs (deux de ces techniques - le coloriage multiple et le coloriage généralisé - utilisent plusieurs jeux de couleurs, les trois autres n'en utilisent qu'un seul).

• On appelle couple un ensemble composé d'une case et d'un chiffre (de 1 à 9). On dira qu'un couple est vrai si le chiffre est bien la valeur de la case (dans la solution du sodoku) ; on dira que le couple est faux si ce chiffre n'est pas la valeur de la case et l'on ne dira rien dans les autres cas (indétermination). À tout moment du processus de résolution, le "statut" d'un couple est donc soit "vrai", soit "faux", soit (encore) indéterminé ! • On appelle jeu de couleurs un ensemble de deux couleurs qu'on dira "opposées" (et qu'on choisira à cet effet) par exemple C1 et C2, ou C3 et C4, ou C5 et C6, ou encore C7 et C8 ... et qui sont destinées à marquer des ressemblances (ou au contraire des divergences) de "statut" entre des "couples" formé d'une case et d'un candidat. Dans les trois techniques de coloriage simple, de coloriage multiple et de coloriage généralisé, on va chaque fois que ce sera possible : - donner la même couleur à deux couples si l'on est sûr que le statut respectif de ces couples est, soit "vrai" et "vrai", soit "faux" et "faux" (dans ce cas, on dira que ces deux couples sont "solidaires" car "vrais" tous les deux ou "faux" tous les deux) ! - donner des couleurs "opposées" à deux couples si l'on est sûr que l'un des deux couples est "vrai" tandis que l'autre couple est "faux" (couples qu'on dira "antagonistes") ! En revanche (attention), avec le bi-coloriage et le coloriage mixte, il peut arriver (mais pas toujours), si l'on a pris en compte des "liens faibles", que deux couples case-candidat de même couleur ne soient pas "solidaires" ou que deux couples de couleurs "opposées" ne soient pas "antagonistes" !

Remarque : si deux couples sont tels que l'un au moins d'entre eux est "faux", on dira que ces couples sont "incompatibles" ; c'est notamment le cas si les 2 cases concernées sont "voisines" ...

Principe d'interdiction

Dans la mise en œuvre d'une technique de coloriage, on progresse pas à pas en prenant en compte, à chaque pas, un nouveau lien. Mais il est interdit de prendre en compte un nouveau lien qui ferait apparaître, par le coloriage supplémentaire qui en résulterait, un couple case-candidat qui aurait la même couleur qu'un couple case-candidat (déjà coloré) situé sur une case "voisine". Remarque : on verra que le fait de tomber sur une "situation d'interdiction" est souvent l'indice de la possibilité d'une élimination de candidat ...

Principe d'élimination

Dans tout essai de coloriage, le but recherché est de permettre, une fois le coloriage terminé, d'éliminer un candidat en vertu du principe suivant : si deux couples case-candidat sont à la fois colorés, antagonistes et "voisins" d'un (même) troisième couple (coloré ou non), ce dernier couple case-candidat est nécessairement "faux" et son candidat peut donc être éliminé de la case de ce couple. Pour pouvoir appliquer correctement ce principe, voici ce qu'il faut entendre par "voisinage" entre couples : deux couples case-candidat distincts sont "voisins" s'ils ont, soit la même case (et donc des candidats distincts), soit même candidat et même région (ligne, colonne ou pavé) ! Parce qu'ils mettent en œuvre plusieurs jeux de couleurs, le coloriage multiple et le coloriage généralisé ne peuvent pas utiliser le principe d'élimination sous la forme simple qui vient d'être expliquée, mais ils l'utilisent sous une forme plus sophistiquée (bien qu'équivalente) !

Tableau comparatif des différentes techniques de coloriage

Nous terminerons ces préliminaires par un petit tableau comparatif :

Technique	Nombre de jeux de couleurs	Types de liens pris en compte	Nombre de candidats analysés	Équivalences logiques "même couleur ⇔ solidarité" "couleurs opposées ⇔ antagonisme"	Voisinage pris en compte	Possibilité de cases multi-jeux (••)
Coloriage simple	1	simples	1	assurées	entre cases	impossible
Coloriage multiple	2 ou +	simples	1	assurées	entre cases	impossible
Bi-coloriage sans liens faibles	1	forts	de 3 à 9	assurées	entre couples "case-candidat"	impossible
Bi-coloriage avec liens faibles (•)	1	liens forts et liens faibles	de 3 à 9	non assurées	entre couples "case-candidat"	impossible
Coloriage mixte sans liens faibles	1	liens simples et liens forts	de 3 à 9	assurées	entre couples "case-candidat"	impossible
Coloriage mixte avec liens faibles (•)	1	tous	de 3 à 9	non assurées	entre couples "case-candidat"	impossible
Coloriage généralisé	2 ou +	tous	de 3 à 9	assurées	entre couples "case-candidat"	possible

renvois :

(•) : la technique ne "fonctionne" correctement que si 2 liens faibles successifs n'ont jamais le même candidat commun ;

(••) : présence éventuelle de cases dont au moins 2 candidats sont colorés en utilisant, pour l'un, un jeu de couleurs, et pour l'autre, un autre jeu de couleurs.

---

Coloriage simple

Commençons par la technique de coloriage la plus simple, celle qui n'exploite que la présence de liens simples concernant tous le même candidat.

En voici le principe : - on choisit un jeu de couleurs "opposées" (par exemple C1 et C2) - on choisit un candidat c (parmi les valeurs qui ne sont pas complètement attribuées) - on ne s'intéresse qu'aux cases qui présentent ce candidat (on fait donc abstraction de toutes les autres) - on repère un "lien simple" pour ce candidat c - on colorie, avec la couleur C1, le fond de l'une des 2 cases de ce lien et on colorie l'autre case avec la couleur C2 - on cherche si l'une des 2 cases du lien précédent ne présente pas, pour le même candidat c, un autre "lien simple" avec une "nouvelle" case. Si c'est le cas pour la case coloriée avec C1, on colorie la nouvelle case avec la couleur C2 ; si c'est le cas pour la case coloriée avec C2, on colorie la nouvelle case avec la couleur C1. On obtient donc ainsi une (ou deux) nouvelle case coloriée. - à partir de cette (ou de ces) nouvelle(s) case(s) coloriée(s), on recommence le processus de l'étape précédente pour étendre encore de proche en proche, et autant que possible, le coloriage à d'autres cases - on peut ainsi poursuivre cette manœuvre de coloriage jusqu'à ce qu'il ne soit plus possible de l'étendre à de nouvelles cases - on se trouve alors en présence d'une grille dont certaines cases sont coloriées.

Attention :

Avant chaque extension du coloriage, il est nécessaire de veiller à la cohérence logique du travail effectué : il faut que la nouvelle case que l'on se propose de colorier avec une certaine couleur ne se trouve pas être "voisine" d'une case déjà coloriée avec cette couleur ; sinon il faut absolument s'interdire cette extension. En revanche, cette "interdiction" a un avantage, car elle signale que l'on va pouvoir, comme on va le voir ci-dessous, procéder non seulement à une élimination de candidat mais même aussi à l'attribution de la valeur c à l'une au moins des cases colorées !

Les cases ainsi colorées possèdent les propriétés suivantes : - leur couleur de fond est, soit C1, soit C2 (le coloriage simple est souvent appelé "coloriage alterné" car on alterne la couleur chaque fois que l'on exploite un nouveau "lien simple") ; - elles possèdent toutes le même candidat (qui est le candidat c choisi au départ) ; - pour ce candidat, chacune d'entre elles est associée à au moins une autre de ces cases, formant avec elle un "lien simple" ; - si l'on considère deux cases quelconques ne présentant pas la même couleur, elles sont obligatoirement "antagonistes", c'est-à-dire que, même si elles ne présentent pas entre elles un "lien simple", si l'une possède la valeur c, l'autre ne la possède pas, et réciproquement ! - en raison de la façon dont le coloriage a été réalisé (changement de couleur à chaque nouveau lien simple détecté), toutes les cases présentant la même couleur (C1 ou C2) sont, vis-à-vis du candidat c choisi, "solidaires", c'est-à-dire qu'ou bien ce candidat c est la valeur de toutes ces cases, ou bien aucune de ces cases n'a ce candidat c comme valeur ! - ce que nous résumerons en disant que toutes les cases "C1" sont solidaires, toutes les cases "C2" sont solidaires, et toute case "C1 "est antagoniste de toute case "C2" !

Élimination de candidat

Une fois le coloriage simple C1|C2 terminé, il va pouvoir servir éventuellement à avancer dans la résolution du sudoku, à condition que l'on se trouve dans la situation "favorable" suivante : - une même case N, non colorée mais présentant le candidat c, est à la fois dans le voisinage d'une case C1 et dans le voisinage d'une case C2 : dans ce cas, le candidat c peut et doit être éliminé c'est-à-dire effacé pour la case N ! Lorsque qu'une élimination vient d'être effectuée, il est recommandé de procéder immédiatement à une mise à jour du coloriage correspondant car celui-ci peut éventuellement permettre d'autres éliminations ! Si une élimination du candidat c intervient dans une case colorée, toutes les cases dotées de la même couleur doivent aussi "perdre" ce candidat puisqu'elles sont solidaires de celle-ci, et toutes les cases qui présentent l'autre couleur doivent au contraire être affectées de la valeur c !

Remarques :

- la situation "favorable" à l'élimination de candidat se rencontre nécessairement dans le cas où l'on est tombé sur l'interdiction décrite ci-dessus : en effet, la case que l'on s'est interdit de colorer est voisine d'une case colorée avec C1 et d'une case colorée avec C2, et elle doit donc perdre son candidat c ; en outre, cette élimination de candidat a pour conséquence immédiate que l'une de ses deux cases voisines colorées va se retrouver avec, pour le candidat c , un statut de solitaire (camouflé ou nu) et doit donc se voir attribuer la valeur c, ainsi, éventuellement, que toutes les autres cases "solidaires", c'est-à-dire dotées de la même couleur ! - si en revanche, on n'est pas tombé sur la situation d'interdiction, il n'est pas certain que le coloriage réalisé permette à coup sûr d'aboutir à une élimination de candidat ! Mais la seule façon de le savoir, c'est de "tenter sa chance" en examinant, une par une, chacune des cases non colorées possédant le candidat c ! - dans les quatre exemples qui vont suivre, les cases n'ont pas été entièrement coloriées, contrairement à l'usage le plus fréquent : on a en effet préféré ne colorier que le fond sur lequel est écrit le candidat c avec lequel on travaille, ce qui permet de mieux rapprocher la technique de "coloriage simple" des autres techniques de coloriage (coloriage multiple, bi-coloriage et coloriage généralisé) ; quant à l’enchainement des liens simples, il a été marqué, dans les commentaires de ces exemples, en utilisant le symbole "~".

Pour commencer, nous illustrerons la technique du coloriage simple alterné par deux exemples (utilisant chaque fois les 2 mêmes couleurs C1|C2) dans lesquels on se trouve dans le cas d' "interdiction" décrit ci-dessus ; et conformément à ce qui a été expliqué, le premier exemple (08a) présentera, après l'élimination initiale, un solitaire camouflé, tandis que le second exemple (08b) présentera un solitaire nu :

exemple 08a : Le coloriage réalisé ici concerne le candidat 8. On a l'enchaînement de liens simples suivant : Gg8 ~Gf8 ~He8 ~Hh8 ~Bh8 ~Cj8 ~Fj8 avec en Bh une "bifurcation" Bh8 ~Bb8 ~Ab8. On s'est interdit de prendre en compte la liaison Fj8~Ff8, pour éviter que les deux cases "voisines" Gf et Ff de la colonne f ne soient dotées de la même couleur ! On peut donc supprimer le candidat 8 de la case Ff, ce qui permet, sur la ligne F , d'attribuer la valeur 8 à la case Fj (solitaire camouflé) ! Toutes les cases solidaires de Fj vont donc à leur tour prendre la valeur 8, à savoir Gg, He, Bh et Ab.

exemple 08a

exemple 08b : Le coloriage réalisé ici concerne le candidat 4. On a l'enchaînement de liens simples suivant : Ah4 ~Af4 ~Gf4 ~Jd4 ~Jh4 ~Gg4 ~Bg4 ~ Ba4 ~Cc4 ~Fc4 ~Fe4 ~Ee4 ~Ea4 . On s'est interdit de matérialiser le lien Jd4 ~Cd4 pour éviter d'avoir sur la ligne C deux cases de même couleur, Cd et Cc. On peut donc supprimer le candidat 4 pour la case Cd qui est "voisine" commune des 2 cases Cc et Jd qui sont de couleurs opposées. On a alors, en colonne d, un 4 solitaire nu à la case Jd qui doit prendre la valeur 4, ainsi que toutes les cases "solidaires" Af, Ba, Ee, Fc et Gg. Quant aux cases de couleur "opposée", elles perdent toutes leur candidat 4, ce qui permet d'attribuer encore (candidats solitaires nus) la valeur 2 aux cases Ah, Fe et Gf, et la valeur 8 aux cases Bg, Cc et Ea et Jh.

exemple 08b

Voici maintenant deux exemples dans lesquels on peut procéder à une élimination de candidat sans avoir au préalable rencontré une situation d' "interdiction" :

exemple 08c : Le coloriage réalisé ici concerne le candidat 2. On a l'enchaînement de liens simples suivant : Ed2 ~Df2 ~Dc2 ~Ea2 ~Ba2(ici il n'y a aucune "bifurcation"). Les cases Ba et Df sont de couleurs opposées et la case Bf est leur "voisine" commune : on peut donc lui retirer le candidat 2 et il lui reste un candidat 7 solitaire nu qui est sa valeur ! La case Ba perd donc son candidat 7 et il lui reste le seul candidat 2 (solitaire nu) qui est donc sa valeur. Les 2 autres cases solidaires de Ba, c'est-à-dire Ed et Dc, prennent donc aussi la valeur 2, tandis que les cases "antagonistes" Df et Ea perdent le candidat 2 !

exemple 08c

exemple 08d : Le coloriage réalisé ici concerne le candidat 8. On a l'enchaînement (sans "bifurcation") de liens simples suivant : Fd8 ~Ad8 ~Bf8 ~Bc8 ~Aa8 ~ Da8 ~Ec8. Les cases Da et Bf sont de couleurs opposées et la case Df est leur "voisine" commune : on doit donc lui retirer le candidat 8 ; de même, les cases Da et Fd sont de couleurs opposées et la case De est leur "voisine" commune qui ne peut donc conserver son candidat 8. À présent, sur la ligne D, la case Da présente donc un 8 solitaire camouflé : elle doit donc prendre la valeur 8, de même que les cases Ad et Bc qui en sont solidaires !

exemple 08d

Coloriage multiple

Le coloriage multiple (appelé souvent aussi "coloriage double" lorsqu'il n'utilise que deux jeux de couleurs opposées) est une extension du coloriage simple.

En effet, le coloriage multiple met en œuvre, non pas un seul, mais au moins deux enchaînements de "liens simples", ces liens concernant tous le même candidat c. Le premier enchaînement utilise par exemple le couple de couleurs opposées C1|C2 , tandis que le second enchaînement utilise le couple de couleurs opposées C3|C4.

Elimination de candidat :

En cas de coloriage multiple, l'élimination éventuelle d'un candidat repose sur une "extension" de l'élimination mise en œuvre dans la technique de coloriage simple : en effet, si l'on détecte (au lieu d'une case isolée non colorée ...) deux cases colorées solidaires (peu importe qu'elles soient toutes deux de la couleur C3 ou de la couleur C4) et dont l'une est voisine d'une case C1 tandis que l'autre est voisine d'une case de couleur C2 (opposée à C1), alors on peut affirmer que :

- que le candidat c peut être effacé pour toutes les cases solidaires dotées de la couleur C3 (ou C4), et

- que les cases antagonistes C4 (ou C3) doivent prendre la valeur c !

exemple 08e : Le coloriage multiple réalisé ici concerne le candidat 8. On a deux enchaînements indépendants, l'un avec le couple de couleurs C1|C2, l'autre avec le couple de couleurs C3|C4 : le premier enchaînement est formé par les liens simples Dg8 ~Cg8 ~Bh8 ~Be8 (sans "bifurcation"), tandis que le second comprend les liens Cd8 ~Ed8 ~Fe8 ~Fc8 ~Dc8 avec la "bifurcation" Ed8~Eh8. On constate que la case Cd est voisine de la case Be, alors que la case Eh (solidaire de Cd) est voisine de la case Dg (antagoniste de Be). On peut donc effacer le candidat 8 pour les 4 cases solidaires Cd, Fe, Dc et Eh (et donner par conséquent la valeur 3 aux cases Fe, Dc et Eh) et donner la valeur 8 aux cases qui en sont "antagonistes", c'est-à-dire Ed et Fc !

exemple 08e

Remarquons qu'un coloriage multiple n'a pas nécessairement à comporter un grand nombre de cases : en effet, on peut (en théorie) concevoir des cas (extrêmes) où le premier enchaînement ne compte que deux cases, et où le second enchaînement n'en compte que trois !

Bi-coloriage

Le bi-coloriage fait appel, non pas aux "liens simples", mais aux "liens de paires", c'est-à-dire aux couples de cases "voisines" dotées de 2 candidats (ni plus ni moins) dont l'un au moins est à la fois commun et propre à ces deux cases . Les "liens de paires" peuvent être des "liens forts" ou des "liens faibles".
Par ailleurs, le bi-coloriage n'utilise qu'un seul jeu de couleurs opposées.

Voici comment on procède :

- on repère un "lien de paires" ; on choisit l'une des cases de ce lien et l'on colorie le fond de cette première case en deux couleurs C1 et C2, la couleur C1 étant affectée au fond du premier candidat de cette case et la couleur C2 au fond du second de ses candidats. On colorie ensuite de la même façon la seconde case avec les couleurs C1 et C2, mais en veillant à ce que la couleur du fond du candidat commun aux deux cases soit inversée !

- on cherche si l'une des deux cases déjà "bi-coloriées" présente un "lien de paires" avec une case pas encore coloriée ; si c'est le cas, on colorie cette nouvelle case en respectant toujours la règle de l'inversion de couleur pour le fond de case du candidat commun ;

- on étend ainsi, de proche en proche, le coloriage, jusqu'à ce qu'il ne soit plus possible d'aller plus loin ;

- Attention : avant chaque extension du coloriage, il est nécessaire de veiller à la cohérence logique du travail effectué : il faut, pour chacun des deux candidats de cette nouvelle case, que la couleur que l'on se propose d'affecter à ce candidat n'ait pas déjà été affectée au même candidat de l'une des cases du "voisinage" de la nouvelle case, sinon il faut renoncer à cette extension (ce qui n'empêche pas d'en chercher d'autres éventuelles ...) !

En cas de bi-coloriage, les principes d'une éventuelle élimination de candidat ressemblent (en partie) à celui de l'élimination des coloriages simples ; en effet :

Si l'on détecte une case non colorée N dont l'un des candidats c est à la fois coloré avec un fond C1 dans une case "voisine" V1 et coloré avec un fond C2 d'une autre case "voisine" V2 et si, en outre, on peut être sûr que parmi les 2 cases V1 et V2, l'une a pour valeur c tandis que l'autre ne l'a pas, alors le candidat c peut être effacé de la case non colorée N ! Lors de l'examen du cheminement des n liens de paires qui relient les cases V1 et V2, voici notamment trois circonstances dans lesquelles on peut être certain que c est la valeur de l'une des deux cases V1 et V2 et de seulement l'une d'entre elles : - cas n° 1 : tous les liens de ce cheminement sont des "liens forts" ; - cas n° 2 : dans la suite ordonnée des n candidats communs de ce cheminement, on ne trouve jamais 2 fois de suite le même candidat et les deux candidats extrêmes, c' (commun à V1 et à la case qui la suit) et c" (commun à V2 et à la case qui la précède) ne sont ni l'un ni l'autre le candidat c ; - cas n° 3 : dans le cheminement qui va de V1 à V2, chacun des tronçons dont les liens sont tous des "liens faibles" fait intervenir une suite ordonnée de candidats communs dans laquelle on ne trouve jamais 2 fois de suite le même candidat (le cas n° 3 est une sorte d' "hybride" des 2 précédents et représente en fait le cas général).

Pour justifier l'affirmation précédente (qui ne va pas de soi lorsque l'un - au moins - des "liens de paire" pris en compte dans le cheminement de V1 à V2 est un "lien faible" ...), examinons la "situation" de la case V1 vis-à-vis du candidat c, lorsque l'on se trouve dans le cas n° 2 décrit ci-dessus :

- si c est la valeur de V1, c ne peut pas être un candidat de N et doit donc être éliminé pour N ;

- inversement, si c n'est pas la valeur de V1, V1 prend nécessairement la valeur c' ; la case voisine de V1 dans l'enchaînement de liens qui conduit de V1 à V2 ne peut donc pas avoir la valeur c' et ce type d' "impossibilité" va se transmettre de proche en proche à travers l'enchaînement de liens... pour aboutir à l'impossibilité de donner la valeur c" à la case V2 qui doit donc prendre la valeur c, ce qui, à nouveau, nous conduit à éliminer le candidat c pour la case N !

Ainsi, quelle que soit la valeur de V1, le candidat c doit être éliminé de N !

Remarque : au lieu de raisonner en partant de V1 pour aboutir à V2, on pourrait aussi bien raisonner en partant de V2 pour aboutir à V1 (la conclusion finale restant bien sûr identique, à savoir l'élimination du candidat c de N).

Comme la technique du "coloriage simple", la technique du bi-coloriage aboutit à un coloriage en 2 couleurs (C1 et C2), et l'on retrouve aussi des "solidarités" et des "antagonismes", mais ces solidarités et antagonismes concernent cette fois, non pas les cases bi-coloriées elles-mêmes, mais des "couples" formés d'une case bi-coloriée et d'un candidat coloré ; en outre, ces solidarités ne s'appliquent pas systématiquement à tous les "couples" de même couleur ! En effet, si l'on est certain que l'un des couples "case-candidat" est "vrai" (on veut dire par là que le candidat de ce couple est la valeur de la case de ce même duo), alors on peut affirmer que :

- tous les couples de même couleur seront "vrais" à condition qu'ils soient reliés au premier couple par une suite ininterrompue de "liens forts" ;

- tous les couples de l'autre couleur seront "faux" à la même condition !

Ceci se produit notamment dans l'exemple 08f, ainsi que, partiellement, dans l'exemple 08g.

En raison de cette différence importante entre "liens forts" et "liens faibles", les enchaînements de "liens de paires" sont représentés, dans les commentaires qui accompagnent ces 2 exemples, par deux symboles distincts : le symbole "=" pour les "liens forts" et le symbole "-" pour les "liens faibles" !

exemple 08f : Le bi-coloriage de cet exemple (qui illustre le cas n° 1) repose sur le circuit de "liens forts" suivant (ici il n'y a aucun lien "faible") : Gg27 =Gh27 =Ah37 =Aj37 =Hj36 =Hh38 =Hg68 =Bg26 =Bj26 =Dj27 (sans bifurcation). Remarquons qu'on s'est interdit d'établir les liaisons Gh27 =Fh28 et Hh38 =Fh28 afin d'éviter l'incohérence d'un 2 à la case Fh qui est incompatible avec celui déjà attribué à la case Dj27 ! Cette interdiction va nous fournir une possibilité d'élimination : en effet, le candidat 2 de la case non colorée Fh qui est à la fois voisine de la case Dj27 et de la case Gh27 doit être éliminé ! On peut donc attribuer la valeur 8 à la case Fh et donc la valeur 3 à la case Hh et, de proche en proche (principe de solidarité), le 6 à Hj, le 3 à Aj, le 7 à Ah, le 2 à Gh, le 7 à Gg, et aussi le 8 à Hg, le 6 à Bg, le 2 à Bj et le 7à Dj !

exemple 08f

exemple 08g : Le bi-coloriage de cet exemple (qui illustre le cas n° 2) repose sur le circuit de "liens de paires" (ici il y a 8 "liens forts" et 4 "liens faibles") suivant : Bj27 -Be74 -De48 =Df81 =Hf18 =Hd81 =Fd14 =Fb41 =Eb17 -Eh72 , avec les trois bifurcations Eb17 =Ab74 , Eb17 =Dc74 et Fd14 -Cd42 . Remarquons qu'on s'est interdit d'établir les liaisons Df81 =Dj17 et Dc74 =Dj17 afin d'éviter l'incohérence d'un 7 à la case Dj qui est incompatible avec celui déjà attribué à la case Bj27 ! Cette interdiction va fournir une possibilité d'élimination : en effet, le candidat 7 de la case non colorée Dj qui est voisine de Bj27 et de Eh27doit être éliminé ! On peut donc attribuer la valeur 1 à la case Dj et donc la valeur 8 à la case Df (solitaire camouflé sur la ligne D) et, de proche en proche (principe de solidarité limité aux seuls "liens forts"), le 4 à De, et aussi le 1 à Hf, le 8 à Hd, le 1 à Fd, le 4 à Fb, le 1 à Eb, le 7 à Ab et le 7 à Dc !

exemple 08g

Bi-coloriage spécial sur trois cases (remarque) :
L'exemple 08g présente un autre circuit de bi-coloriage intéressant : ce petit circuit, qui est formé de deux "liens de paires" reliant 3 cases (Bj27-Be74-Cd42), permet l'élimination d'un candidat de la case (Ch247), qui est voisine à la fois de la première et de la dernière des 3 cases du circuit, car ce candidat (ici un 2) est coloré - mais avec deux couleurs opposées - , dans la première case et dans la dernière case de ce circuit ; les anglo-saxons appellent "XY-Wing" ce type assez fréquent de configuration c₁ c₂ - c₂ c₃ - c₃ c₁, où chacun des 2 liens peut être indifféremment "fort" ou "faible" !

Coloriage mixte

Le coloriage mixte est une technique de coloriage qui utilise à la fois les possibilités du coloriage simple et celles du bi-coloriage, en utilisant comme eux un seul jeu de couleurs opposées : C1|C2.

En cas de coloriage mixte, les principes d'une éventuelle élimination de candidat sont quasiment identiques à ceux du bi-coloriage ; en effet :

Si l'on détecte une case (colorée ou non) N dont l'un des candidats c est à la fois "voisin" d'un couple "case-candidat coloré" K1 de couleur C1 et "voisin" d'un couple "case-candidat coloré" K2 de couleur C2 et si, en outre, on peut être sûr que parmi les 2 couples "case-candidat" K1 et K2, l'un correspond à une hypothèse vraie tandis que l'autre correspond à une hypothèse fausse, alors le candidat c peut être effacé de la case N ! Pour être certain que l'un des couples est "vrai" tandis que l'autre est "faux", il faut, dans l'examen du cheminement qui relie les couples K1 et K2, s'intéresser à chacun des tronçons qui ne comportent que des "liens de paires" et repérer si, pour chacun d'entre eux, l'on est dans l'une des trois circonstances suivantes : - cas n° 1 : tous les liens de ce tronçon sont des "liens forts" ; - cas n° 2 : dans la suite ordonnée des n candidats communs de ce tronçon, on ne trouve jamais 2 fois de suite le même candidat ; - cas n° 3 : chacun des éventuels sous-tronçons (de ce tronçon) dont les liens sont tous des "liens faibles" fait intervenir une suite ordonnée de candidats communs dans laquelle on ne trouve jamais 2 fois de suite le même candidat (le cas n° 3 est une sorte d' "hybride" des 2 précédents et représente en fait le cas général).

exemple 08h : Le coloriage mixte de cet exemple est basé sur le circuit suivant : Fa13=Fd23/Fd3~Dd3 avec une bifurcation Fa13/Fa1~Ff1~Df1 Le couple Df2 est à la fois "voisin" de Df1 et "voisin" de Fd2 et l'on est certain que Df1 et Fd2 sont "antagonistes" puisque les liens de paires mis en œuvre dans le circuit sont tous des "liens forts" (cas n° 1) : Df2 correspond donc à une hypothèse fausse et l'on peut éliminer le candidat 2 de la case Df (la suite de la résolution est plus délicate ...)

exemple 08h

Remarques :

- Voisinage entre deux couples "case-candidat" : la notion de "voisinage" est plus subtile dans le cas de 2 couples "case-candidat" que dans le cas de 2 cases "entières" (qu'elles soient colorées ou non colorées). Elle est destinée à déceler l'éventuelle "incompatibilité" entre chacune des hypothèses représentées par ces 2 couples, l' "incompatibilité" étant l'impossibilité pour ces 2 hypothèses d'être vraies toutes les deux (2 hypothèses incompatibles peuvent être fausses toutes les deux). Le voisinage éventuel (et donc l' "incompatibilité" correspondante) entre 2 couples "case-candidat" n'est établi (et ne doit donc être examiné) que dans chacune des circonstances suivantes : - les 2 candidats de ces 2 couples sont identiques et les 2 cases qui contiennent ces couples sont différents et "voisines" (au sens que nous avons donné à la notion de "voisinage" entre cases) ; - les 2 cases qui contiennent ces 2 couples sont identiques et les 2 candidats de ces couples sont différents ! Autrement dit, deux couples "case-candidat" différents sont "voisins" s'ils ont, soit même case, soit même candidat et même région ; et s'ils sont "voisins", ils représentent des hypothèses "incompatibles" ! - un circuit "mixte" présente au moins une case "charnière", c'est-à-dire une case présentant d'un côté un lien "simple" (pour l'un de ses candidats) et de l'autre un "lien de paire" ; ceci n'est possible que si la case n'a que 2 candidats (paire) (dans l'exemple ci-dessus, on a 2 cases-charnières, la case Fa et la case Fd) ; - il peut arriver qu'un couple soit "voisin" d'un autre couple situé sur la même case (c'est le cas du couple Df1/Df2 de l'exemple ci-dessus) ; - il peut arriver qu'une case portant une paire de candidats soit une "double charnière", quand elle relie deux liens "simples" relatifs à des candidats différents (l'exemple ci-dessus ne comporte pas une telle case).

On pourra trouver, au chapitre suivant consacré au coloriage généralisé, deux autres exemples de coloriage mixte :

- le circuit C1|C2 de l'exemple 08i et

- le circuit C3|C4 de l'exemple 08j !

Coloriage généralisé

Le coloriage généralisé est une combinaison de toutes les techniques de coloriage et peut en utiliser toutes les possibilités (mode de coloriage et possibilité d'élimination), sauf la prise en compte des "liens faibles".
À la différence du coloriage simple, du bi-coloriage ou du coloriage mixte, il met en œuvre, comme le coloriage multiple, au moins deux jeux distincts de couleurs opposées : C1|C2, C3|C4, C5|C6, C7|C8, etc ...
À la différence du bi-coloriage et du coloriage mixte, les circuits d'un coloriage généralisé excluent tout lien de paires "faible" !

Elimination de candidat :

- Le principe utilisé pour l'élimination d'un candidat dans le cas d'un coloriage multiple est utilisable dans un coloriage généralisé, avec toutefois deux petites différence dues au fait que l'on travaille en général sur plusieurs candidats à la fois :

- la notion de "voisinage" ordinaire entre cases doit être remplacée par celle de "voisinage" entre couples "case-candidat"

- en outre il peut arriver qu'un couple soit "voisin" d'un autre couple situé sur la même case (c'est le cas des couples Gd2/Gd5 de l'exemple 08i et des couples Aa7/Aa8 de l'exemple 08j ; voir ces 2 exemples ci-dessous) ;

- Lorsque le coloriage utilise n jeux de couleurs opposées, le raisonnement qui permet une élimination de candidat met en jeu, en principe, des cases colorées qui font intervenir l'ensemble de ces n jeux de couleurs ; aussi, dès que n dépasse 2 (comme dans l'exemple 08j ci-dessous), le raisonnement est délicat à établir avec rigueur et il l'est d'autant plus que n est plus grand ...

Pour le faire comprendre, le plus simple est de présenter dès maintenant les deux exemples annoncés :

Premier exemple

Le premier exemple qui suit (exemple 08i) est un exemple complexe repose sur deux circuits ; le premier circuit, basé sur le couple de couleurs opposées C1|C2, est un circuit "mixte" constitué à la fois de "liens simples" et de "liens de paire", puisqu'il comprend successivement un lien "simple" (candidat 2), puis un lien de paire et enfin une série de quatre "liens simples" (candidat 2) : Ee2~Ej2/Ej25=Dj25/Dj2~ Dd2~Ee2~He2~Gd2, avec une bifurcation ("lien simple" pour le candidat 5) Ej25/Ej5~Ea5 ; le second circuit, basé sur le couple de couleurs opposées C3|C4, est un circuit "pur" constitué exclusivement, et pour le candidat 5, de liens "simples" Gd5~Gc5~Ja5~Je5~Ce5~Cd5 avec une bifurcation Gc5~Dc5.
La case Gd25 appartient à la fois au premier et au second circuit !

exemple 08i : On remarque que les 2 couples "case-candidat" Dc5 et Gd5 sont "solidaires" (même couleur) et respectivement "<A HREF="#vsn">voisins</A>" des couples "antagonistes" Ea5 et Gd2 (couleurs opposées). Par conséquent, ces deux couples Dc5 et Gd5, ainsi que les autres couples équivalents (Ja5 et Ce5) correspondent à une "hypothèse fausse" : on doit donc retirer le candidat 5 à la case Ce qui prend donc la valeur 7 (solitaire nu) et le même candidat 5 aux cases Dc, Gd et Ja (dont la valeur reste pour l'instant encore indéterminée).

exemple 08i

nota : dans l'image ci-dessus, les candidats inscrits sont déjà, contrairement à l'habitude prise pour les autres images, le résultat d'éliminations particulières (basées successivement sur un quatuor nu incomplet 2578 dans le pavé Zy, une coloration simple du candidat 2, la dominance du pavé Yz sur la colonne j pour le candidat 2, et enfin une paire nue 68 en colonne j et dans le pavé Zz) !

---

Second exemple
Le second exemple complexe ci-dessous (exemple 08j) repose sur trois circuits indépendants : le premier circuit, basé sur le couple de couleurs opposées C1|C2, est un circuit de 4 "liens simples", le second, basé sur le couple de couleurs opposées C3|C4, est un circuit "mixte" formé de "liens simples" et de "liens forts", enfin le dernier circuit, basé sur le couple de couleurs opposées C5|C6 est un circuit de 2 "liens simples" ; le cheminement du premier circuit s'écrit Da7~Aa7~Ab7~Db7 avec une bifurcation Ab7/Ab17/Ab1~Gb1 (remarquer comment la paire 17 de la case Ab lui permet de jouer un rôle de double charnière entre 2 liens simples portant sur 2 candidats différents), celui du second circuit s'écrit Hc58=He58=Ge15/Ge5~Ga5~Ea5~Ec5 avec une bifurcation He58=Je18 et celui du troisième s'écrit Ac18/Ac8~Aa8~Ja8
La case Aa78 appartient à la fois au premier et au second circuit !

exemple 08j : Le couple "case-candidat" Ge1 est "voisin" du couple Gb1, tandis que le couple Je8 (solidaire de Ge1) est "voisin" du couple Ja8 : donc si l'hypothèse C3 était vraie, elle entraînerait que C1 et C5 seraient toutes deux des "hypothèses fausses". Or, à la case Aa, les couples "voisins" Aa7 et Aa8 montrent que les couleurs C2 et C6 sont incompatibles et donc qu'au moins l'une des couleurs C1 et C5 correspond à une hypothèse vraie. Ceci n'est possible que si la couleur C3 correspond à une hypothèse fausse : on peut donc affirmer que l'hypothèse C4 est vraie ! On peut donc attribuer un 8 à la case He, un 5 aux cases Ea, Ge et Hc et un 1 à la case Je.

exemple 08j

nota : dans l'image ci-dessus, les candidats qui figurent sont déjà, contrairement à l'habitude prise pour les autres images, le résultat d'éliminations particulières (basées successivement sur une paire nue 67 sur la ligne H et la dominance du pavé Yy sur la colonne e pour le candidat 6) !

---

Terminons par quelques commentaires généraux :

- un coloriage généralisé utilise toujours plusieurs (au moins deux) jeux de couleurs opposées : C1|C2, C3|C4, C5|C6, C7|C8, etc ...

- à chaque jeu de couleurs correspond un "circuit", c'est-à-dire un enchaînement de liens ; et réciproquement, chaque circuit ne met en œuvre qu'un seul jeu de 2 couleurs, et ce jeu lui est propre ;

- un circuit n'est pas nécessairement "pur", c'est-à-dire constitué de liens de même nature ; il peut au contraire être "mixte", c'est-à-dire combiner à la fois des liens "simples" ("~") et des "liens (de paire) forts" ("=") ;

- un circuit "mixte" présente au moins une case "charnière", c'est-à-dire une case présentant d'un côté un lien "simple" (pour l'un de ses candidats) et de l'autre un "lien de paire" ; ceci n'est possible que si la case n'a que 2 candidats (paire) ;

- il arrive qu'une case portant une paire de candidats soit une "double charnière", quand elle relie deux liens "simples" relatifs à des candidats différents (c'est le cas de la case Ab de l'exemple 08j) ;

- il est assez fréquent qu'une case soit à cheval sur deux circuits distincts (c'est le cas de la case Gd de l'exemple 08i et de la case Aa de l'exemple 08j).

Glossaire

A   B   C   D   E   F   G   H   I   J   K   L   M N   O   P   Q   R   S   T   U   V  W  X   Y    Z

antagonistes	se dit de 2 couples "case-candidat" (généralement colorés) qui ont des statuts contraires : l'affirmation "le candidat de l'un des couples est la valeur de la case du même couple" est vraie pour l'un des couples et elle est fausse pour l'autre couple !
bloc	ensemble de 3 pavés contigus. Il existe 3 blocs horizontaux (X, Y et Z) et trois blocs verticaux (x, y et z). Les blocs horizontaux comprennent 3 lignes ; les blocs horizontaux comprennent 3 colonnes
camouflé	qualificatif s'appliquant, dans une région, à un "solitaire" ou à un "groupe" (paire, trio ou quatuor) ; un groupe de n candidats est "camouflé" si, dans la région considérée, il existe un sous-ensemble de n cases tel que ces cases présentent toutes l'ensemble de ces n candidats, qu'au moins l'une d'entre elles présentent au moins un autre candidat et que les autres cases de la région ne présentent aucun de ces n candidats ; l'adjectif contraire de "camouflé" est "nu"
candidat	chiffre qui, à un moment donné de l'avancement de la résolution du problème, est susceptible d'être, parmi d'autres, la valeur (encore indéterminée) d'une case donnée encore non "résolue"
coloriage	technique qui consiste à colorier un certain nombre de couples "case-candidat" de façon que, dans la mesure du possible, tous les couples dotés de la même couleur soient "solidaires" deux à deux
couple "case-candidat"	association d'une case et d'un candidat : l'existence d'un couple "case-candidat" signifie que ce candidat fait partie des candidats de cette case ; à un couple correspond une hypothèse : celle-ci est "vraie" si le candidat est la valeur de cette case, et elle est "fausse" dans le cas contraire ! Par extension, on peut dire d'un couple qu'il est "vrai" ou qu'il est "faux" ! Deux couples case-candidat peuvent notamment être "solidaires", "antagonistes" ou "incompatibles" (et donc "voisins")
étape	dans une grille à résoudre, il y a autant d'étapes que de valeurs inconnues à découvrir ; avancer d'une étape dans la résolution d'un sudoku consiste donc à trouver (par raisonnement) la valeur d'une case encore non résolue. Une étape peut comporter plusieurs sous-étapes, chacune d'elle consistant à éliminer au moins un candidat de l'une des cases de la grille.
groupe	ensemble de n candidats présents dans les listes de "candidats" des cases d'une même région et présentant une certaine particularité ; un groupe peut être "nu" ou "camouflé". Selon la valeur de n, on parle de paire, de trio ou de quatuor
incompatibles	se dit des hypothèses correspondant à deux couples "case-candidat", quand on peut affirmer que l'une (au moins) de ces deux hypothèses est fausse. Par extension, on peut parler de couples "incompatibles" ; deux couples "voisins" sont toujours "incompatibles"
lien	présence d'une relation spéciale entre 2 cases "voisines" ; un lien peut être "simple", "fort" ou "faible"
lien de paires	"lien fort" ou "lien faible"
lien faible	présence dans une même région de deux cases possédant chacune deux candidats - et deux seulement -, l'un de ces candidats (au moins) étant commun aux deux cases, ce candidat pouvant aussi appartenir à une (ou plusieurs) autre case de la même région
lien fort	présence dans une même région de deux cases possédant chacune deux candidats - et deux seulement -, l'un de ces candidats (au moins) étant à la fois commun aux deux cases et propre à ces deux seules cases (aucune autre case de la région ne le possède)
lien simple	pour un "candidat" donné, présence dans une même région de deux cases - et deux seulement - possédant ce candidat
mince	voir "région"
nu	qualificatif s'appliquant, dans une "région", à un "solitaire" ou à un "groupe" (paire, trio ou quatuor) ; un groupe de n candidats est "nu" si, dans la région considérée, il existe un sous-ensemble de n cases tel que ces cases présentent toutes exactement n candidats, que ces candidats sont exactement ceux du "groupe" et que les autres cases de la région ne présentent aucun de ces n candidats ; l'adjectif contraire de "nu" est "camouflé"
paire	"groupe" de 2 candidats présents dans les listes de "candidats" des cases d'une même région (voir "groupe" et aussi "lien de paires")
pavé	"région" carrée de 3x3=9 cases, situées à l'intersection de 2 blocs et donc disposées sur 3 lignes et 3 colonnes contiguës
quatuor	"groupe" de 4 candidats présents dans les listes de "candidats" des cases d'une même région
région	mot générique qui désigne indifféremment une ligne, une colonne ou un pavé de 9 cases ; une région est dite mince si elle désigne une ligne ou une colonne (mais pas un pavé)
réseau	ensemble de n lignes et de n colonnes dont les cases situées aux intersections de ces lignes et de ces colonnes possèdent une certaine particularité
résolue	se dit d'une case dont on connaît la valeur (on dit aussi "remplie")
solidaires	se dit de 2 couples "case-candidat" (généralement colorés) qui ont le même "statut" : ou bien l'affirmation "le candidat d'un couple est la valeur de la case du même couple" est vraie pour ces 2 couples, ou bien elle est fausse pour les 2 couples !
solitaire	se dit d'un "candidat" tel que, dans une certaine région, il n'existe qu'une seule case qui présente ce "candidat". Un candidat solitaire peut être "nu" ou "camouflé", selon qu'il est ou non le seul candidat de cette case. Si pour un certain candidat, une case présente un solitaire, nu ou camouflé, ce candidat ne peut être que la "valeur" de cette case
trio	"groupe" de 3 candidats présents dans les listes de "candidats" des cases d'une même région
valeur	chiffre qui correspond au contenu d'une case. Une valeur peut être, soit initiale (si elle fait partie des données du problème), soit déduite (si on l'a trouvée par raisonnement). Si à un moment donné, la valeur est encore indéterminée, les chiffres possibles à cet instant s'appellent les "candidats" de cette case
voisinage	le voisinage d'une case est constitué par l'ensemble des 20 cases "voisines" de cette case (voir définition suivante) ; on peut aussi parler de "voisinage" à propos de couples "case-candidat"
voisines	se dit de deux cases qui appartiennent à une même région (ligne, colonne ou pavé). Exemple : les cases Eh, Jd et Ff sont toutes des "voisines" de la case Ed, alors que Dc n'est pas une "voisine" de Ed
voisins	se dit de deux couples "case-candidat" distincts qui ont, soit la même case, soit même candidat et même région (cases "voisines") ; les hypothèses correspondant à deux couples "voisins" sont "incompatibles"

Petit lexique franco-anglais

bi-coloriage ⇔ forcing chains bi-coloriage ⇔ XY-Chains bi-coloriage "spécial" sur 3 cases ⇔ XY-Wing bloc ⇔ block camouflé ⇔ hidden candidat ⇔ candidate case ⇔ cell colonne ⇔ column coloriage généralisé ⇔ 3D - Medusa coloriage multiple ⇔ multi-colouring coloriage simple ⇔ simple colouring groupe ⇔ subset ligne ⇔ row nu ⇔ naked paire ⇔ pair pavé ⇔ box (ou parfois block) quatuor ⇔ quad région ⇔ group régions dominantes ⇔ interactions régions dominantes ⇔ locked candidates réseau-II ⇔ X-Wing réseau-III ⇔ swordfish réseau-IV ⇔ jellyfish solitaire ⇔ single trio ⇔ triple

3D - Medusa ⇔ coloriage généralisé block ⇔ bloc (ou parfois pavé) box ⇔ pavé candidate ⇔ candidat cell ⇔ case column ⇔ colonne forcing chains ⇔ bi-coloriage group ⇔ région hidden ⇔ camouflé interactions ⇔ régions dominantes jellyfish ⇔ réseau-IV locked candidates ⇔ régions dominantes multi-colouring ⇔ coloriage multiple naked ⇔ nu pair ⇔ paire quad ⇔ quatuor row ⇔ ligne simple colouring ⇔ coloriage simple single ⇔ solitaire subset ⇔ groupe swordfish ⇔ réseau-III triple ⇔ trio X-Wing ⇔ réseau-II XY-Chains ⇔ bi-coloriage XY-Wing ⇔ bi-coloriage "spécial" sur 3 cases