X-Wing
lundi 6 août 2007
par fj
Le X-Wing est une technique d’élimination de candidats. Un X-Wing permet d’effectuer un placement définitif uniquement si la case concernée ne contient que deux candidats et que l’un d’eux est justement le candidat concerné par le X-Wing.

Un X-Wing demande :

  • un candidat bien identifié,
  • quatre cases formant un X et contenant le candidat,
  • une présence limitée du candidat (en deux exemplaires seulements), soit dans les deux colonnes (X-Wing de colonne) contenant les quatre cases, soit dans les deux lignes (X-Wing de ligne).

L’effet du X-Wing est simple : suppression du candidat dans les lignes (cas d’un X-Wing de colonne) ou dans les colonnes (X-Wing de ligne) contenant les quatres cases, à l’exception de ces quatres cases évidemment.

La difficulté principale d’un X-Wing est sa détection. Il existe une technique de marquage permettant de repérer à coup sûr tous les X-Wing présents dans un diagramme entièrement rempli de listes de candidats : Marques à distance.

Mais contrairement à ce que beaucoup de joueurs de SUDOKU pensent, il est parfaitement possible (et particulièrement efficace) de détecter un X-Wng de manière très précoce bien avant que toutes les cases ne soient remplies.

A noter que le X-Wing situé dans un alignement est assez fréquent. Il fait alors partie de la famille plus générale des Swing (un Swing peut ne pas être un X-wing). Un simple marquage de proximité suffit pour le détecter facilement.

Exemple extrème d’un X-Wing détecté dès la position initiale

Voici un diagramme initial de SUDOKU (d’un niveau 3-4). Appliquons lui une méthode de balayage du 1 (on raye toutes les positions interdites) :

Tout d’abors, la technique de balayage donne immédiatement un placement en région centrale :

Mais il fait aussi apparaître un X-Wing colonne :

En effet, il n’y a que deux 1 en colonnes A et I et ces 1 se trouvent dans les mêmes lignes 1 et 9. L’effet du X-Wing est le suivant :

Et ce n’est pas fini ! Un second X-Wing "colonne" apparaît soudain (B et G) :

Avec comme effet :

Ceci dit, j’ai résolu facilement ce SUDOKU sans utiliser les X-Wing : il est en effet suffisamment simple pour que la stratégie de base suffise (recherche des marques de choix puis approche globale alternée avec le report des marques).

X-wing de colonne

X-wing de ligne