Technique de résolution d'un Su Doku (Sudoku)
Un matin comme un autre, dans le RER A, nous nous sommes assis face à un type dont le genre est connu sous le nom d'homme d'affaires. À la main droite (ou la gauche, ça n'a aucune importance), un stylo-bille. Sur ces genoux, un journal, ouvert à la page "jeux". Trois grilles, de 9 x 9, contenant des chiffres. Durant tout le trajet, notre homme d'affaires ne placera qu'un seul chiffre dans l'une des trois grilles.
Le lendemain soir Mélanie, mue par une curiosité toute féminine, achetait un recueil de ces grilles, qui se nomment Su Doku. On raconte que ce jeux est très populaire au Japon et qu'il y a un engouement sans précédent (et alors, le Rubik's Cube, oublié ?) en Europe depuis la parution de grilles dans le Times en novembre 2004.
Qu'est-ce qu'une grille de Su Doku ? Voici un exemple :
L'objectif est de remplir la grille des chiffres de 1 à 9 de façon à ce que chaque chiffre n'apparaisse qu'une fois dans chaque ligne, colonne ou carré de 3 x 3. Comment procéder ? C'est là l'objet de cet article...
Examinons la grille, en particulier le chiffre 2. On en retrouve un sur la dernière rangée et un deux rangées plus haut. On en déduit donc que le chiffre 2 qui se trouve dans le carré du milieu en bas doit se trouver sur l'avant-dernière rangée. Il y a deux cases possibles, celle de la quatrième et cinquième colonne. Or il y a déjà un 2 dans la cinquième colonne (sur la deuxième rangée). On en déduit donc qu'on peut placer le chiffre 2 au centre du carré en bas au milieu.
Ce processus de déduction est le premier de notre arsenal. Avant de poursuivre, introduisons une définition : un groupe est un ensemble de neuf cases d'une même ligne, même colonne ou carré de 3 x 3. L'objectif est donc que les 27 groupes de la grille contiennent chacun tous les nombres de 1 à 9.
Règle n° 1
Étant donné un chiffre et un groupe, s'il n'y a qu'une seule case possible dans le groupe pour le chiffre donné, alors ce chiffre peut être placé dans la case en question.
Dans notre exemple, le chiffre donné est le 2, le groupe le carré en bas au milieu. La seule case possible est celle au centre du carré. On peut donc y placer le 2.
Notez que la règle ne précise pas comment déterminer les cases possibles. Les règles du jeu (le fait qu'un même chiffre ne peut apparaître deux fois dans le même groupe) sont cependant un bon point de départ.
Surprise, cette règle est en fait suffisante pour résoudre les grilles les plus faciles publiées dans la presse ! Il suffit d'un peu d'observation et la grille est complétée en quelques minutes.
Cependant, le joueur passe invariablement à des problèmes plus difficiles et de nouvelles techniques doivent alors être employées. La règle suivante est excessivement banale mais n'est pas si simple à appliquer :
Règle n° 0
Si, sur une case donné, un seul chiffre n'est possible, alors ce chiffre peut être placé sur la case en question.
Par exemple, considérons la case à l'intersection de la troisième rangée et de la cinquième colonne. Dans le carré, on a déjà les chiffres 2, 7, 8 et 9. Dans la colonne les chiffres 6 et 9 et dans la rangée les chiffres 3, 4, 5 et 8. Seul le chiffre 1 peut donc se trouver dans la case en question.
Évident, mais l'être humain n'étant pas une machine, il se lasse rapidement de faire ces observations pour toutes les cases libres de la grille...
Cependant, ces deux règles permettent de résoudre la majorité des grilles publiées dans la presse, y compris la grille exemple ci-haut, pourtant classée diabolique !
Voici deux exemples de grilles prouvant que ces règles ne sont pas suffisantes :
Dans cette première situation, les deux règles ci-haut ne peuvent rien pour nous.
Considérons la première colonne. Les possibilités, de haut en bas, pour les cases libres, sont : { 3, 8 }; { 2, 9 }; { 3, 8 }; { 4, 7, 9}; { 3, 9 }; { 2, 3, 4, 7 }. On remarque que deux cases possèdent les même deux possibilités, soit 3 et 8. On en déduit que ces deux chiffres doivent dont se trouver sur ces deux cases et qu'en conséquence il ne se trouvent pas sur d'autres cases de la colonne. En particulier, on peut donc placer un 9 à la sixième rangée, ce qui débloque la situation.
Cette règle, généralisée à n cases, est un peu plus complexe que les précédentes :
Règle n° 2
Si, dans un groupe donné, l'ensemble définit par l'union des chiffres possibles de n cases différentes possède n chiffres différents, alors ces n chiffres se trouvent dans ces n cases et ne se trouvent donc pas sur d'autres cases du groupe.
Un exemple avec trois cases : les possibilités { 1, 6 }; { 2, 6 }; { 1, 2 } impliquent que les chiffres 1, 2 et 6 se trouvent sur ces trois cases. Ainsi, sur une quatrième case dont les possibilités seraient { 1, 6, 7 } on peut placer le 7.
Passons à notre deuxième grille exemple :
Dans cette deuxième situation, notre nouvelle règle ne nous permet pas de placer aucun nouveau chiffre. Cependant, après observation attentive de la quatrième colonne, on s'aperçoit que le chiffre 5 doit se trouver dans l'une des trois premières cases de la colonne. Il y a une quatrième case de libre dans le carré où se trouvent ces trois cases. Les possibilités pour cette case étant {2, 5}, on peut y placer le 2 car on sait que le 5 doit se trouver dans l'une des trois autres cases.
Règle n° 3
Si, dans un groupe donné, toutes les cases possibles pour un chiffre donné se trouvent dans un même deuxième groupe, alors le chiffre en question ne peut se trouver dans aucune des autres cases de ce deuxième groupe.
Tout comme le cas des deux premières règles, la règle n° 3 est beaucoup plus simple à appliquer pour un être humain que la règle n° 2, qui au contraire ne pose aucun souci pour une machine.
Conclusion
On voit donc qu'avec un ensemble restreint de règles simples, on peut parvenir à résoudre virtuellement toutes les grilles publiées. La question intéressante est maintenant de savoir si les règles énoncées dans cet article sont suffisantes pour résoudre une grille de Su Doku ne possédant qu'une solution...
Dans un prochain article, présentation du programme de résolution.
Mise à jour d'un article du 14/08/2005
Le lendemain soir Mélanie, mue par une curiosité toute féminine, achetait un recueil de ces grilles, qui se nomment Su Doku. On raconte que ce jeux est très populaire au Japon et qu'il y a un engouement sans précédent (et alors, le Rubik's Cube, oublié ?) en Europe depuis la parution de grilles dans le Times en novembre 2004.
Qu'est-ce qu'une grille de Su Doku ? Voici un exemple :
Examinons la grille, en particulier le chiffre 2. On en retrouve un sur la dernière rangée et un deux rangées plus haut. On en déduit donc que le chiffre 2 qui se trouve dans le carré du milieu en bas doit se trouver sur l'avant-dernière rangée. Il y a deux cases possibles, celle de la quatrième et cinquième colonne. Or il y a déjà un 2 dans la cinquième colonne (sur la deuxième rangée). On en déduit donc qu'on peut placer le chiffre 2 au centre du carré en bas au milieu.
Ce processus de déduction est le premier de notre arsenal. Avant de poursuivre, introduisons une définition : un groupe est un ensemble de neuf cases d'une même ligne, même colonne ou carré de 3 x 3. L'objectif est donc que les 27 groupes de la grille contiennent chacun tous les nombres de 1 à 9.
Règle n° 1
Étant donné un chiffre et un groupe, s'il n'y a qu'une seule case possible dans le groupe pour le chiffre donné, alors ce chiffre peut être placé dans la case en question.
Dans notre exemple, le chiffre donné est le 2, le groupe le carré en bas au milieu. La seule case possible est celle au centre du carré. On peut donc y placer le 2.
Notez que la règle ne précise pas comment déterminer les cases possibles. Les règles du jeu (le fait qu'un même chiffre ne peut apparaître deux fois dans le même groupe) sont cependant un bon point de départ.
Surprise, cette règle est en fait suffisante pour résoudre les grilles les plus faciles publiées dans la presse ! Il suffit d'un peu d'observation et la grille est complétée en quelques minutes.
Cependant, le joueur passe invariablement à des problèmes plus difficiles et de nouvelles techniques doivent alors être employées. La règle suivante est excessivement banale mais n'est pas si simple à appliquer :
Règle n° 0
Si, sur une case donné, un seul chiffre n'est possible, alors ce chiffre peut être placé sur la case en question.
Par exemple, considérons la case à l'intersection de la troisième rangée et de la cinquième colonne. Dans le carré, on a déjà les chiffres 2, 7, 8 et 9. Dans la colonne les chiffres 6 et 9 et dans la rangée les chiffres 3, 4, 5 et 8. Seul le chiffre 1 peut donc se trouver dans la case en question.
Évident, mais l'être humain n'étant pas une machine, il se lasse rapidement de faire ces observations pour toutes les cases libres de la grille...
Cependant, ces deux règles permettent de résoudre la majorité des grilles publiées dans la presse, y compris la grille exemple ci-haut, pourtant classée diabolique !
Voici deux exemples de grilles prouvant que ces règles ne sont pas suffisantes :
Considérons la première colonne. Les possibilités, de haut en bas, pour les cases libres, sont : { 3, 8 }; { 2, 9 }; { 3, 8 }; { 4, 7, 9}; { 3, 9 }; { 2, 3, 4, 7 }. On remarque que deux cases possèdent les même deux possibilités, soit 3 et 8. On en déduit que ces deux chiffres doivent dont se trouver sur ces deux cases et qu'en conséquence il ne se trouvent pas sur d'autres cases de la colonne. En particulier, on peut donc placer un 9 à la sixième rangée, ce qui débloque la situation.
Cette règle, généralisée à n cases, est un peu plus complexe que les précédentes :
Règle n° 2
Si, dans un groupe donné, l'ensemble définit par l'union des chiffres possibles de n cases différentes possède n chiffres différents, alors ces n chiffres se trouvent dans ces n cases et ne se trouvent donc pas sur d'autres cases du groupe.
Un exemple avec trois cases : les possibilités { 1, 6 }; { 2, 6 }; { 1, 2 } impliquent que les chiffres 1, 2 et 6 se trouvent sur ces trois cases. Ainsi, sur une quatrième case dont les possibilités seraient { 1, 6, 7 } on peut placer le 7.
Passons à notre deuxième grille exemple :
Règle n° 3
Si, dans un groupe donné, toutes les cases possibles pour un chiffre donné se trouvent dans un même deuxième groupe, alors le chiffre en question ne peut se trouver dans aucune des autres cases de ce deuxième groupe.
Tout comme le cas des deux premières règles, la règle n° 3 est beaucoup plus simple à appliquer pour un être humain que la règle n° 2, qui au contraire ne pose aucun souci pour une machine.
Conclusion
On voit donc qu'avec un ensemble restreint de règles simples, on peut parvenir à résoudre virtuellement toutes les grilles publiées. La question intéressante est maintenant de savoir si les règles énoncées dans cet article sont suffisantes pour résoudre une grille de Su Doku ne possédant qu'une solution...
Dans un prochain article, présentation du programme de résolution.
À suivre...
Mise à jour d'un article du 14/08/2005