> Voyages, philatélie, mariage, loisirs créatifs...

Les techniques plus compliquées pour résoudre les Sudoku  —  Ecrit par Stephanie

Dans un précédent article, j'ai essayé d'expliquer les techniques les plus simples pour résoudre les Sudoku (Su Doku ou Soduku). Ces techniques sont indispensables pour commencer à résoudre tous les Sudoku. Mais elles ne sont pas suffisantes pour les sudoku de niveau moyen ou difficile. Pour ces derniers, il vous faudra également maîtriser les techniques des paires ou triplets cachés et la technique du X-Wing que je vais tenter d'expliquer ci-dessous. Ces techniques ne permettent pas de mettre un chiffre dans une case mais d'éliminer des indices possibles dans une ou plusieurs cases lorsqu'on a fait le recensement exhaustif de tous les indices possibles dans chaque case.
Pour les Sudoku les plus diaboliques, il vous faudra également maîtriser les techniques du Swordfish, du Coloring (ou Colouring), et des paires liées. Mais pour ces 3 techniques, personnellement, je n'arrive pas à les repérer dans un grille. Et même pire : pour le Sworfish et le colouring, je n'arrive pas à comprendre comment ces techniques fonctionnent. Alors, si vous les connaissez, n'hesitez à pas à nous aider.

Dans les grilles ci-dessous, les chiffres en noir sont les chiffres fixes ou trouvés en cours de résolution. Les chiffres écrits en petit et en bleu sont tous les chiffres possibles dans la case concernée(= indices). Les chiffres écrits en petit et en rouge sont les chiffres possibles dans la case concernée après élimination de certains chiffres par une des techniques décrites ci-dessous



Les paires cachées

Dans le grille ci dessus, tous les indices ont été notés pour la région en haut à gauche. On peut voir que les chiffres "1" et "9" n'apparaissent que dans 2 cases (cases 2 et 3 de la colonne n°1). Par conséquent, on peut en déduire que ces 2 chiffres sont forcément dans ces 2 cases et que dans ces 2 cases, les seuls chiffres possibles sont le "1" et le "9". On peut donc supprimer les autres indices possibles c'est- à-dire le "2" et le "5" dans la case 2 de la colonne n°1 et le 5 dans la case 3 de la colonne n°1

Pour généraliser, dès que vous trouvez 2 chiffres dans 2 cases d'une même région, colonne ou ligne et uniquement dans ces 2 cases, vous pouvez éliminer tous les autres chiffres possibles dans ces 2 cases.

Les triplets cachés

La technique des triplets cachés est la même que celle des paires cachées mais avec 3 chiffres au lieu de 2

Dans la grille ci-dessus, on peut voir que les chiffres "3", "6" et "7" ne se trouvent que dans 3 cases : les cases n°4, 6 et 7. Par conséquent, tous les autres chiffres que les "3", "6" et "7" peuvent être supprimés de ces 3 cases.

Pour généraliser, dès que vous trouver 3 chiffres dans 3 cases d'une même région, colonne ou ligne et uniquement dans ces cases, vous pouvez éliminer tous les autres chiffres possibles dans ces 3 cases. Attention, il n'est pas nécessaire que les 3 chiffres soient présent dans les 3 cases, il peut n'y avoir que 2 ou 1. La seule chose importante est que ces 3 chiffres ne se retrouvent pas dans d'autres cases que ces 3 cases.

X-Wing

Dans la grille ci-dessous, regardez les cases dont le fond est jaune. Ces 4 cases forment un carré, elles contiennent toutes les quatre, le chiffre "6". Et ce chiffre "6" n'apparaît dans aucune autre case des lignes 1 et 9 : lignes dans lesquelles se trouvent les 4 cases à fond jaune. Par conséquent, on peut éliminer tous les chiffres "6" qui se touvent dans les autres cases des colonnes n°6 et 9 (où se trouvent les 4 cases à fond jaune)

Prenons, la case n°6 de la ligne n°1 (fond jaune). Si le "6" se trouve dans cette case, cela veut dire qu'il n'est pas dans tout le reste de la colonne notamment dans la case 6 de la ligne n°9 (fond jaune). Si le 6 n'est pas dans cette case "6" de la ligne 9, cela veut donc dire qu'il est dans la case 9 de la ligne 9 ( fond jaune) et que par conséquent, il n'est plus dans aucune autre case de la colonne 9.
On peut donc faire le même raisonnement pour chacune des quatre cases à fond jaune

Pour généraliser, si 4 cases contenant le même chiffre forment un carré et que ce chiffre n'apparait pas sur les autres cases des 2 lignes de ce carré, on peut éliminer ce chiffre sur les autres cases des colonnes de ce carré.
De même, si 4 cases contenant le même chiffre forment un carré et que ce chiffre n'apparait pas sur les autres cases des 2 colonnes de ce carré, on peut éliminer ce chiffre sur les autres cases des lignes de ce carré.

posté le 13/11/2005 à 16:48:38 par Stephanie - Catégorie : General - Groovy programming