X-wing (Sudoku)

X-wing (Sudoku)

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

Sommaire

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.

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 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 »

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

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.

Élimination des « 9 » impossibles.

Voir aussi

Technique du Swordfish


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article X-wing (Sudoku) de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • X-wing (sudoku) — 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 1.1 Première… …   Wikipédia en Français

  • Sudoku — proposé par la presse. Le sudoku (prononcé soudokou en français, / …   Wikipédia en Français

  • Sudoku — (jap. 数独 Sūdoku, kurz für 数字は独身に限る Sūji wa dokushin ni kagiru, wörtlich so viel wie „Isolieren Sie die Zahlen“) ist ein Logikrätsel und ähnelt lateinischen Quadraten. In der üblichen Version ist es das Ziel, ein 9×9 Gitter mit den Ziffern 1 bis 9 …   Deutsch Wikipedia

  • Sūdoku — Sudoku (jap. 数独 Sūdoku, kurz für 数字は独身に限る Sūji wa dokushin ni kagiru, wörtlich „Eine Zahl bleibt immer allein“) ist ein Logikrätsel und ähnelt Magischen Quadraten. In der üblichen Version ist es das Ziel, ein 9×9 Gitter mit den Ziffern 1 bis 9 so …   Deutsch Wikipedia

  • X-Sudoku — Sudoku (jap. 数独 Sūdoku, kurz für 数字は独身に限る Sūji wa dokushin ni kagiru, wörtlich „Eine Zahl bleibt immer allein“) ist ein Logikrätsel und ähnelt Magischen Quadraten. In der üblichen Version ist es das Ziel, ein 9×9 Gitter mit den Ziffern 1 bis 9 so …   Deutsch Wikipedia

  • List of Sudoku terms and jargon — This is a list of Sudoku terms and jargon. List organization and conventions This list provides a brief glossary of Sudoku terminology.Items are listed thematically, and usually only once, with a brief description and possibly a link to a… …   Wikipedia

  • Swordfish (Sudoku) — La méthode swordfish est une technique de résolution de sudoku basée sur le X wing permettant l élimination de plusieurs candidats dans les grilles de niveau de difficulté élevé. Principe Pour un candidat spécifique, un swordfish est constitué… …   Wikipédia en Français

  • X-wing (disambiguation) — The term X wing may refer to:* X wing, a starfighter from the fictional Star Wars universe * , a novel series by Michael A. Stackpole and Aaron Allston * The , a series of space based flight simulators set in the Star Wars universe. The series… …   Wikipedia

  • Sodoku (jeu) — Sudoku Sudoku proposé par la presse. Le sudoku (prononcé / …   Wikipédia en Français

  • Su Doku — Sudoku Sudoku proposé par la presse. Le sudoku (prononcé / …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”