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.<BR>
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. <br>
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 ...<br><br>
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 ...
Solution finale de la grille présentée : <br>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.<br><br>
<br>
<br>
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.<br>
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):
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) :<BR><BR>
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 :
=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).
Il convient aussi de mentionner la classification suivante :
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 :
Élimination directe.
On procède en quatre temps :
Distinguons quelques types de cas :
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) :
... ensuite, un exemple particulièrement facile :
... et enfin un dernier exemple, moins immédiat :
Recherche des valeurs uniques.
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 : 
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 :
É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 :
Voici un premier exemple :
Voici un second exemple (pour lequel on a seulement illustré l'étape b) : 
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) : 
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.<br><br>
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 :
=Trois techniques élaborées=
<br>
L'ensemble des techniques élaborées se range dans trois grandes catégories :
- les régions dominantes <br><br>
- les groupes nus <br><br>
- les groupes camouflés <br><br>
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.
<br><br>
Pour pouvoir utiliser une technique élaborée, il est donc nécessaire d'identifier les candidats des cases encore non résolues.
<br><br>
Identification préalable des candidats.
<br>
<br><br>
Voici, à titre illustratif, ce que cela donne dans le cas de certains des exemples déjà rencontrés (01a, 01b, 01c et 02a) :<br><br>
<br><br>
<br>
Régions dominantes.
<br>
<br>
Les techniques basées sur la notion de région dominante sont fondées sur la généralisation
de l'évidence suivante : <BR>
<br><br>
En voici le principe. 
<BR>
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).<BR>
<BR>
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).<br>
Donnons deux exemples :<br>
<br>
<br>
Groupes nus.
<br>
Les techniques basées sur les groupes nus constituent une généralisation de la méthode de recherche des valeurs uniques ("solitaires nus").
Voici quelques exemples :<br><br>
<br>
<br>
<br>
<br>
<br>
Groupes camouflés.
<br>
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".<br> (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")<br>
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 !
<br><br>
Voici deux exemples :<br><br>
<br>
<br><br>
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=
<br>
Les techniques extrêmes n'interviennent que très exceptionnellement au début de la résolution d'un sudoku !
<br><br>
Nous ne nous intéresserons qu'aux deux catégories de techniques extrêmes les plus utiles : <br>
- les réseaux<br>
- les différentes variantes de coloriage
<br><br>
Techniques basées sur les réseaux.
<br>
Ces techniques constituent, comme les techniques (déjà vues) basées sur les régions dominantes, une généralisation de l'affirmation : <BR>
"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".<br><br>
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é).
<br>
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" !). <br>
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 :<br><br>
<br>
<br>
<br><br>
Techniques basées sur le coloriage.
<br><br>
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.
<br>
<br>
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 : <BR>
<br>
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" :<BR>
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). 
<br>
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" ...
Tableau comparatif des différentes techniques de coloriage.
<br>
Nous terminerons ces préliminaires par un petit tableau comparatif :<BR><BR>
<BR>
renvois : 
<BR><HR ALIGN="CENTER" WIDTH="40%" SIZE="1" NOSHADE>
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.<BR><BR>
Attention : <br>
Élimination de candidat.
Remarques :<br>
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 :<br><br>
<br>
<br>
Voici maintenant deux exemples dans lesquels on peut procéder à une élimination de candidat sans avoir au préalable rencontré une situation d' "interdiction" :<br>
<br>
<br><br>
Coloriage multiple.
<br><br>
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.
<br><br>
<br><br>
Elimination de candidat :
<br><br>
<br><br>
<br><br>
Bi-coloriage.
<br><br>
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".<br>
Par ailleurs, le bi-coloriage n'utilise qu'un seul jeu de couleurs opposées.<br>
<br>
Voici comment on procède :<br>
<BR>
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 :<BR>
<BR>
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 :<BR>
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 :<BR>
<br>
Bi-coloriage spécial sur trois cases (remarque) :<BR>
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 
c1
c2
c2
c3
c3
c1, où chacun des 2 liens peut être indifféremment "fort" ou "faible" !
<br><br>
Coloriage mixte.
<br><br>
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.<BR>
<BR>
En cas de coloriage mixte, les principes d'une éventuelle élimination de candidat sont quasiment identiques à ceux du bi-coloriage ; en effet :<BR>
<br><br>
Remarques :
On pourra trouver, au chapitre suivant consacré au coloriage généralisé, deux autres exemples de coloriage mixte :<BR>
<br><br>
Coloriage généralisé.
<br><br>
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".<BR>
À 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 ...<BR>
À la différence du bi-coloriage et du coloriage mixte, les circuits d'un coloriage généralisé excluent tout lien de paires "faible" !<BR>
Elimination de candidat :
<br><br>
Premier exemple<br>
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.<BR>
La case Gd25 appartient à la fois au premier et au second circuit !
<br><br>
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) !
<HR ALIGN="CENTER" WIDTH="20%" SIZE="1" NOSHADE><BR>
Second exemple<br>
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<BR>
La case Aa78 appartient à la fois au premier et au second circuit !
<br><br>
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) !
<HR ALIGN="CENTER" WIDTH="20%" SIZE="1" NOSHADE><BR>
Terminons par quelques commentaires généraux :<BR>
<br><br>
=Glossaire=
<br>
<BR>
<br>
=Petit lexique franco-anglais=