SUDOKU
TECHNIQUES DE SUDOKUSudoku : La Piste du tigre (Loop)
Cette technique est considérée par certains comme la technique universelle permettant de résoudre n’importe quelle grille de sudoku. Nous allons aborder l’univers des boucles par l’une des plus simples : celle que l’on nomme X-Cycle.
Définitions :
– L’inférence : c’est une opération logique portant sur des propositions tenues pour vraies qu’on appelle aussi prémisses. Un exemple concret connu : en rentrant chez moi, je vois une ambulance devant ma maison (ce fait est réel, la prémisse). Je ne peux pas m’empêcher d’imaginer que quelqu’un est malade à la maison (je formule une inférence). Formuler, ou envisager une inférence, c’est imaginer une ou des conclusions à partir d’un fait établi.
Un lien existe entre deux cases si elles appartiennent à la même zone Sudoku (ligne, colonne ou bloc) et si elles partagent un même chiffre candidat. Si deux cases ont deux chiffres candidats communs, il y a deux liens. Mais soulignons que, dans la pratique du X-Cycle, les termes d’inférence et de lien sont indifféremment employés.
Quand un lien existe entre deux cases, on peut alors formuler une inférence et déterminer la valeur d’un candidat : si une case contient le candidat A, alors la seconde case du lien ne peut pas le contenir et vice-versa. Par exemple, une zone Sudoku contenant au moins trois candidats identiques alors que l’on considère un lien entre deux d’entre eux. Dans ce cas, on parle d’une inférence faible.
D’autre part, si l’une des cases du lien ne contient pas le candidat A, alors la seconde doit le contenir. Par exemple, une zone Su-doku ne contenant que deux possibilités pour un chiffre candidat. On parle d’une inférence forte.
Toutefois, il est important de souligner qu’une inférence forte est d’abord et aussi une inférence faible.
– La boucle ou Nice Loop : on appelle ainsi une chaîne de cases reliées entre elles par des inférences et se refermant sur elle-même.
– Le sommet est le chiffre candidat sur lequel arrive et repart un lien. Dans cette technique, il peut être assimilé à une case.
– La boucle d’inférences alternées ou boucle d’alternances ou Alternating Nice Loop : c’est une boucle qui alterne les liens de forte et de faible inférence.
– si l’alternance des liens forts et faibles est parfaite et complète (très rare), on parle de boucle d’alternances régulières.
– s’il y a une seule imperfection dans la boucle, c’est-à-dire deux liens consécutifs de même nature (fort-fort ou faible-faible), on parle de boucle d’alternances irrégulières, celle-ci a forcement un nombre de sommets impairs, sinon la boucle est discontinue deux fois.
Règles :
1 – Dans une boucle d’alternances régulières, on peut éliminer tous les candidats des cases qui peuvent être vues par au moins deux cases de la boucle.
2 – Dans une boucle d’alternances irrégulières, si une case est reliée par deux liens forts, alors dans cette case, le candidat de la boucle doit être conservé.
3 – Dans une boucle d’alternances irrégulières, si une case est reliée par deux liens faibles, alors dans cette case, le candidat de la boucle doit être supprimé.
Conventions d’écriture : (les cases désignées ne correspondent pas à l’exemple de la grille de droite, elles sont données à titre d’exemple)
– Pour indiquer un lien fort, on utilise le signe (=) : L1C1 =1= L1C8 indique qu’il existe un lien fort avec le candidat 1 entre les cases L1C1 et L1C8.
– Pour indiquer un lien faible, on utilise le signe (–) : L1C1 -1- L5C1 indique qu’il existe un lien faible avec le candidat 1 entre les cases L1C1 et L5C1.
Exemple réel de boucle d’alternances irrégulières
Dans l’exemple ci-dessus, les liens forts sont représentés par des flèches pleines et les liens faibles par des flèches en pointillés.
Dans la ligne 7, quatre cases contiennent le candidat 5 : si L7C4 contient le 5, L7C7 ne peut pas le contenir et inversement. Nous avons ici une inférence faible.
Dans la colonne 5, deux cases seulement contiennent le candidat 5, L6C5 et L9C5 : si L6C5 ne contient pas le 5, alors L9C5 doit le contenir. Il s’agit d’une inférence forte.
On peut noter cette boucle de la manière suivante :
L7C4 -5- L7C7 =5= L6C7 -5- L6C5 =5= L9C5 -5- L7C4
Il s’agit d’une boucle d’alternances irrégulières.
La case L7C4 est reliée par deux liens faibles, donc d’après la règle n°3, on peut y supprimer le candidat de l’inférence, ici le 5.
Exemple de boucle d’alternances régulières
On peut noter cette boucle de la manière suivante :
L1C1 -5- L8C1 =5= L8C9 -5- L4C9 =5= L4C4 -5- L1C4 =5= L1C1
La règle n°1 dit que l’on peut éliminer tous les candidats 5 des cases qui peuvent être vues par au moins deux cases de la boucle.
C’est le cas des candidats 5 des cases L7C1, L2C4, L5C4 et L7C9.
Exemple réel de boucle d’alternances irrégulières
Dans cette boucle, nous utilisons l’idée qu’une inférence forte est aussi et d’abord une inférence faible. C’est le cas ici de la liaison L3C2 -5- L1C3 : on interprète le lien fort comme un lien faible afin d’obtenir une boucle d’alternances régulières.
On peut noter cette boucle de la manière suivante :
L1C3 =5= L1C7 -5- L3C8 =5= L5C8 -5- L5C6 =5= L8C6 -5- L8C2 =5= L3C2 -5- L1C3
Grâce à cette interprétation du lien fort, on peut utiliser la règle n°1 qui dit que l’on peut éliminer tous les candidats 5 des cases qui peuvent être vues par au moins deux cases de la boucle.
C’est le cas des candidats 5 des cases L3C7, L3C9, L5C5, L5C9, L8C5 et L8C9.
Exemple de boucle d’alternances irrégulières
Dans cet exemple, l’irrégularité se réalise sur la case L3C4 par deux liaisons fortes.
Il est intéressant de remarquer les liens qui existent entre les trois cases contenant la paire 5-8: L4C5, L3C5, L3C4. Ce sont des paires conjuguées et par conséquent, il existe deux liaisons par case, chacune ayant de plus une inférence forte. Or, on sait que l’on peut interpréter une inférence forte comme une inférence faible.
On peut noter cette boucle de la manière suivante :
L3C4 =5= L7C4 -5- L7C1 =5= L5C1 -5- L5C6 =5= L4C5 -5- L3C5 =5= L3C4
La règle n°1 dit que dans le cas d’une boucle d’alternances irrégulières, si une case est reliée par deux liens forts, alors le candidat d’inférence doit être conservé dans cette case. C’est le cas de la case L3C4, qui contiendra donc le candidat 5.
Remarque : dans ce cas de figure, on remarquera qu’il n’existe en réalité qu’une seule liaison faible (ligne 7). On peut donc démarrer la boucle de plusieurs endroits, mais quand on a assigné une force à un lien, fort ou faible, il ne doit pas être modifier en cours de route.