Fantomas' side - Articles pour le tag sudokuhttps://blog.fantomas.site/blog/tags/sudoku/Les derniers articles taggés sous sudokufrCopyright (c) 2005-2018, Julien FacheSat, 19 Apr 2014 22:18:18 +0000La face cachée du Sudoku https://blog.fantomas.site/blog/2011/10/11/la-face-cachee-du-sudoku/ <img src="/media/cache/6f/85/6f85967bc7fc45ed3dc82e56fa667bd7.jpg" alt="La face cachée du Sudoku" /> <h1>Introduction</h1><p>Tout commence un soir entre amis, où une envie démente de coder un petit projet nous surprend entre 2 bières. :D</p><p>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.</p><p>Ensuite nous vient l'idée de programmer un résolveur universel de <a title="Le Sudoku sur Wikipedia" href="http://fr.wikipedia.org/wiki/Sudoku">Sudoku</a>, ayant quelques connaissances de base à propos de ce jeu, j'imagine dans les grandes lignes un algorithme pour résoudre ce genre de puzzles...</p><p>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...</p><h1>Passage à l'acte</h1><p>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 <a title="Classification des grilles de Sudoku" href="http://www.le-sudoku.fr/le-sudoku/classification">cette difficulté est toute relative</a>.</p><p>En effet seul le nombre de <a title="Les différentes techniques du Sudoku" href="http://www.mots-croises.ch/Manuels/Sudoku/technique.htm">techniques de résolutions</a> 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 "<em>Diabolique</em>" de les maîtriser. Seules les techniques élémentaires seront nécessaire pour 95% des grilles publiées.</p><p>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. </p><p>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.</p><p>A la suite de cette série d'échecs, je décide d'implémenter un algorithme de résolution basé sur le <a title="BackTracking sur Wikipedia" href="http://fr.wikipedia.org/wiki/Retour_sur_trace">backtracking</a>, 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.</p><h1>Réflexions</h1><p>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. </p><p>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. <br />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.</p><p>Même si un humain peut utiliser la technique du <em>Backtracking</em> (appelé aussi <a title="Nishio et Sudoku" href="http://www.mots-croises.ch/Manuels/Sudoku/Nishio.htm">Nishio</a>) 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.</p><p>Par contre pour une machine, la donne s'inverse, la machine est rigoureusement rigoureuse et peut faire tous ces calculs très rapidement.</p><p>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.</p><h1>Résultats</h1><p>Le résultat de toute ces expériences est disponible sur PyPI sous le nom de <a title="Mon solveur de sudoku sur PyPI" href="http://pypi.python.org/pypi/sudoku-solver">sudoku-solver</a>.</p><pre>$ easy_install sudoku-solver $ sudoku_solver votre_grille.txt</pre><p>Vous pouvez éventuellement contribuer sur la page Github du projet à l'adresse suivante : <a title="Sudoku Solver sur Github" href="https://github.com/Fantomas42/sudoku-solver">https://github.com/Fantomas42/sudoku-solver</a></p><p>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 : <a title="Résolvez vos puzzles de Sudoku en ligne" href="http://sudoku.willbreak.it/">http://sudoku.willbreak.it/</a></p><p>Bon puzzles !</p> fantomas42@gmail.com (fantomas)Tue, 11 Oct 2011 16:49:56 +0000https://blog.fantomas.site/blog/2011/10/11/la-face-cachee-du-sudoku/DécouvertesDéveloppementExpériences