Fantomas’side

Weblog open-source

La face cachée du Sudoku

Introduction

Tout commence un soir entre amis, où une envie démente de coder un petit projet nous surprend entre 2 bières. :D

Lui vient du monde Java, moi du Python, mais ayant subi la même formation, le moment fût propice pour comparer nos progrès et évolutions et aussi lancer un troll ou deux.

Ensuite nous vient l'idée de programmer un résolveur universel de Sudoku, ayant quelques connaissances de base à propos de ce jeu, j'imagine dans les grandes lignes un algorithme pour résoudre ce genre de puzzles...

L'idée générale du programme est d'appliquer de manière séquentielle les 2 ou 3 stratégies de résolutions que j'utilise moi même quand je fais un Sudoku tiré d'un magazine...

Passage à l'acte

Rapidement j'obtiens un résultat, mais se pose le problème de la difficulté. En effet, les grilles disponibles dans les magazines sont classées par difficulté croissante, or cette difficulté est toute relative.

En effet seul le nombre de techniques de résolutions nécessaires (en général 3 ou 4) à un puzzle conditionne le niveau de difficulté. A savoir qu'il existe de techniques très complexes pour résoudre certaines grilles de Sudoku, mais il ne sera jamais nécessaire même à un niveau dit "Diabolique" de les maîtriser. Seules les techniques élémentaires seront nécessaire pour 95% des grilles publiées.

Mais concernant les 5% restant, là cela devient beaucoup plus complexe, car après plusieurs heures de recherches et de compréhension de ces techniques, je décide d'en implémenter certaines dans le résolveur pour augmenter ses chances de résolution.

Mais le problème reste entier, même si j'augmente le nombre d'algorithmes de résolution, si je tombe sur un cas que je n'ai pas prévu, je ne peux pas résoudre complètement la grille. En effet, le programme n'est pas capable d'improviser une solution ou d'échafauder une hypothèse qui lui permettrait de se sortir de ce cas imprévu.

A la suite de cette série d'échecs, je décide d'implémenter un algorithme de résolution basé sur le backtracking, solution qui me convient beaucoup mieux car le taux de résolution des puzzles est de 100%, mais insatisfaisante car elle ne permet pas d'expliquer la solution et le temps de résolution d'un puzzle est peu prédicable et très fluctuant.

Réflexions

En guise de conclusion à cette immersion dans le monde du Sudoku qui s'est révélée au final bien plus riche qu'il ne le semblait aux premiers abords, j'ai appris une belle leçon en matière de programmation et surtout d'algorithmique.

En effet mimer la façon de penser d'un homme pour résoudre certains problèmes de programmation peut parfois se révéler intéressant et source de solutions, mais il ne faut pas oublier que l'on traite avec une machine.
Une machine n'a pas la capacité d'innovation ou d'évolution face à un problème non identifié, par contre elle est capable de retenir des millions d'informations et de les traiter beaucoup plus rapidement que n'importe quel humain et ça, c'est un avantage indéniable.

Même si un humain peut utiliser la technique du Backtracking (appelé aussi Nishio) pour résoudre sa grille, il mettra un temps phénoménal mais il n'y arrivera que s'il est très rigoureux et ce n'est pas du tout ludique.

Par contre pour une machine, la donne s'inverse, la machine est rigoureusement rigoureuse et peut faire tous ces calculs très rapidement.

Pour conclure, même si un humain et une machine peuvent plus ou moins faire la même chose, il ne faut jamais oublier de prendre en compte les points forts et points faibles de l'un et de l'autre dans la conception d'un algorithme.

Résultats

Le résultat de toute ces expériences est disponible sur PyPI sous le nom de sudoku-solver.

$ easy_install sudoku-solver
$ sudoku_solver votre_grille.txt

Vous pouvez éventuellement contribuer sur la page Github du projet à l'adresse suivante : https://github.com/Fantomas42/sudoku-solver

Et pour terminer, je n'ai pas pu m'empêcher de réaliser une démo web de ma librairie sous le framework Django. Donc si vous voulez résoudre ou vérifier vos grilles de Sudoku, allez à cette adresse : http://sudoku.willbreak.it/

Bon puzzles !