Technique Chaîne XY au sudoku

Une chaîne XY est une suite de cases à deux candidats, chacune voyant la suivante, disposées de sorte que le même chiffre se trouve aux deux extrémités. L'une de ces deux extrémités doit contenir ce chiffre, donc toute case qui voit les deux extrémités peut le perdre.

Le principe du motif

Une case bivaluée est une case qui n'a plus que deux candidats. C'est un interrupteur : écartez un chiffre et l'autre est forcé. Alignez ces interrupteurs et la contrainte se propage.

Partez d'une case contenant {z,a}. Sa voisine contient {a,b} et la voit. La suivante contient {b,c} et voit la précédente, et ainsi de suite, jusqu'à ce que la dernière case contienne {y,z}, revenant au chiffre du départ. Chaque case partage son chiffre de liaison avec la case précédente et transmet un nouveau chiffre vers l'avant.

Supposez maintenant que la première case ne soit pas z. Alors elle vaut a, donc la deuxième ne peut pas valoir a et doit valoir b, donc la troisième ne peut pas valoir b, et l'onde court jusqu'à l'autre bout, où la dernière case est forcée à z. Soit la première extrémité vaut z, soit la dernière vaut z. Il n'y a pas de troisième option, et toute case qui voit les deux extrémités perd z.

Un Y-Wing est simplement la plus courte chaîne XY utile, ce qui explique que la règle d'élimination se lise de la même façon.

Quand la chercher

• La grille est pleine de cases bivaluées et rien d'autre ne produit.
• Deux cases bivaluées éloignées partagent un chiffre, et vous voyez un chemin de cases bivaluées entre elles.
• Un chiffre semble presque se résoudre. Les chaînes sont plus efficaces sur les chiffres qui apparaissent dans de nombreuses cases à deux candidats.

Comment l'appliquer, étape par étape

1. Marquez toutes les cases bivaluées de la grille.
2. Choisissez une case de départ et prenez l'un de ses deux chiffres comme z, le chiffre que vous espérez éliminer.
3. Passez à une case bivaluée qui la voit et partage l'autre chiffre.
4. Continuez à avancer, en partageant chaque fois le chiffre transmis par la case précédente, sans jamais répéter une case.
5. Arrêtez-vous quand le second chiffre de la case courante est de nouveau z. La chaîne est fermée.
6. Supprimez z de toute case qui voit les deux cases d'extrémité.

Un exemple détaillé

Six cases bivaluées : E3 , D2 , H2 , G2 , G9 et E9 . Chacune voit la suivante, et chaque paire partage le chiffre transmis : 8 de E3 à D2 (carré 4), 3 de D2 à H2 (colonne 2), 5 de H2 à G2 (colonne 2), 7 de G2 à G9 (ligne G) et 9 de G9 à E9 (colonne 9).

Si E3 n'est pas 3, il est 8. Alors D2 est 3, H2 est 5, G2 est 7, G9 est 9 et E9 est 3. Donc E3 est 3, ou E9 est 3, ou les deux. Les extrémités sont E3 et E9, et 3 est le chiffre d'extrémité.

E6 voit les deux extrémités par la ligne E, donc le 3 est retiré de E6.

E3 et E9 partagent aussi un 3 dans la ligne E, donc la chaîne se referme en boucle. Les solveurs appellent cela un Y-cycle, et il se lit de la même façon.

Erreurs courantes

• Utiliser une case à trois candidats. Chaque maillon de la chaîne doit être strictement bivalué.
• Sauter la vérification de visibilité. Les voisines doivent partager une ligne, une colonne ou un carré, et pas seulement sembler proches.
• Éliminer dans les cases d'extrémité. Les extrémités font partie du motif et gardent leurs candidats.
• Réutiliser une case. Une chaîne qui se reboucle sur elle-même est une autre technique, avec d'autres règles.
• Finir sur le mauvais chiffre. Si la dernière case n'offre pas z, la chaîne ne prouve encore rien : prolongez-la.

Où la rencontrer

Les chaînes XY font partie de l'équipement standard du sudoku classique Expert, où les cases bivaluées abondent et où les motifs plus simples sont tous épuisés. Commencez par des chaînes de trois et quatre cases ; une fois qu'elles viennent naturellement, les plus longues ne coûtent que de la patience.