La méthode X-Wing est une technique de résolution de Sudoku. Son nom provient des X-wing de Star Wars, le X fait référence à la disposition des cases testées lors de l'application de cette méthode.
Principe
Cette méthode repose sur une règle de base du sudoku : si un nombre figure dans une case, il ne figure dans aucune autre case de la même rangée (ligne ou colonne), et on peut donc éliminer sa candidature dans ces cases. Cela s'applique encore si on ne connait pas précisément la case où figure le nombre, et le « X-wing » s'applique à un tel cas dans une des deux conditions suivantes :
on doit avoir deux lignes distinctes qui partagent la même valeur candidate dans les deux (et uniquement deux) mêmes colonnes.
OU
on doit avoir deux colonnes distinctes qui partagent la même valeur candidate dans les deux (et uniquement deux) mêmes lignes.
Par disjonction des cas, il est possible d'éliminer des candidats qui apparaissent sur les bords du rectangle formé par les intersections entre ces lignes et ces colonnes.
Première étape
La première étape consiste à identifier des cases satisfaisant les contraintes. Dans l'exemple ci-dessous, la deuxième contrainte est satisfaite.
Nous avons le chiffre 9 qui est un candidat dans deux colonnes distinctes, qui sont partagées par deux lignes distinctes. Aucune autre ligne n'a comme candidat le chiffre 9 dans la première et dernière colonne.
Première étape : identification du "X-Wing", un rectangle formé ici par les quatre « 9 »
Deuxième étape
La deuxième étape repose sur le constat que si l'on choisit le chiffre « 9 » pour la case en haut à gauche, alors la case en haut à droite ne peut être un « 9 » en vertu des règles du Sudoku. De même pour la case en bas à gauche. On sait ainsi que les candidats « 9 » sont impossibles sur la ligne du haut et la colonne de gauche. Comme la case en bas à droite contient soit un 9 ou un 8, on sait que le 9 est obligatoirement dans cette case.
Première solution
On inverse la situation avec le 9 à droite et on observe le même résultat, mais inversé.
Deuxième solution
Troisième étape
Dans les deux situations possibles, la présence d'un « 9 » sur les lignes et les colonnes qui se trouvent sur les bords du rectangle (excepté les quatre cases utilisées pour l'analyse) est incompatible avec les règles du Sudoku. On peut donc éliminer les « 9 » impossibles.
