URL: https://linuxfr.org/users/fmorel/journaux/r%C3%A9solution-de-sudokus-avec-aptitude Title: Résolution de sudokus avec Aptitude Authors: florent morel Date: 2008年09月02日T00:00:59+02:00 Tags: debian Score: 23 Oui, on peut résoudre des sudokus avec Aptitude. Et, oui, je parle bien du casse-tête japonais avec une grille de numéros et du logiciel de gestion de paquets Debian ! Je n'ai rien inventé, tout vient du blog de Daniel Burrows (développeur Debian et créateur d'Aptitude) : [http://algebraicthunk.net/~dburrows/blog/entry/package-manag(...)](http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/) [http://algebraicthunk.net/~dburrows/blog/entry/package-manag(...)](http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku-2/) Pour ne pas faire un journal-bookmark et comme ce n'est pas si compliqué que ça, j'explique un peu. Ceci n'est pas une traduction complète de ces deux articles, le lecteur intrigué cliquera sur ces liens et par la même occasion pourra en savoir plus sur les entrailles d'Aptitude (surtout pour le deuxième article). Je ne rapelle pas les règles du sudoku que tout le monde connaît ou pourra aller lire sur Wikipédia par exemple : [http://fr.wikipedia.org/wiki/Sudoku](http://fr.wikipedia.org/wiki/Sudoku) Ce cher Daniel Burrows a créé 9*9*9=729 paquets, nommés CellR.C-V avec R, C et V compris entre 1 et 9 et R représentant l'indice d'une ligne, C l'indice d'une colonne et V la valeur de la cellule. Installer le paquet Cell5.3.2, c'est comme inscrire 2 dans la case de la 5ème ligne de la 3ème colonne. Ensuite, il a créé des paquets virtuels : - CellR.C : Si le paquet Cell4.8 est installé cela signifie que la 4ème ligne de la 8ème colonne a été remplie. Il les a utilisés pour vérifier qu'une seule valeur est placée dans une case et que chaque case est remplie. - blockR.C-V : pour s'assurer qu'une seule cellule par "bloc" ne contient la valeur V (un bloc est un carré de 9 cases qui doivent toutes avoir une valeur différente. - rowR-V : qui représente le fait qu'une case de la colonne R a déjà été remplie avec la valeur V. - colC-V : pareil que précédemment pour les lignes. Une fois tous ces paquets définis, les règles du sudoku imposent les dépendances et conflits : Si le paquet cellR.C-V a BR comme "ligne de bloc" et BC comme "ligne de colonne", les paquets virtuels sont qui sont fournis pas ce paquet sont : cellR.C, blockBR.BC-V, rowR-V, colC-V et ce paquet est en conflit avec ces mêmes paquets. (Là, OK, pour cette histoire de conflit, c'est un peu difficile à comprendre et je ne suis pas sûr que ce soit bien clair pour moi. En tout cas, c'est lui qui le dit et apparemment, ça utilise le fait que les "auto-conflits" sont ignorés dans les fichiers deb. Peut-être que les linuxfriens qui font des paquets Debian dès le petit déjeuner sauront expliquer.) Enfin, Daniel Burrows a créé un paquet "puzzle" qui a comme dépendances cell1.1, cell1.2... pour imposer que toutes les cases soient remplies et cell5.9-1 si le problème qu'il cherche a résoudre impose que la case (5,9) ait la valeur 1. Ensuite aptitude install puzzle et ... ça a marché. Enfin pas à tout les coups. Il fournit un script python pour prendre un sudoku généré par ksudoku et faire le test. Ce qui est intéressant c'est qu'il explique pourquoi Aptitude ne trouve pas le résultat à chaque fois, quelles options lui passer pour que ça fonctionne et pourquoi c'est plus lent qu'avec un logiciel fait exprès. Enfin il liste des choses à faire pour améliorer la rapidité mais explique qu'il ne va les implémenter : parce que ce n'est pas évident que ce soit plus rapide avec des problèmes réels de dépendances entre paquets (c'est un peu à ça que ça sert aptitude quand même), c'est trop compliqué à implémenter et ça trop de risque de casser des choses.