Sudoku/Sudolettres

 
 

Tactique : Analyse

Les deux thèmes de ce procédé sont l'élimination et l'hypothèse (ce dernier procédé peut être évité si l'on est suffisamment entraîné).

Approche par Élimination

Élimination : la recherche de la solution se fait en éliminant successivement les candidats d'une cellule de façon à ne retenir qu'un seul candidat. Une fois ce candidat trouvé, une autre recherche devrait être effectuée de façon à déterminer les conséquences sur les autres cellules. Il y a plusieurs techniques d'élimination qui s'appuient sur les règles ci-dessous, lesquelles ont d'utiles corollaires :

  1. Un ensemble donné de n cellules dans une rangée, une colonne ou une région, ne peut recevoir que n chiffres différents. Cette règle est à la base de la technique d' « élimination du candidat orphelin », discutée ci-dessous.
  2. Chaque candidat doit ultimement appartenir à un modèle auto-consistant et indépendant. Cette règle est à la base des techniques d'analyse avancées, lesquelles demandent d'inspecter l'ensemble de toutes les possibilités pour un candidat. Il n'y a qu'un nombre fini de « circuits fermés » ou possibilités de grilles « n×n » qui existent. Cette règle a donné naissance aux méthodes X-wing et Swordfish, entre autres. Si un tel modèle est identifié, alors l'élimination de candidats est souvent possible.
  3. Un chiffre donné ne peut recevoir qu'une seule position dans sa case, ligne ou colonne, les autres emplacements candidats entrant en contradiction avec les éliminations déjà effectuées.

L'une des techniques les plus utilisées est l' « élimination du candidat orphelin ». Les cellules avec un même ensemble de candidats sont dites couplées si le nombre de candidats dans chacune d'elle est égal au nombre de cellules qui peuvent les accueillir. Par exemple, deux cellules sont couplées si elles contiennent une paire unique de candidats (p, q) dans une rangée, une colonne ou une région; trois cellules sont dites couplées si elles contiennent un triplet unique de candidats (p, q, r). Ces chiffres ne peuvent apparaître ailleurs, car il y aurait conflit selon la rangée, la colonne ou la région. Pour cette raison, les candidats (p, q, r) qui se trouvent dans les autres cellules sont à éliminer. Ce principe vaut avec des sous-ensembles de candidats : si trois cellules ont seulement { (p, q, r), (p, q), (q, r) }, ou { (p, r), (q, r), (p, q) }, tous les candidats de cet ensemble qui se trouvent dans les autres cellules sont à éliminer.

Un deuxième principe découle du principe précédent. Si le nombre de cellules dans une rangée, une colonne ou une région, est égal à la taille d'un ensemble de candidats (on parle alors de groupe de multiples numériquement liés), les cellules et les chiffres sont couplés et seulement ces chiffres apparaîtront dans les cellules. Tous les autres candidats sont à éliminer. Par exemple, si (p, q) peut seulement apparaître dans deux cellules (d'une rangée, d'une colonne ou d'une région), les autres candidats sont à éliminer.

Le premier principe s'appuie sur le concept de « chiffres couplés uniquement », alors que le second s'appuie sur le concept de « cellules couplées uniquement ». Les techniques avancées s'appuient sur ces concepts et englobent de multiples rangées, de multiples colonnes et de multiples régions.


Approche par hypothèse

Une cellule avec seulement deux candidats est choisie et l'un des deux chiffres est inscrit dans la cellule. Les étapes précédentes sont répétées et mènent soit à une contradiction (chiffre dupliqué ou cellule sans candidat), soit à une proposition valide. Évidemment, dans le cas d'une contradiction, le deuxième chiffre fait partie de la solution. L'algorithme de Nishio est une forme épurée de cette approche : Pour chaque candidat d'une cellule, est-ce qu'insérer un chiffre en particulier prévient l'inscription de ce candidat ailleurs dans la grille ? Si la réponse est oui, alors le candidat est éliminé.

L'approche par hypothèse demande d'utiliser un crayon et une gomme à effacer. Les puristes la rejettent, car elle est une approche par essais et erreurs, alors que la plupart des grilles publiées font appel à la logique seulement pour être résolues. Cependant, cette approche a le mérite de souvent mener à la solution plus rapidement.

