Journal Résolution de sudokus avec Aptitude

Posté par  .
Étiquettes :
23
2
sept.
2008
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-manag(...)

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

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.

  • # urpmi

    Posté par  (site web personnel) . Évalué à 7.

    Ca serait marrant de faire le même test avec urpmi ;-)

    • [^] # Re: urpmi

      Posté par  . Évalué à 2.

      Ou pas. :)

      Urpmi, Yum et autre Apt sont plus ou moins similaires : ils doivent gérer un compromis entre la rapidité de la résolution du problème de dépendances et la qualité de cette même solution.

      Je me demande par contre comment se débrouillerait ZYpp sur les limites rencontrées par Apt dans la résolution des Sudoku, sachant qu'il utilise un solveur SAT qui est complet (il ne trouve pas une solution possible, mais il trouve la meilleure solution possible dans un temps très raisonnable.)

  • # Une fois de plus...

    Posté par  . Évalué à 10.

    ... Debian s'illustre avec ses outils de gestion de paquets à la pointe de la technologie :)

  • # Japonais

    Posté par  . Évalué à 3.

    je parle bien du casse-tête japonais
    Le Sudoku n'a de japonais que le nom. C'est même expliqué de long en large sur la page Wikipédia citée dans l'article (http://fr.wikipedia.org/wiki/Sudoku).

    C'est une chouette astuce en tout cas :-)
    Ca permet de résoudre toutes les grilles "immédiates", c'est à dire celles qui se remplissent sans avoir besoin de faire d'hypothèses. Niveaux 1, 2, 3 et 4 dans les livres de jeux habituels. Au delà, pas de mystère, il faut soit un cerveau et beaucoup de temps (niveau 7, j'y passe une bonne heure mais je suis moyen)... ou un logiciel qui trouve en moins d'une seconde après avoir pressé la touche de validation.

    • [^] # Re: Japonais

      Posté par  (site web personnel) . Évalué à 3.

      Tu définis comment les niveaux de difficulté ?

      Je fais ceux du Monde (sans problème, sauf les experts que je réussis une fois sur 10, le dernier de dimanche par exemple, ne mértiait pas cette catégorie, je l'ai fait sans gomme). Je bloque souvent sur les supérieurs de Libé.

      A ce propos, si quelqu'un pouvait m'indiquer un bon tuto de résolution de Sudoku, ça serait sympa.

      A part l'application des règles (du style il y a forcément un 8 dans cette ligne, et ça ne peut être que sur cette case), et les doublons/triplés/quadruplés (dans une ligne/colonne/carré, je sais que 2 cases ne peuvent contenir que 3 et 7 par exemple, dans si une case de cette "zone" peut contenir 3 ou 5, elle contient forcément 5), je cherche des astuces.

      Et hélas, peu de journaux expliquent comment résoudre. Avoir la solution ne m'intéresse pas, je peux recopier mon Sudoku, puis essayer une hypothèse, et revenir en arrière si ce n'est pas bon, mais il doit y avoir une méthode plus intelligente, non ?

      ウィズコロナ

      • [^] # Re: Japonais

        Posté par  . Évalué à 3.

        Tu définis comment les niveaux de difficulté ?

        J'imagine que ça doit dépendre des méthodes à utiliser pour le résoudre. Quand on peut faire des déductions assez simples, le niveau est facile, quand on est obligé de tester plusieurs coups possibles, c'est difficile.

        Ma méthode en général est de regarder les coups possibles dans une case puis de les éliminer en fonction de ce qui se trouve autour, jusqu'à n'avoir plus qu'une possibilité.

        J'avais fait un petit code en Lisp pour résoudre les Sudokus, malheureusement, je n'ai jamais eu le courage d'implémenter toutes les méthodes de résolution possibles, ce qui fait qu'il ne peut pas résoudre les grilles les plus complexes (vu que je cherchais à optimiser, je ne suis pas passé par la méthode bourrin "on teste tout").

        C'est ça le plus marrant dans ce genre de casse-tête je trouve, pas de les résoudre à la main à la chaîne :)

      • [^] # Re: Japonais

        Posté par  (site web personnel, Mastodon) . Évalué à 3.

        Moi perso, j'applique la simple méthode de résolution par contrainte.

        En gros, tu assignes les 9 chiffres dans toutes les cases. Puis tu effaces ceux qui ne sont pas possibles de manière directe. Et tu rétières. Rien que ça, ça permet généralement d'aller très loin de manière "mécanique".

        Ensuite, si vraiment tu es bloqué, faut faire une hypothèse. Tu choisis la case où il te reste le moins de choix et tu "forkes" ton arbre des possibilités.

        En programmation, c'est super simple à faire. À la main, faut juste un peu de bon sens et faire travailler un peu sa mémoire à court terme mais ça fonctionne bien aussi.

        Le gros avantage de cette méthode c'est que c'est systématique.

        Mes livres CC By-SA : https://ploum.net/livres.html

        • [^] # Re: Japonais

          Posté par  (site web personnel) . Évalué à 2.

          Merci pour ta méthode.

          Quand j'ai une hypothèse à formuler, j'essaie de choisir ce qui a l'air d'avoir la proba la plus élevée.
          Mais ce n'est pas parce que il y a 2 chances sur 3 pour qu'une case contienne un 8 que ça se vérifiera.

          ウィズコロナ

      • [^] # Re: Japonais

        Posté par  . Évalué à 2.

        Tu définis comment les niveaux de difficulté
        Je me base bêtement sur les niveaux des livres de jeux. Ils sont tous à peu près équivalents (un niveau 6 chez l'un est équivalent au 6 d'un autre). Cela reste tout de même très bancal car beaucoup de grilles sont tout de même d'un niveau très inférieur à celui annoncé. Je pense qu'ils utilisent un programme pour générer les grilles, mais que leur programme de notation se base sur un calcul trop simpliste (du genre c'est basé sur le nombre d'itération de résolution en force brute, alors qu'il faudrait plutôt calculer sur des nombres d'hypothèses par exemple).

        Pour les méthodes, il n'y en a pas 36 accessibles au cerveau humain. Ce sont celles que tu connais. D'autres sont expliquées sur la page de wikipédia, mais une fois arrivé au bout des déductions logiques, le plus rapide est de faire une hypothèse. Pour les hypothèses j'écris des mini-grilles dans la marge. Et je me trompe souvent :-)

      • [^] # Re: Japonais

        Posté par  . Évalué à 0.

        J'ai fait une petite application en ruby avec Shoes qui applique le même type de raisonnement. A chaque fois qu'il bloque sur une grille je l'étudie et j'ajoute de nouveaux raisonnements. Pour le moment il sait traité jusqu'au niveau difficile des grilles du monde. Il travaille sans hypothèse car je pense que l'on peut résoudre tous les sudokus par raisonnement et pas par hypothèse qui est une technique "boeuf" d'ordinateur ;-) .

  • # Pour ceux qui voudraient en savoir plus..

    Posté par  . Évalué à 6.

    Pour ceux qui voudraient en savoir plus sur le fonctionnement d'Apt et d'Aptitude, je ne peux que recommander l'article de D.Burrows :

    D. Burrows, Modelling and Resolving Software Dependencies, June 2005 : http://people.debian.org/~dburrows/model.pdf

    C'est assez long mais très instructif.

  • # Moi, j'utilise...

    Posté par  . Évalué à 10.

    ... ma copine.
    Trés pratique, avec une interface un peu trop humaine qu'elle en devient chiante parfois. Mais une fois, la touche "merci chérie" enfoncée, je suis tranquille pour une bonne heure sans qu'elle vienne me casser les pieds. Ce qui me laisse le temps de faire 4 5 grilles d'un niveau supérieur pénards.

  • # Bof!

    Posté par  (site web personnel) . Évalué à 2.

    Moi je trouve que le sudoku c'est ennuyeux. En fait il s'agit juste de boutons à états qui peuvent pas prendre le même état qu'un autre bouton sur la même ligne ou dans le même carré.

    En fait résoudre un sudoku reviens juste à cocher le seul état possible pour chaque bouton.

    Pour être un peu plus concret, en prenant une grille avec 9 états (le truc le plus courant il me semble), vous complétez les cases vides avec les 9 états possibles et vous rayez ceux qui ne sont pas possibles de par l'état des autres cases. A la fin (c'est vite fait) il n'y a qu'un état qui n'est pas barré par case. Le plus long est d'inscrire les 9 états dans chaque case.

    Voila, j'imagine que le but c'est de faire travailler le cerveau, mais je trouve ça vraiment trop ennuyeux ce jeux de case à cocher.

    • [^] # Re: Bof!

      Posté par  . Évalué à 3.

      Pour moi (même si je ne joue pas au Sudoku) (un peu comme dit un commentaire au dessus), l'intérêt réside dans le fait de trouver la méthode la plus rapide de résoudre une grille (voir l'algorithmie, la complexité) et peut-être l'"intuition" (qu'on n'arrive pas à "enseigner" aux ordinateurs, comme pour les échecs par exemple).

    • [^] # Re: Bof!

      Posté par  . Évalué à 3.

      Ce que tu décris, ce sont les sudoku "ordinaires". Ca se résouds effectivement très rapidement. Mais lorsque tu as des grilles avec vraiment peu de cases pré-renseignées, ça ne fontionne pas du tout comme ça :-)

      Cela dit, aimer ou pas, c'est une question de goût, je ne discute pas.

      • [^] # Re: Bof!

        Posté par  (site web personnel) . Évalué à 2.

        Je peux me tromper mais il me semble que la méthode que je décris se généralise. Le plus long en fait c'est de marquer tout les états dans chaque case. Après il s'agit vraiment de simplement barrer les états impossibles, ce qui devient de plus en plus simple à mesure que tu coches des états impossibles.

        En procédent de la sorte, tu vois clairement par exemple que dans un carré (celui dont la hauteur × la largeur donne le nombre d'états), même s'il te reste plusieurs possibilités (inférieur ou égale à 3 pour une grille à 9 états) dans plusieurs cases, il peu y avoir une case qui reste la seule possibilité d'avoir cette état dans le carré.

        Bien sûr tout ça peut être fait de tête, mais ça apparaît bien plus clairement avec des états à cocher. Inutile d'écrire des nombres d'ailleurs, de simple traits, chacun représentant un état, suffisent. Par exemple pour une grille à 9 états, on peut écrire dans chaque case:

        |||
        |||
        |||

        qui représente respectivement :

        1 4 7
        2 5 8
        3 6 9

        Et donc obtenir :

        †††
        †|†
        †††


        Est équivalent à dire que le seul état pour cette case est 5.

        En fait le fait de mettre des nombres est juste là pour te présenter le problème d'une manière à le rendre plus difficile. Si on te présentait une grille ou dans chaque case tu avais déjà la présentation comme je l'explique ci-dessus, tu verrais tout de suite qu'il s'agit juste de cocher les états impossibles pour les cases où l'état n'est pas encore définie, par rapport aux cases ou un seul état n'est pas coché.

        • [^] # Re: Bof!

          Posté par  . Évalué à 2.

          Ce que tu décris, ça s'apelle grosso modo la propagation de contrainte.

          Tu fais des déductions logiques en déduisant les valeurs impossibles dans chacune des cases, et quand il n'y a plus qu'une seule valeur possible, tu peux la prendre en compte dans tes déduction.

          Et non, dans le cas du Sudoku, ça ne suffit pas pour résoudre la grille, en tout cas avec des méthodes de déductions "abordables" diront nous:
          il y a des cas ou ta grille sera dans un état ou elle ne sera pas finie et ou tu ne pourra plus rien déduire avec les méthodes de déductions dont tu dispose.


          Dans ces cas là, ce qu'on fait, c'est qu'on pose une hypothèse, genre on prend une case et on met un nombre encore possible arbitrairement (ou pas), et on vois ce qu'on peut en déduire. Si tu arrives dans un état impossible, genre t'as une case ou tu peux plus mettre de nombre, ton hypothèse est fausse, et tu peux retenter autre chose.

          Si tu arrives de nouveau dans un état ou tu peux plus rien déduire, tu repose une hypothèse, etc.

          PS: si on veut généraliser, en programmation par contrainte, pour tes cases, on utilise la notion de "variables", et pour tes boutons allumés/éteints, la notion de domaine d'une variable (l'ensemble des valeur que peux encore prendre une variable)

  • # Technique de sodoku

    Posté par  . Évalué à 2.

    Bonjour,

    Voilà un des nombreux liens vers des tutoriaux de sodoku : http://naxos.fr.free.fr/sudoku/hints.html

    La méthode la plus rapide pour résoudre un sodoku est la force brut, il me semble, le nombre de grille possible n'étant pas si énorme.

    cordialement,

    • [^] # Re: Technique de sodoku

      Posté par  . Évalué à 5.

      La méthode la plus rapide pour résoudre un sodoku est la force brut
      Avec seulement 5 milliards de possibilitées, c'est vrai que la force brute de ton cerveau y arrive facilement :-)

      Par contre, faire un programme "force brute" est vraiment très simple. Et pour résoudre une seule grille ça prends nettement moins d'une seconde en C. Vraiment pas la peine de se compliquer la vie à programmer quelque chose d'optimisé (sauf pour le plaisir, ou éventuellement la recherche).

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.