Résolution de casse-têtes/Résolution du sudoku
L'animation (cases avec fond jaune) reproduit le déroulement chronologique de la solution
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.
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
[modifier | modifier le wikicode]La grille ci-dessous est un exemple de sudoku d'un niveau de difficulté assez grand ...
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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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) :
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
[modifier | modifier le wikicode]• 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é
[modifier | modifier le wikicode]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 :
|
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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode](ou recherche d'un candidat "solitaire camouflé") On procède en quatre temps :
|
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 : ici on travaille dans les lignes A et B du bloc X, et avec la colonne g |
 |
... 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 |
 |
... 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 |
 |
Recherche des valeurs uniques
[modifier | modifier le wikicode](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 :
|
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). |
 |
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 : |
 |
Élimination indirecte
[modifier | modifier le wikicode]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 :
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 !
|
Voici un second exemple (pour lequel on a seulement illustré l'étape b) :
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 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 !
|
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
[modifier | modifier le wikicode]
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
[modifier | modifier le wikicode]
Pour ce faire, il faut, pour chaque case examinée, procéder en trois temps :
|
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 : |
 |
candidats de l'exemple 01b : |
 |
candidats de l'exemple 01c : |
 |
candidats de l'exemple 02a : |
 |
Régions dominantes
[modifier | modifier le wikicode]
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 : |
 |
exemple 04b : |
 |
Groupes nus
[modifier | modifier le wikicode]
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). |
Voici quelques exemples :
exemple 05a : |
 |
exemple 05b : 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 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 05c : 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 05d : |
 |
exemple 05e : |
 |
Groupes camouflés
[modifier | modifier le wikicode]
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 :
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) !
|
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 : 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 06b : 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) ! |
 |
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
[modifier | modifier le wikicode]
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
[modifier | modifier le wikicode]
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). |
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 : |
 |
exemple 07b : |
 |
exemple 07c : |
 |
Techniques basées sur le coloriage
[modifier | modifier le wikicode]
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
[modifier | modifier le wikicode]Les différentes techniques
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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.
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 !
|
Jeux de couleurs
[modifier | modifier le wikicode]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)
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.
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
[modifier | modifier le wikicode]|
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". |
Principe d'élimination
[modifier | modifier le wikicode]|
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. |
Tableau comparatif des différentes techniques de coloriage
[modifier | modifier le wikicode]
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
[modifier | modifier le wikicode]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 :
|
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 :
|
Élimination de candidat
[modifier | modifier le wikicode]
|
Remarques :
|
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 : |
 |
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 : |
 |
exemple 08d : |
 |
Coloriage multiple
[modifier | modifier le wikicode]
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 : |
 |
- 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
[modifier | modifier le wikicode]
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 ! |
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 : |
 |
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
c1
c2
-
c2
c3
-
c3
c1, où chacun des 2 liens peut être indifféremment "fort" ou "faible" !
Coloriage mixte
[modifier | modifier le wikicode]
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 :
|
exemple 08h : |
 |
Remarques :
|
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é
[modifier | modifier le wikicode]
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) ;
- - la notion de "voisinage" ordinaire entre cases doit être remplacée par celle de "voisinage" entre couples "case-candidat"
- - 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 : |
 |
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 : |
 |
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
[modifier | modifier le wikicode]| 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
[modifier | modifier le wikicode]
|
|