X-wing (Sudoku)
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[modifier | modifier le code]
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[modifier | modifier le code]
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.
Deuxième étape[modifier | modifier le code]
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.
On inverse la situation avec le 9 à droite et on observe le même résultat, mais inversé.
Troisième étape[modifier | modifier le code]
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.
Voir aussi[modifier | modifier le code]
- Technique du Swordfish
