29 août 2005

Maîtriser le Sudoku

Depuis quelque temps, je suis accro à un jeu de logique : le sudoku. Je sais, pour quelqu'un qui habite au Japon c'est pas très glorieux de découvrir ça une fois que ça s'est bien répandu dans le monde entier. Mais je rattrape mon retard !

Pour ceux qui ne connaissent pas, il s'agit d'une grille de régions de 3×3 formant une grille 9×9. Il s'agit de placer dans chaque région, chaque ligne et chaque colonne les chiffres de 1 à 9, une seule fois chacun. Pour plus de détails, regardez le lien au-dessus. Si vous voulez vous amuser un peu, essayez un générateur de grilles. Je vous conseille d'imprimer la page, c'est bien plus agréable.

Après avoir resolu plusieurs dizaines de lignes, le processus de résolution devient assez répétitif (mais on ne s'en lasse pas). Les règles de résolution logique que j'utilise se comptent sur les doigts d'une main, et je ne pense pas qu'il y en aie d'autres - a part dérouler l'arbre des possibilités. J'ai donc décidé de programmer un générateur de grilles. Il y en a bien sûr déjà beaucoup sur le web, mais c'était pour comprendre un peu le fonctionnement.

Il y a une façon simple de créer des grilles, en utilisant un solveur logiciel. On part d'une grille blanche, puis on ajoute récursivement des chiffres aléatoirement. À chaque insertion, le solveur vérifie qu'il y a une unique solution. S'il n'y a pas de solution, il fautrevenir en arrière. S'il y en a plusieurs, il faut continuer à ajouter des chiffres. Ça donne une grille assez mauvaise (c'est-à-dire pas très intéressante à résoudre) mais ce sera un début. Plus tard il faudra implémenter un algorithme plus proche de la création à la main, mais c'est un challenge ; les programmes actuels ne produisent pas de résultat aussi bon que ce qui est fait à la main.
J'ai donc commencé à écrire mon solveur. Afin de s'assurer que les grilles sont solvables par des règles logiques, j'ai implémenté un solveur se basant sur des règles logiques, comme un humain. Bien sûr dérouler l'arbre des possibilités est plus facile, mais je préfère reporter ça au plus tard pour éviter au joueur humain d'y avoir recours lui aussi.

Pour le moment, j'ai juste implémenté deux règles :
  • Élimination : pour une case donnée, on regarde les « voisins » (même ligne, même colonne ou même région). S'il ne reste qu'une possibilité, la valeur de lacase est déterminée.
  • Remplissage : pour une région (ou ligne, ou colonne) donnée, on regarde les chiffres manquants. S'il n'y a qu'une case dans laquelle un nombre donné ne peut entrer, alors la valeur de la case est déterminée.
Maintenant je suis un peu embêté. Les autres règles que j'applique sont plus compliqués à mettre sous forme d'algorithme, car elle se basent sur des déductions intermédiaires genre « Il y a un trois dans l'une de ces deux cases ». Je crois qu'au moins dans un premier temps je vais quand même dérouler l'arbre des possibilités, mais me limiter à un ou deux niveaux pour que ça reste humainement possible. J'essayerai ensuite de résoudre les grilles ainsi générées.

En attendant le générateur, je vous livre le sudoku qui m'a donné le plus de mal jusqu'ici. Il est issu d'un livre japonais qui s'appelle tout simplement Sudoku 3, aux éditions Nikoli. L'auteur est Kunpei Aizawa (désolé pour le piratage, je ne le referai plus).

J'y ai passé largement plus d'une heure. Imprimez-le, essayez de le faire et donnez vos temps en commentaire !



2

5
9






4

5
8


1


3

2


4





7

9
8




5


2
3


1


7

6
3






7

9
4

16 commentaires:

Anonyme a dit…

Ouais j'ai pigé le truc. C'est assez chiant à faire puisqu'il y a au début 3 possibilités ou 2 si on choisit bien ses lignes. En tout cas je connaissais pas ce jeu !

Erwan a dit…

