Contexte
Le sudoku étant un peu le jeu à la mode en ce moment, je me suis dit qu'il fallait que je m'y intéresse histoire de ne pas paraître complètement stupide en société... Pour ceux qui ne connaissent pas, je conseille (comme toujours) l'excellente page sur la wikipedia. Pour ceux qui veulent des grilles pour jouer, ce n'est pas ici que vous en trouverez mais sur le site Websudoku.
Le jeu en lui-même est relativement simple à comprendre et s'adapte à tout âge. Par contre, certaines grilles peuvent s'avérer réellement dures à résoudre. Mon but était de trouver un moyen de résoudre informatiquement ces grilles, de la même façon que je le fais en réfléchissant.
Solution technique
Armé de ces bonnes résolutions, je me suis lancé dans le code. J'ai pour plusieurs raisons choisi le Java. Parmi elles, la principale est que je voulais améliorer mes connaissances dans ce langage, assez utilisé actuellement et que je maîtrisais mal. La seconde est qu'il permet de développer assez vite, sans trop se soucier de la gestion de la mémoire. Le principal défaut de java, le temps d'éxécution, est ici peu critique vu la relative faible complexité des sudokus.
Plutôt que des solutions violentes (comme analyse méthodique des possibilités ou recuit simulé) ou génériques (programmation par contrainte), j'ai cherché à reproduire le schéma de réflexion
Dans un premier temps, le logiciel va chercher tous les coups autorisés et les noter dans un tableau de coups potentiels
Si pour une case donnée, il n'a qu'une position de jeu, il va jouer ce coup là. C'est le rôle de la classe JouerSimple
Une fois que cette méthode de jeu a épuisé tous les coups possibles, il va rechercher si dans un sous-ensemble (bloc, colonne ou ligne), un nombre apparaît une seule fois. C'est le rôle de la classe JouerSeul.
Les techniques suivantes vont consister non plus à trouver un coup à jouer directement, mais à réduire la liste des coups possibles. On a pour ça la classe JouerExclusionBlocLigne, qui va chercher les intersections pour chaque nombre. De même, la classe JouerSimplificationNUplet permet de simplifier les n-uplets. Plus pratiquement, quand sur une ligne (ou un bloc, ou une colonne), on trouve que n chiffres peuvent être joués sur exactement n cases, on est sûr qu'ils ne peuvent pas être joués sur les autres positions.
La dernière technique (implémentée par JouerChaineForcage) est beaucoup moins élégante, elle consiste à implémenter les chaines de forçage, donc à raisonner par l'absurde. On fait l'hypothèse de jouer une position (typiquement sur une doublette) jusqu'à arriver à une position impossible. Dans ce cas, c'est que le coup initial était erronné. Cette technique est indispensable pour finir certaines grilles "diaboliques"
Techniquement, la classe jouerCoup sert d'interface à toutes ces techniques de jeu. La classe Resolveur sert à résoudre le sudoku, en chargeant dynamiquement les classes préceédentes. Il est donc très simple d'implémenter d'autre techniques de jeux, simplement en les faisant hériter de la classe JouerCoup et en les ajoutant en bonne position dans la classe Resolveur.
Utilisation
Pour utiliser ce solveur de sudoku (et a fortiori le compiler), vous devez disposer d'une machine virtuelle java en version 1.5 (disponible sur le site de sun)
Pour l'utiliser, le programme prend en entrée un fichier sdk, qui est simplement une grille de sudoku avec un espace pour une case vide, le nombre pour les cases du départ, avec une ligne par ligne (voir le fichier d'exemple). En sortie, le programme affiche sur l'écran la méthode pour résoudre le sudoku et la grille finale. Si le programme n'arrive pas à terminer, il affiche une grille des "possibles à jouer". N'hésitez pas à m'envoyer toute grille que le programme ne résoud pas que je me penche sur le problème !
Au niveau de la syntaxe, il suffit de se mettre dans une ligne de commande et de taper :
- java -jar sudoku.jar exemple.sdk
Il peut être une bonne idée de rediriger la sortie vers un fichier (ajouter >fichier.txt au bout de la ligne) pour pouvoir la consulter avec un éditeur de texte ou l'imprimer
Voici la solution pour l'exemple fourni.
Todo
De nombreuses évolutions sont prévues, dont la principale est de doter le programme d'une ergonomie digne de ce nom, et en particulier en utilisant une IHM au lieu de la commande en ligne actuelle. Vous pouvez voir dans les sources le début du projet (package gui), hélas pas beaucoup avancé et laissé pour compte à causes d'autres priorités actuellement
Une autre idée consiste à mettre en ligne une applet pour résoudre les sudokus. Hélas, le choix de java 1.5, qui simplifie la programmation, limite son utilisation "in line".
Globalement, je n'ai pas réussi à coincer ce solveur, toute remarque sera la bienvenue. De même, je pense qu'on peut nettement améliorer les performances, je n'ai pas trop eu le temps de me plonger dans le sujet.
