Technique universelle de résolution
Les techniques élémentaires ayant été utilisées, la résolution des grilles de niveau élevé (7 et plus) nécessitent l'utilisation de "techniques experts" comme la dynamique de l'espadon (X-Wing), l'approche du tigre (AIC), la danse des espions (unicité), l'attaque du cobra (ALS), etc...
techniques qui en fait se déduisent toutes d'une seule
technique universelle, la technique des pistes (ou technique des marquages).
L'assistant sudoku dispose d'un outil mettant en œuvre cette technique expliqué ci-dessous. Evidemment, cette technique peut être appliquée aussi sur une version imprimée de la grille en utilisant des marquages de son choix, un par piste, par exemple en entourant d'un rond les candidats de la piste 1 et en entourant d'un carré ceux de la piste 2. Sur le site nous avons choisi des couleurs.
Technique des pistes
Une "piste" est un ensemble de candidats se déduisant les uns des autres par raisonnement logique à partir d'un candidat choisi comme point de départ.
Par exemple dans la grille ci-contre, le candidat de départ de la piste à construire (candidats coloriés en bleu) est le 5 de la case L2C5.
Le raisonnement à tenir pour construire la piste est le suivant :
SI le 5 de L2C5 est solution, alors le 8 de L3C5 est solution, alors le 2 de L3C4 est aussi solution, ainsi de suite... tous les candidats coloriés en bleu sont solutions et constituent la piste bleu.
On peut construire ainsi autant de pistes qu'on le souhaite afin d'en tirer des informations utilent à la résolution de la grille.
La 1ère information utile va de soi:
Si une piste conduit à une contradiction (par exemple deux candidats de la piste se situant dans la même zone sudoku, ce qui est impossible), le candidat de départ n'est pas solution et peut donc être éliminé.
Par exemple dans la grille ci-contre, le 1 de la case L3C5 peut être éliminé puisque la piste au départ de ce candidat conduit aux 1 des cases L1C1 et L1C9 de la même ligne.
En construisant simultanément deux pistes au départ de deux candidats formant une paire (case ne comptant que 2 candidats ou candidat ne figurant que 2 fois dans une zone sudoku) on tire beaucoup plus d'informations.
Par exemple dans la grille ci-contre, on construit une piste (bleu) au départ du 9 de la case L8C4 et une piste (jaune) au départ du 9 de la case L9C6.
Les deux pistes ont en commun le 9 de la case L2C3. Comme les deux pistes partent d'une paire de 9 dont forcément l'un au moins est solution on en déduit que
le 9 de la case L2C3 est solution !
On peut alors supprimer le 9 des cases L1C2 et L9C3.
On poursuit ensuite la construction des pistes afin d'en tirer le maximum de résultats (poursuiver sur la
"Grille-Démo" ).
On trouvera des exemples d'application de la technique des pistes dans les problèmes de sudoku avec solution proposés en page d'accueil.
Dans l'application de la technique des pistes au départ d'une paire de candidats on rencontre généralement l'une des situations suivantes :
1- Les deux pistes ont en commun un même candidat dans une case, ce candidat est solution de la case.
2- Les deux pistes ont en commun un candidat de même valeur mais dans deux cases différentes, tout candidat qui voit* les deux cases peut être éliminé.
3- Les deux pistes ont chacune un candidat dans une même case, les autres candidats de la case peuvent être éliminés.
4- Une piste a deux fois un candidat de même valeur dans une même zone sudoku, cette piste n'est pas bonne et ce sont les candidats de l'autre piste qui sont solutions.
Plus généralement, toute contradiction constatée pour une piste valide l'autre piste comme solution.
5- Une piste conduit à la solution de la grille en remplissant celle-ci sans contradiction, ce cas arrive de temps en temps.
6- Les pistes n'aboutissent pas ou plus à des conclusions utilent. Effacez les pistes et repartez d'une autre paire unique.
*
On dit qu'un candidat voit une case s'il appartient à une même zone sudoku que cette case
Exemples d'utilisation de la technique des pistes
1- Candidats communs aux deux pistes
Dans la grille ci-dessous, le départ des pistes se fait sur la paire de 8 du bloc 2. La piste bleu conduit au 1 de la case L3C8. La piste jaune conduit aussi au 1 de la case L3C8. L'une et l'autre piste conduisent au 1 de la case L3C8, le 1 est donc solution (point 1 de la technique) et donc le 9 de la case L2C7 aussi
2- Elimination partielle
On peut utiliser la technique des pistes pour l'élimination partielle de candidats.
Le départ des pistes se fait sur la case L1C8 qui ne compte que deux candidats. On en déduit que les candidats 7 et 8 de la case L2C1 peuvent être éliminés (point 3 de la technique),
ainsi que les candidats 2 et 9 de la case L1C9 qui voient les mêmes valeurs sur les deux pistes (point 2 de la technique).
Le 5 de la case L2C5 aussi peut être éliminé si bien que l'on déduit en cascade la solution dans plusieurs cases.
Exemple tiré du bimestriel Sudoku Maestro N°13 dans lequel l'élimination est faite par la méthode Sue de Coq (L'arme et la soie)
3- Invalidation d'une piste
Fréquemment une piste conduit à une contradiction, ce qui l'invalide et valide les candidats de l'autre piste qui sont donc solutions.
Sur la grille ci-dessous, le départ des pistes se fait sur la paire de 3 du bloc central.
La piste bleu conduit à une contradiction (point 4 de la technique) puisque qu'elle contient le 1 deux fois dans la colonne C4, elle est donc invalidée et ce sont les candidats de la piste jaune qui sont solutions.
Utilisation de pistes secondaires
Il arrive parfois que l'une des pistes principales (1 et 2, dans l'exemple ci-dessous respectivement en bleu et jaune) soit impossible à développer suffisamment.
On peut alors poursuive cette piste avec deux pistes secondaires (Pistes 3 et 4, dans l'exemple ci-contre respectivement en vert et mauve).
Le départ des deux pistes secondaires se fait sur un couple de candidats uniques ne faisant pas partie de la piste principale que l'on prolonge.
Dans l'exemple ci-contre la piste 3 en vert et la piste 4 en mauve sont associées à la piste bleu. La piste en vert conduit à une contradiction (situation 2 décrite ci-dessous), le candidat de valeur 2 (en vert et en bleu) de la ligne L2 sont dans la même zone sudoku, ce qui est impossible.
Les candidats de la piste mauve sont donc des candidats de la piste bleu.
Pour les pistes secondaires on rencontre en général l'une des situations suivantes :
1- Les deux pistes secondaires conduisent à un même candidat, ce candidat fait partie de la piste principale.
2- L'une des deux pistes secondaires conduit à une contradiction, les candidats de l'autre piste secondaire font partie de la piste principale.
3- Les deux pistes secondaires et l'autre piste principale (celle dont ne sont pas issues les pistes secondaires) ont en commun un candidat de même valeur dans des cases différentes, tout candidat qui voit les 3 cases peut être supprimé.
Pour contruire les pistes secondaires, il ne faut pas oublier que les candidats de la piste principale dont sont issues les deux pistes secondaires sont aussi des candidats des deux pistes secondaires.
On trouvera une bonne application de la technique des pistes secondaires dans la résolution de la très
difficile grille de l'Al Escagot.