Lawren, je te conseille de commencer par des grilles plus faciles pour assimiler le principe de resolution. Sur ces grilles il y a pas mal de cases dont la valeur est determinee directement.

Il y en a la:
http://www.websudoku.com/

Anonyme a dit…

Je te remercie, je voulais juste piger le principe de résolution.

Si il y a déjà une possibilité, ça devient facile à résoudre nan?

En tout cas je savais pas que ce jeu "sudoku" était super connu. J'en avais jamais entendu parlé avant que tu fasses ton article.

Erwan a dit…

Par definition, les grilles dites "faciles" sont faciles a resoudre. Mais c'est utile pour se faire la main. Ensuite tu as des niveaux de difficulte croissant, et a toi de trouver des regles logiques qui permettent de resoudre les grilles les plus difficles.

Il y a des grilles dans lesquelles tu n'as qu'une possibilite pour quelques chiffres, donc au debut on avance vite, puis on est coince et on doit appliquer des regles differentes. Mais evidement, la meilleure facon de comprendre c'est d'essayer de resoudre des grilles. Le seul probleme, c'est qu'on devient vite accro !

Bon, apres je ne t'oblige pas a essayer. Je disais juste qu'au cas ou toi (ou d'autres) veulent essayer la grille que je propose dans cet article, il vaut mieux etre entraine avant.

Didier Durand a dit…

Le sudoku devient une vraie folie dans mon entourage: en Suisse, plusieurs journaux (Blick, Le Matin, etc...) ont publié tout l'été des grilles de manière quotidienne et organisé des concours autour de ces grilles.

En France, cela arrive aussi: dixit un ami qui tient un kiosque de presse et qui est dévalisé!

PS: moi, j'adore !

Anonyme a dit…

Finalement, j'ai été à la Fnac today, et j'ai vu des magazines de sudoku en vente à la caisse à côté des piles... lol

Anonyme a dit…

Bonjour,
J'étais dans le train et une dame à coté de moi planchait sur ces grilles, je suis donc venue sur internet pour satisfaire ma curiosité, mais j'essaye de faire les grilles et je n'en résoud aucune... si il y a un "truc" j'aimerais bien le connaitre pour commencer, merci.

Erwan a dit…

Bonjour Anonyme.

Si tu lis l'anglais, tu as quelques trucs expliques ici:
http://www.puzzle.jp/keys/sudoku_keys-e.html

Ensuite, tu as la des grilles de difficultes croissantes. Mieux vaut commencer par des faciles !
http://www.puzzle.jp/letsplay/play_sudoku-e.html

Anonyme a dit…

Bonjour Erwan,
Je suis l'anonyme d'au-dessus, je suis Bérangère, je suis allée voir les pages que tu m'as conseillé et je ne suis toujours pas dedans... disons que je ne comprend pas leur explication, je ne comprend pas la logique du sudoku, ou y at-il des calculs à faire ?? Désolée d'insister autant mais j'aimerais bien comprendre, merci encore.

Anonyme a dit…

moi javais un sudoku que jai fai mais jetais pris

mais jtrouve que ltien yer plus dur

Anonyme a dit…

Tu peux aussi essayer sur www.e-sudoku.fr, moi j'y ai tout appris dans le livre de sudoku.

Anonyme a dit…

.

Pour jouer au sudoku en ligne (ou imprimer ses grilles), il y a aussi http://www.sudoku.free.fr/

.

Anonyme a dit…

salut si tu veux te perfectionner va la
http://www.sudoku-gratuit.fr

il est tres complet tu trouveras ton bonheure

Anonyme a dit…

-

Perso, j'adore ce jeu. Je joue ici : http://www.123sudoku.net/.

-

inevco a dit…

Salut ! Finalement, as-tu réussi à créer un générateur de grille Sudoku ? Je travaille actuellement à tenter de créer un algorithme logique et intelligent .. c'est pas évident ! Reviens moi si tu trouves kekchose !

pp1234p@yahoo.com

sudoku online a dit…

J'avoue que je n'aime pas trop jouer au sudoku niveau difficile. Juste pour passer le temps.

Carolina
domo-sudoku.com