SUDOKU
TECHNIQUES DE SUDOKUSudoku : Les espions cachés (Hidden rectangle)
Nous reprenons ici la technique de la Danse des espions pour la compléter par la notion de liens forts que l’on rencontre parfois et qui permet de nouvelles réductions de candidats.
Rappelons qu’aucune règle du Sudoku ne stipule que les grilles doivent avoir une solution unique. Pourtant, lors de la fabrication de nos grilles, nous l’imposons comme une contrainte car nous jugeons cette règle absolument indispensable à une résolution convenable.
Nous pouvons alors disposer de techniques de résolution qui se basent sur ce prédicat. Ces techniques sont réunies dans une rubrique dite de la Danse des espions (DE ou UR pour Unique Rectangle dans la littérature anglaise). La Danse des espions se compose de quatre cases étant exactement disposées en deux lignes, deux colonnes et deux blocs.
Modèle à solution double :
Quatre cases placées en rectangle, contenant chacune deux candidats 7 et 8, forment une grille à deux solutions, ce qui est impossible. Il y a donc forcément un ou plusieurs autres chiffres candidats qui viennent empêcher ce cas de figure.
Étudions quelques cas d’unicité :
DE + 1
Permet de supprimer les candidats a et b de la case abx. C’est le cas du Rectangle Unique.
DE + 2x
Permet de supprimer le candidat x de toute zone Su-doku voyant les 2 cases abx.
DE + 2xy
Combiné avec une case qui contient le couple xy, cela forme une paire cachée. Ce qui permet de supprimer toute autre occurrence de x et y dans la zone Sudoku considérée (ligne, colonne ou bloc).
DE + 2 / 1LF (cas n°1)
Il y a une liaison forte (LF), le candidat b sera supprimé de la première ligne.
DE + 2 / 1LF (cas n°2)
Il y a une LF, le candidat b sera supprimé de la case aby.
DE + 3
Tout candidat x sera supprimé du bloc contenant les cases abx en colonne à droite.
DE + 3xyz
Sur la ligne 1, s’il existe une paire xy voyant les cases abx, aby et abz, on pourra supprimer tous les autres x et y communs aux quatre cases.
DE + 3xyz / 1LF
2 ou 3 cases avec des candidats (z est optionnel), un LF et au moins une case à l’extérieur contenant au moins y (a et b étant optionnels) : si cette case partage une zone Su-doku avec la case abx, alors le candidat b peut être supprimé de la case abx.
DE + 3xyz / 2LF (cas n°1)
Trois des quatre cases ont un candidat supplémentaire, il y a aussi deux LF : on peut supprimer le candidat b de la case commune aux deux LF (ici de la case aby).
DE + 3xyz / 2LF (cas n°2)
Les liens forts ont ici une case commune mais ne portent pas sur le même candidat. Un des liens se porte sur la case à deux candidats. Le candidat a peut être supprimé de la case abx.
DE + 3xyz / 2LF (cas n°3)
Les liens forts sont disjoints sur des candidats différents. On peut supprimer le candidat bde la case abx.
DE + 3xyz / 2LF (cas n°4)
Le lien fort est ici disjoint mais sur le même candidat. On est dans le cas d’un Espadon du type I (X-Wing) : le candidat a peut être supprimé de toute case qui voit abx et abz et de toute case qui voit aby et ab. Mais ce qui est intéressant dans ce cas, c’est qu’on peut aussi supprimer le candidat b de la case abx.