résolution du Sudoku
Vocabulaire
Le sudoku classique est composé d'une grille de 81 cases, organisées en 9 lignes de 9 colonnes.
La grille est aussi subdivisée en 9 régions contenant chacune 9 cases.
On appelle Groupe un ensemble de 9 cases appartenant soit à la même ligne, soit à la même colonne, soit à la même région.
Il y a au total 27 groupes
La règle du jeu est simple: Chaque groupe doit contenir tous les chiffres de 1 à 9.
On appelle candidat un chiffre a priori possible pour une case. Une case est résolue quand une case ne contient plus qu'un seul candidat. Le candidat unique devient la solution.
On appelle intersection un ensemble de trois cases appartenant à la fois à une ligne et une région, ou à une colonne et une région. Il y a au total 54 intersections.
Méthodes de résolution
Les méthodes suivantes sont par ordre de difficulté croissante.
Vous devait donc appliquer la première méthode jusqu'à ce qu'elle ne permette plus d'avancer.
Vous tenter alors la deuxième méthode. Si elle permet de résoudre une case, alors il faut revenir à la première méthode.
Si la deuxième méthode ne donne rien, alors tenter la suivante...
Chaque fois qu'une méthode complexe permet de réduire un ensemble de candidats, il faut revenir aux méthodes simples.
Méthodes simples
Réduction par croix
Cette méthode est très visuelle.
Pour placer le chiffre "1", vous rayez toutes les lignes, colonnes et régions qui contiennent déjà "1".
Pour toutes les cases non rayées, le chiffre "1" constitue un candidat pour cette case.
Si dans un groupe il ne reste qu'une seule case non rayée, alors vous pouvez y placer de façon certaine le "1".
Refaites la même chose pour les autres chiffres.
Candidat unique (ou décompte)
Dans chaque case vous écrivez tous les candidats. Si la case ne contient qu'un seul candidat, alors ce candidat est la solution de la case.
Méthodes plus complexes
Ces méthodes imposent de commencer par écrire tous les candidats possibles dans chaque case. On Procède ensuite par élimination des candidats.
Méthode des intersections
Cette méthode permet, par l'analyse des candidats d'un groupe, de réduire les candidats d'un autre groupe.
Pour une ligne, si un candidat n'apparait que dans une des trois intersections possibles, alors ce candidat est obligatoirement dans l'intersection. On peut donc éliminer ce candidat des cases de la région qui ne font pas partie de l'intersection.
De plus, si l'ensemble des possibiltés obligatoires de l'intersection a la même taille que le nombre de cellules non résolues de l'intersection, alors l'intersection ne peut comprendre que les candidats identifiés comme obligatoires.
Le même résonnement s'applique pour les intersections entre colonnes et régions, régions et lignes, régions et colonnes.
Méthode des chaînes (ou cases couplées)
Cette méthode permet de simplifier les candidats dans un groupe.
Dans l'exemple suivant, si l'on place l'un des chiffres 1,2,3 en dehors des cases A,B,C, alors une de ces cases n'aura plus de solution possible.
1,2,3 ne peuvent donc être placés que dans les cases A,B,C.
C'est ce que l'on nomme une chaîne.
L'exemple montre deux chaînes triviales: ABC avec trois candidats (123) et ABCD avec 4 candidats (1234).
La chaîne la plus courte est la plus intéressante.
Sachant que 123 ne peut être placé que dans ABC, nous pouvons éliminer 123 des autres cases.
Trouver une chaîne permet donc de réduire les candidats des autres cases.
Généralisation: Il y a chaîne si la somme des candidats de n cases contient exactement n candidats.
La méthode des chaînes doit être appliquée plusieurs fois au même groupe, jusqu'à réduction complète.
Essayez de réduire cet exemple et vérifiez votre réponse: solution
Méthode des jumeaux (ou chiffres couplés)
Cette méthode permet de simplifier les candidats dans un groupe.
Dans l'exemple suivant, les chiffres 1,2 n'apparaissent pas en dehors des cases A,B. Si 1 est en A, alors 2 ne peut être que en B. De même si 1 est en B, alors 2 ne peut être que en A.
Cela permet de dire qu'excepté 1,2, aucun autres chiffres ne peut apparaitre dans A,B.
Trouver des jumeaux permet donc de réduire les candidats des cases concernées:
Généralisation: Si n éléments apparaissent dans exactement n cases, alors aucun autre élément ne peut apparaitre dans ces n cases.
La méthode des jumeaux doit être appliquée plusieurs fois au même groupe, jusqu'à réduction complète.
Essayez de réduire cet exemple et vérifiez votre réponse: solution
Entrainement aux méthodes chaînes ou jumeaux
Complétez les 9 cases "Avant" représentant les candidats d'un groupe (ligne, colonnes ou région):
Vous remarquerez que les deux méthodes ont toujours le même résultat final.
C'est parce que les deux méthodes sont strictement équivalentes!
Si vous n'obtenez pas le même résultat, c'est que vous avez commis une erreur:
Le nombre de candidats différents doit être rigoureusement égal au nombre de cases occupées.
Si vous laissez des cases vides, alors vous devez réduire d'autant le nombre de candidats différents.
Démonstration de l'équivalence: le complément d'une chaîne donne des jumeaux et le complément des jumeaux donne une chaîne.
- Exemple des chaînes : avec 123 trouvés, les jumeaux sont 456789
- Exemple des jumeaux : avec 12 trouvés, la chaîne est 3456789
Il est tout de même bon de connaitre les deux méthodes, car il aurait été difficile de voir les jumeaux 456789 ou la chaîne 3456789.
Remarques: la simplification obtenue pour l'exemple des chaînes montre la puissance de cette méthode.
Méthode dites x-wing et son extension swordfish
Cette méthode n'est pas implémentée, c'est une lacune à corriger...
Classification des grilles
- Une grille est dite facile si elle est résolue essentiellement par la méthode des exclusions avec occasionnellement la méthode des candidats uniques.
- Une grille est dite moyenne si elle nécessite une seule fois l'une des méthodes intersection, chaîne ou jumeaux.
- Une grille difficile nécessite plusieurs fois les méthodes intersection, chaîne ou jumeaux.
- Une grille est diabolique si après avoir épuisé toutes les méthodes de résolution logiques, elle ne peut être résolue que en testant des hypothèses.
Il ne faut pas confondre difficulté et patience.
Une grille d'un niveau donné peut certes sembler plus ou moins difficile,
il n'empêche que si vous maitrisez les méthodes requises pour ce niveau,
vous saurez toujours la résoudre avec un peu de persévérence même si c'est une grille de 36X36!
méthodes des hypothèses
Les méthodes de résolutions ont échouées, cela ne veux pas dire qu'il n'y a pas de solution.
Si vous êtes sûr de n'avoir commis aucune erreur, alors vous avez une grille diabolique!
Vous devez maintenant vous écarter des solutions purement logiques.
Avec le logiciel, il faut faire une sauvegarde par "Sauver". Sur papier, il faut faire une copie de la grille.
Parmi les cases non remplies, choisir le premier candidat disponible et tenter ensuite de résoudre la grille par les méthodes classiques.
Vous serez peut être ammené à faire plusieurs fois des hypothèses. Si vous arrivez à une impossibilité (case sans candidat), alors la supposition était fausse. Il faut revenir à la grille sauvegardée (avec "Reprendre") et tenter une autre supposition.
Jouer
Le lien Sudoku permet de jouer aux différents niveaux, avec à la demande une aide au cas par cas, histoire de se familiariser avec les méthodes de résolution.