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