X-wing (Sudoku)

Un article de Wikipédia, l'encyclopédie libre.

La méthode X-Wing est une technique de résolution de Sudoku. Son nom provient des X-wing de la Guerre des étoiles, le X fait référence à la disposition des cases testées lors de l'application de cette méthode.

Sommaire

1 Principe
2 Voir aussi

[modifier] Principe

Cette méthode permet d'éliminer des candidats potentiels dans plusieurs cases. Pour l'appliquer, l'une des deux conditions suivantes doit être remplie :

on doit avoir deux lignes distinctes qui partagent la même valeur candidate dans les deux (et uniquement deux) mêmes colonnes.
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.

[modifier] Première étape

La première consiste à identifier des cases satisfaisant les contraintes. Dans l'exemple ci-contre, 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 »

[modifier] 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 alternative

On inverse la situation avec le 9 à droite et on observe le même résultat, mais inversé.

Deuxième alternative

[modifier] 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és les quatre cases utilisées pour l'analyse) est incompatible avec les règles du Sudoku. On peut donc éliminer les « 9 » impossibles.