Résolution d’un Sudoku
lundi 31 janvier 2011, par
Le jeu du Sudoku a envahi les magazines. J’y ai joué quelque fois pour passer le temps, tout en songeant que voilà un jeu prise de tête sans intérêt culturel (en comparaison avec des mots croisées par exemple). Ce qui m’intéressait plus, c’est comment un automate pourrait résoudre ces jeux de sudoku. Après plusieurs mois à me dire que ça pourrait être intéressant, j’ai plongé...
Je me suis donc amusé à programmer en PHP avec un rendu en HTML (donc visible dans un navigateur) la résolution de jeux de sudoku.
La première tâche a été de représenter le jeu, ce qui se fait très bien dans un tableau. L’enregistrement du jeu se fait sur la base de la valeur et des possibilités de chaque case.
Le raisonnement logique a consisté :
– si une case n’a qu’une possibilité, on peut donner la valeur à cette case
– si dans une ligne, une valeur ne peut se mettre qu’à un endroit, c’est celui là
– même chose pour une colonne
– même chose pour un carré (un bloc)
La suite a été plus compliqué et pour arrêter de me prendre la tête, je me suis permis l’émission d’hypothèse qui est soumise ensuite au raisonnement logique plus haut.
Bref, on boucle entre logique et hypothèse. Cela résout tous les jeu que j’ai pu essayer, mais il reste une faille et une insatisfaction.
La faille d’abord : les hypothèses ne sont pas entrée dans un boucle récurrente, ce qui veut dire que si on fait une première hypothèse qui nous amène à une situation où il faudrait en faire une seconde qui s’avère mauvaise, on peut revenir sur la dernière hypothèse, mais pas sur la première qui est peut-être erronée.
L’insatisfaction, c’est de ne pas avoir eu le courage de résoudre par pure logique seulement. Il aurait fallu pour cela jouer avec les combinaisons de listes de possibilités dans les lignes, colonnes et blocs, ce que je n’ai pas fait. L’informaticien normalement constitué est partisan du moindre effort pour lui même avant de l’être pour la machine, en tout cas c’est mon cas.
Mais je ne désespère pas, un jour peut-être...
– Tout sur le Sudoku sur Wikipédia y compris les méthodes de résolution informatiques.
