Fantomas’side

Weblog open-source

Archives pour le tag : sudoku

Flux RSS de sudoku

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 ...

Continuer la lecture