Technique de résolution d'un Su Doku (Sudoku)

Publié le par Étienne

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 :
Sudoku n° 79
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 :
Sudoku n° 80
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 :
Sudoku n° 100
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.

À suivre...

Mise à jour d'un article du 14/08/2005
Pour être informé des derniers articles, inscrivez vous :
Commenter cet article
Z
bonjour , super interressant toutes tes techniques et explications
 
si vous voulez télécharger plus de 100000 grilles de sudoku allez sur
http://www.sudoku-gratuit.fr 
Toutes les grilles de sudoku à télécharger et à imprimer sont gratuites et il y a tous les niveaux de difficulté (facile, moyen,difficile et diabolique) .De plus le site propose une multitude de variantes tel que des sudokus X ou diagonal, des grilles samourai ou samurai, des wordoku ou encore le alphadoku.Depuis peu je viens d'ajouter des japanes puzzles tels que des le picross ou logimage ou encore nonograms. Vous trouverez aussi des grilles de logicolor.Des grilles pour les enfants avec des symboles tels que lors héros de dessins animés (dora,simpsons,winnie l'ourson).Les anglais disent sudoku puzzle.Vous pouvez aussi télécharger des ebook ou des cahiers de grilles .Vous pouvez jouer en ligne avec des jeux en flash ou en java script.Pour les webmasters , je vous propose des scripts pour mettre un jeu de sudoku en ligne sur votre site web ou votre page web, tout cela est facile à mettre en place (un simple copier/coller).Des logiciels de jeu de sudoku sont aussi à télécharger sur le site avec des solver ou solutionneur de grilles .Vous cherchez un jeu de sudo-ku pour votre pocket pc ou palm ? Vous le trouverez sur le site
à bientôt sur http://www.sudoku-gratuit.fr
Répondre
L
Encore et toujours de la pub...
E
.

http://www.sudoku.free.fr/

.
Répondre
E
Grilles de sudoku à jouer en ligne ou à imprimer, logiciels, liens, actualité, etc... le tout est gratuit bien évidement : http://www.sudoku.free.fr .
Répondre
B
je viens de lancer un concours de résolution d'une grille un peu difficile... pas encore de succès pour le moment.
Répondre
A
Après la théorie, rien ne vaut la pratique ! Enfin tout ça pour dire que j'ai bien aimé vos explications, et pour vous inviter à affronter d'autres sudokistes en tournois sur www.e-sudoku.fr.
Répondre