Un programme qui resoud les Sudoku
L’avantage du mois de Mai, c’est qu’avec tous ses jours fériés, il permet de dégager du temps pour de petits développements. Ces derniers jours, je me suis attelé à développer un programme pour résoudre les Sudoku. Aucun intérêt ni économique, ni scientifique, simplement un petit défi personnel.
Ayant été assez intrigué par la démarche adoptée par Peter Norvig, Directeur R&D chez Google, qui préconise une approche via un arbre de recherche, au lieu de se focaliser sur une propagation par contraintes. Mon petit programme, écrit en C, effectue uniquement une propagation par contraintes:
- Le premier type de contrainte consiste à identifier les cases pour lesquelles il n’existe qu’une solution possible. C’est en général le cas des Sudoku "faciles", comme celui-ci:
| | |5| | | |4| | |
| | |2|1|6|4|7| | |
| |1| | |9| | |3| |
|4| | |9| |2| | |3|
| | |9| |1| |2| | |
|8| | |6| |5| | |7|
| |5| | |7| | |8| |
| | |8|4|2|6|5| | |
| | |7| | | |3| | |
- Le second type de contrainte consiste à identifier dans un bloc, une ligne ou une colonne, la seule possibilité pour un chiffre d’apparaître, ou deux cases possibles pour deux chiffres, ce qui élimine tout autre chiffre (on pourrait faire la même chose pour trois ou quatre chiffres, mais sans intérêt). Cela permet de résoudre les Sudoku un peu plus difficiles, comme ceux qui paraissent dans les pages week-end de journaux comme Le Monde ou Le Figaro.
| | | | | |1| | |4|
| |8|5| |2| | |7| |
|4| | | | | | | | |
| |3| | | |7|6| | |
| |1| |2| |8| |9| |
| | |7|1| | | |4| |
| | | | | | | | |2|
| |4| | |8|2|1|3| |
|1| | |6| | | | | |
- Le troisieme type de contrainte consiste à identifier les lignes et les colonnes, a l’intérieur, ou une valeur ne peut pas apparaitre, car elle est deja unique possibilité sur la ligne ou la colonne d’un bloc adjacent. Cette contrainte permet de resoudre les Sudoku vraiment plus durs, comme les "Diabolik" proposés par Astraware.
| | | | | | | |5| |
| |5| |3| | |4| |8|
|6| | | | |7|1|3| |
| | | | | |9|7| |1|
|5|6| | | | | |4|3|
|1| |7|8| | | | | |
| |1|5|2| | | | |4|
|8| |2| | |3| |6| |
| |7| | | | | | | |
Je n’ai pas encore pu aller au bout de mes tests, ni d’effectuer de mesures de performances pour le comparer avec le programme en Python proposé par Peter Norvig. Quand ce sera fait, mes lecteurs pourront meme recuperer le source et le binaire (sous Windows) pour jouer de leur coté..
Update: la propagation de contraintes pures n’a pas donné entièrement satisfaction. Un gros bug qui trainait forçait en fait certaines contraintes, et provoquait la résolution par chance. Une fois ce bug corrigé, seul le premier exemple continuait de fonctionner. Suivant le conseil de Peter Norvig, j’ai donc implémenté rapidement une procédure récursive qui teste les différentes valeurs possibles sur la première case non encore résolue et poursuit la propagation de contraintes. Et là, ça marche très bien.
En termes de performances, les deux premiers exemples passent en moins de 0.01s. Le troisième prend 0.03s. Quant à l’exemple suivant, considéré comme l’un des plus difficiles, il se résoud en fait très rapidement en 0.01s, et sans nécessiter de récursion (la propagation des contraintes fonctionnant à merveille ici).
Encore un peu de nettoyage, et le source sera livré sur ce même billet.
Hervé Kabla, ancien patron d’agence de comm’, consultant très digital et cofondateur de la série des livres expliqués à mon boss.
Crédits photo : Yann Gourvennec
Salut Herve.
Je fais le même travail de mon coté.
Par contre , je regarde autour de moi comment les gens resolvent leur SUDOKU pour optimiser.
Dans mon entourage, les hommes et les femmes ne resolvent pas de la même façon.
Les femmes sont beaucoup plus rapide.
Ne pas tirez de conclusions attives…
Hum, les femmes qui font plus d’un Sudoku de difficulté correcte dans leur vie sont rares… Je n’en connais qu’une… Si les femmes sont plus rapides, peut-etre est-ce parce qu’elles s’interessent (en général) aux plus simples?
Quid (en terme de performance) de la résolution du sudoku dit « AI Escargot », réputé comme étant le plus difficile connu jusqu’à présent ?
C’est le dernier point mentionné: resolution sans recursivité, en un centième de secondes. Même à la main, il n’est pas si difficile que cela…
Tu dois en connaître deux alors… car je pense que nous ne faisons pas référence à la même, et pourtant tu les connais toutes les deux 😉
Celle a laquelle je pense travaille a l’ARCEP. Qui est l’autre?
L’autre travaille dans un hôpital ! Et il me semble bien qu’elle est plus rapide… à vérifier !
Normal, la concurrence y est rude…
50 mn pour l’ « AI Escargot » au réveil ! Je pense qu’elle peut faire mieux 😉
Salut, personnellement, j’en avais fait une version php, absolument pas optimisée (et d’ailleurs pas tout-à-fait achevée)
Je serais curieux de pouvoir comparer avec ton source. Tu le mets quand à disposition ?
Quand ce sera le cas, je te remercie si tu peux me prévenir.
Merci et @+
Et bien tres bientot, le temps de passer du pas tout-a-fait achevé actuel a une version un peu plus robuste. J’ai encore deux trois grilles qui partent en vrille…