assistant-sudoku.com

Grille Sudoku résolue

La grille -183
Easter Monster est certainement une des grilles sudoku les plus difficiles au monde (niveau conventionnel égal à 47) et a fait l'objet de nombreuses études.
Voici une étude de cette grille par la technique des pistes.

Afficher les commentaires Cacher les commentaires

---

La solution

Cette grille exceptionnelle présente des "symétries" intéressantes que l'on peut exploiter pour sa résolution et que l'on va mettre en évidence. Etablissons à cet effet trois propriétés P1, P2 et P3. P1 - Toute piste qui passe par l'un des couples de candidats suivants est invalide : 27L2B1, 27C2B1, 16L2B3, 16C8B3, 16L8C7, 16C2B7, 27L8B9, 27C8B9. Faisons la démonstration pour le premier couple, celle-ci étant semblable pour les autres couples de candidats. Une piste bleue qui passe 27L2B1 se développe comme sur la figure ci-dessous et conduit à contradiction dans la case L5C8 qui ne peut avoir de candidat bleu. Dès lors on peut éliminer tous les candidats dont les pistes sont issues et qui passent par l'un des couples de candidats précités. Ce sont tous les candidats de la figure suivante barrés d'un trait rouge. Faisons la démonstration pour deux candidats, celle-ci étant semblable pour les autres. La piste verte issue du 2L3C1 peut être prolongée par les deux branches bleue et jaune issues de la paire cachée verte de 7B1, qui l'une comme l'autre passe par un couple de candidats conduisant à invalidité. La piste verte est donc invalide et le 2 peut être supprimé. De la même manière, la piste verte issue du 4L5C2 peut être prolongée par les deux branches bleue et jaune issues de la paire d'ensembles cachés verte 8C2B1 et 8C2B7, qui l'une comme l'autre passe par un couple de candidats conduisant à invalidité. La piste verte est donc invalide et le 4 peut être supprimé. Toutes ces suppressions font apparaître un triplet 126 sur L5, ce qui permet à nouveau les suppressions des autres candidats barrés d'un trait rouge sur la figure suivante, avec notamment la validation du 4L5C6 faisant apparaître un autre triplet 126 sur C5. Sur la grille ainsi simplifiée, établissons la seconde propriété qui facilitera la construction de la solution. P2 - Toute piste qui passe par l'un des couples de candidats suivants est invalide : 1L2C7-1L8C3, 1L3C8-1L7C2, 2L2C1-2L8C7, 2L3C2-2L7C8. Démontrons le pour deux de ces couples, la démonstration étant semblable pour les autres. Une piste bleue qui passe par 1L2C7 et 1L8C3, passe aussi forcément par le 6L1C8 et le 6L9C2 en vertu de la propriété P1. Elle se développe donc comme sur la figure ci-dessous et conduit à contradiction dans la case L5C4 qui ne peut avoir de candidat bleu. De même, une piste qui passe par 1L3C8 et 1L7C2 conduit à contradiction, la démonstration est du même type que la précédente. Dès lors montrons l'invalidité pour le 3ème couple. Une piste bleue qui passe parle 2L2C1 et 2L8C7 peut être développée (en vertu de P1) puis prolongée en cascade (en vertu des résultas de P2 déjà acquis) par la piste verte du 1L2C7, puis par celle violette issue du 4L1C7, ce qui conduit à contradiction dans B8 qui ne peut avoir de candidats 3 violet. La piste verte passe donc par le 4L3C9 ce qui conduit aussi à contradiction dans le bloc 1 qui ne peut avoir de candidat 4 vert. La piste bleue passe donc par le 1L3C8 et conduit donc à contradiction dans L2C5 qui ne peut avoir de candidat bleu. CDFD De même, une piste qui passe par 2L3C2 et 2L7C8 conduit à contradiction, la démonstration est du même type que la précédente. Fort de ces résultats, on peut maintenant étudier les interactions de deux jeux de pistes bleue issue du 2L2C1 et jaune issue du 2L3C2 qui permettent quelques éliminations. Etablissons enfin la dernière propriété de "symétrie". P3 - Toute piste qui passe par l'un des couples de candidats suivants est invalide : 2L2C1-1L3C8, 2L3C2-1L2C7. Une piste bleue qui passe à la fois par le 2L2C1 et le 1L3C8 conduit à contradiction dans B2 avec deux 9 bleus. De même, une piste jaune qui passe à la fois par le 2L3C2 et 1L2C7, que l'on prolonge par une bifurcation issue de la paire de 4B3 conduit pour chacune des deux branches de la bifurcation à des contradictions. Résolution A l'aide de ces 3 propriétés , on peut maintenant étudier les interactions de deux jeux de pistes bleue issue du 2L2C1 et jaune issue du 2L3C2. La large extension des deux pistes permet de nombreuses éliminations par croisement et la validation du 8L4C7. La piste jaune prolongée via le 8L3C9 passe par le 7L1C2 bleu et donc le 2L2C1 bleu, ce qui valide ces candidats et toute la piste bleue, et du même coup invalide la piste jaune avec deux 7 jaune sur L1. Un dernier jeu de pistes issues par exemple de la paire de 9B3 permet de terminer la grille avec une piste bleu qui la couvre et une piste jaune conduisant à contradiction dans L5C3. Cette construction de la solution démontre son unicité.