C'est à chaque joueur de trouver une méthode qui lui donne les meilleurs résultats. Certains développeront une méthode qui réduit les inconvénients des propositions précédentes. Par exemple, certains trouveront ennuyeux de devoir inscrire tous les candidats dans toutes les cellules. L'approche par hypothèse demande d'être organisé. L'idéal est de trouver une façon de faire qui minimise le décompte, le nombre de candidats et le nombre d'hypothèses.

En principe, ces trois procédés (candidat unique par croisement+candidat unique par comptage et élimination+groupes indépendants de multiples numériquement liés traités selon une ou plusieurs dimensions) suffisent pour réussir intégralement une grille. Mais il y a des situations où il semble qu’il n’est plus possible d’avancer. Voici un début d’exemple :

Vous avez trouvé à partir des chiffres déjà révélés selon les régions et les colonnes, les multiples 123-12-1456-479-23-56-2456-178-89 écrits sur toute une ligne pour une certaine grille. D’abord, on relève les 123, 12 et 23 numériquement liés ; trois multiples formés des trois chiffres 1, 2 et 3, qui vont occuper chacun l’une des trois cases. Donc la ligne se simplifie en 123-12-456-479-23-56-456-78-89. Ensuite, on considère les multiples 456, 56 et 456 qui sont aussi numériquement liés, mais leur groupe est indépendant de celui des multiples formés à la base des chiffres 1, 2 et 3.Pour la même raison, la ligne se simplifie en 123-12-456-79-23-56-456-78-89. Il reste donc trois multiples 79, 78 et 89 qui sont numériquement liés, mais constituent un troisième groupe indépendant des deux premiers. À ce niveau, on dira que l’on a rempli la ligne de façon optimale. Les simplifications ainsi effectuées vont se répercuter sur les régions, les colonnes puis sur les autres lignes puis de nouveau sur les régions, les colonnes et les lignes si l’on arrive à dégager chaque fois, de nouveaux groupes indépendants. S’il reste toujours des cases sans candidat unique, alors, on pourra attaquer par traitement des multiples en considérant deux dimensions à la fois; colonnes X lignes (principe de l'unicité, X-Wing par exemple), colonnes X régions (doublons, jumeaux par exemple), lignes X régions (idem). Si la solution n'apparaît pas toujours, alors, désormais, vous êtes invité à utiliser les techniques de traitement à trois dimensions (lignes X colonnes X régions) dont par exemple, celles découlant de l'utilisation des chemins (théorie basée sur la logique bivalente; il y est ou il n'y est pas).

Et si votre labeur n'aboutit pas toujours à la grille-solution, alors, c’est à cause de l’une des deux raisons suivantes :
  • Vous vous êtes bien appliqué et vous avez rempli entièrement la grille de façon optimale par des chiffres uniques dans certaines cases et par des multiples dans les autres. Mais, tous les groupes des multiples que vous avez inscrits sont indépendants. Dans ce cas, Vous avez affaire à une grille présentant plusieurs solutions ! Ce n’est pas un « bon » Su-Doku et le problème ne devait pas être proposé, malheureusement !
  • Toutes les cases de votre grille ont des candidats uniques ou multiples, mais, faute d’expérience, vous n’arrivez pas à discerner facilement des groupes indépendants de multiples numériquement liés. Dans ce cas, vous pouvez procéder par la disjonction de l’un des multiples. C’est-à-dire faire une hypothèse sur ses chiffres, et voir l’effet qui va se répercuter sur les autres multiples. Si vous avez vraiment un « bon » jeu de Su-Doku, alors un seul chiffre du multiple en question conduira à la solution du problème, tandis que pour tous les autres, on aboutira à des situations de blocage ! Dans le cas contraire, le problème ne mérite pas d’être posé ! Par principe !

Mais le fait de formuler une hypothèse sur le chiffre à choisir parmi ceux d'un multiple donné ne garantit pas toujours la simplification des autres multiples et risque d'aboutir sur de nouvelles hypothèses à faire, ce qui augmente rapidement le nombre de grilles à examiner successivement! Pire encore, les grilles obtenues peuvent être d'un niveau médiocre et donc sans intérêt intellectuel!

Retour menu Tactiques