[Plan du site] Vous êtes ici --- > Le Site du Zéro > Les news > Programmation > DebSudoku, ou comment résoudre des sudokus avec dpkg > Lecture d'une news

Commentaires de news :
DebSudoku, ou comment résoudre des sudokus avec dpkg

Revenir à liste des news

DebSudoku, ou comment résoudre des sudokus avec dpkg

# Par wgmpgp, le 28/08/2008 à 22:35:32

Daniel Burrows, développeur de logiciels libres et chercheur en informatique, nous a fait part ce samedi 23 août d'une expérience amusante qu'il a réalisée. Son but : utiliser le gestionnaire de paquets de la distribution Linux Debian (nommé dpkg) pour résoudre le puzzle japonais bien connu : le sudoku. Il l'a fait en réponse à un article posté sur le blog de Russel Coker, qui évoquait ironiquement le fait que Debian n'avait pas besoin d'un gestionnaire de paquets capable de résoudre un Sudoku. Voilà un moyen original de résoudre des sudokus qui aurait dû être utilisé par les participants au concours de programmation en C++.

Faisons tout d'abord un petit rappel avant d'entrer dans le coeur de cette brève. Un gestionnaire de paquets est un logiciel pré installé avec 99% des distributions Linux (de cette façon, les utilisateurs de Slackware sont contents :-°

), permettant d'installer très facilement des logiciels, en gérant les dépendances et les conflits entre les programmes. On peut notamment citer dpkg, utilisé par Debian, portage, de Gentoo, ou pacman, d'Archlinux. Ainsi, le gestionnaire de paquets va prendre un logiciel sous forme d'un paquet (la plupart du temps une archive, comme un fichier zip), et va suivre les instructions pour l'installer (par exemple : « pour m'installer, tu auras besoin d'installer le logiciel X, et il faut que le logiciel Y ne soit pas installé »).

De l'autre côté, un sudoku est un puzzle de 9 cases sur 9 (sauf variantes), à remplir selon des règles simples :

Une ligne doit contenir tous les chiffres de 1 à 9 ;
Une colonne doit contenir tous les chiffres de 1 à 9 ;
Un bloc de 3 chiffres sur 3 (il y en a donc 9 sur la grille) doit également contenir tous les chiffres de 1 à 9.

Le lien entre les paquets et le sudoku est tout simplement le fait que les deux peuvent êtres exprimés sous la forme de dépendances et de conflits. En effet, pour que notre sudoku soit rempli, il faut que les 9 lignes, les 9 colonnes et les 9 blocs soient remplis. On peut ainsi très facilement faire le lien avec les paquets logiciels : par des relations de dépendances, ce schéma est très facilement reproductible. De la même manière, un sudoku peut être vu sous la forme de conflits : deux chiffres identiques sur la même ligne sont en conflit, et de même pour les colonnes et les blocs.

Ce travail peut sembler inutile à l'utilisateur. Cependant, cela permet aux développeurs d'isoler des problèmes et d'améliorer la résolution des dépendances du gestionnaire de paquets : en effet, l'auteur de DebSudoku a remarqué qu'une recherche de solutions en utilisant des conflits est beaucoup plus rapide que celle utilisant les dépendances, mais également que certaines modifications du code permettent une résolution plus rapide des conflits. Daniel Burrows a également évoqué trois idées permettant d'augmenter sensiblement la vitesse de résolution des dépendances dans dpkg, prouvant ainsi que son expérimentation n'était pas tout à fait inutile.

[en] Partie 1 et partie 2 de l'article parlant de DebSudoku sur le blog de Daniel Burrows
[en] Le code source de DebSudoku

Retour en haut

32 Commentaires

Désolé, les commentaires de cette news sont désactivés, vous ne pouvez pas en ajouter !

Pseudo	Commentaire
Page : 1 2 Suivante
1 visiteur sur cette news (0 membre et 1 anonyme)
Page : 1 2 Suivante
Agbeladem	# Posté le 28/08/2008 à 22:46:31
2^24=16777216 Groupe : Membres	Bon article.
Thunderseb	# Posté le 28/08/2008 à 22:46:46
Trolleur en chef !	Moais, faut quand même être motivé pour passer son temps à ça (enfin moi, déjà sur papier un sudoku m'énerve alors penser à une méthode pour le résoudre, très peu pour moi ) Drache, boue et VTT \| Smilies \| Mettre des vidéos Flash \| Ça puxx \| Browsers RealFox \| FOXYCODE \| AJAX et l'échange de données en JavaScript \| L4D Une map pour Half-Life² avec Hammer 4 \| Protect the witch
Le Zéro	# Posté le 28/08/2008 à 22:48:45
I'm a ZerO Groupe : Membres	A ce propos, à quand les résultats du concours ?! Fallait comme même y penser ! Utiliser la résolution des sudokus pour améliorer la gestion des paquets. PS: Il n'y a pas quelques newsers en moins ?! En tout cas zxbsoz wgmpgp ne s'arrete plus ! Avancement de mon site web, MyFrog.fr : \|\|\|\|\|\|\|\|\|\| Le Zéro
vergere	# Posté le 28/08/2008 à 22:50:19
Groupe : Membres	Il devait vraiment se faire chier --> Dsl, j'avais lu en travers la news. "Et quand ils baisent, les connards, c'est bruyamment et à coté des trous" Desproges
wgmpgp	# Posté le 28/08/2008 à 22:52:06
Rotoclap true fan Groupe : Membres	Citation : vergere Il devait vraiment se faire chier C'est la première chose à laquelle j'ai pensé en lisant ça. Mais finalement c'est une super idée pour optimiser les algorithmes utilisés pour la résolution de conflits . Membre de l'association Prologin - Contributeur à Pygments - Administrateur des serveurs Noobulous - Auteur de news - Un projet intéressant La saucisse orange de rotoclap coûte 5900 euros. 흣
Tarmalik	# Posté le 28/08/2008 à 22:54:05
Groupe : Membres	Super news, merci
kna	# Posté le 28/08/2008 à 22:58:52
Groupe : Membres	C'est un truc qui servait à rien au départ, et qui finalement peut servir, si j'ai bien compris... Citation : News Un gestionnaire de paquets est un logiciel pré installé avec 99% des distributions Linux (de cette façon, les utilisateurs de Slackware sont contents slackware aussi a un gestionnaire de paquets : pkgtool (et ses outils installpkg, removepkg, updatepkg et makepkg), mais par contre il ne résoud pas les dépendances. Et donc ne pourrait pas résoudre un sudoku... A ma connaissance il n'existe pas de distribs linux sans gestionnaire de paquets. Celà dit peut-être... I thought what I'd do was, I'd pretend to be one of those deaf-mutes.
bluestorm	# Posté le 28/08/2008 à 23:05:26
dont ask to ask Groupe : Membres	On peut relier ça au travail qu'on effectué des chercheurs, entre autre de l'INRIA, sur la formalisation de la gestion de paquets des systèmes libres. Ils avaient à l'époque développé des outils pour vérifier les dépendances cycliques, etc. et vérifier la cohérence des dépôts. Managing the Complexity of Large Free and Open Source Package-Based Software Distributions Programmation : la récursivité Présentation de KDE : les KIO-slaves Le typage en programmation : présentation thématique et historique mes textes divers
Galdon	# Posté le 28/08/2008 à 23:21:41
Ah, monde de merde ! Groupe : Membres	Ca tombe à pic pour le concours After Effects - 3dsmax - des liens sympas - Encoder avec Virtualdub
Kyan	# Posté le 28/08/2008 à 23:24:46
Groupe : Membres	Je ne dirai qu'un mot : ÉNORME ! Ubuntu is an ancient african word meaning : "I can't configure Debian" Le clavier AZERTY, c'est dépassé vieux rabougris obsolète tout pourri ! Maintenant, la clâââsse, c'est le clavier BÉPO
Tycale	# Posté le 28/08/2008 à 23:37:44
Apple Groupe : Membres	Sympa la news. Bravo à son auteur et bravo à l'auteur de debsudoku La nux-team, les plus beaux toussa toussa : www.nux-team.net #nux-team @ quakenet : Ruby Rulz §!§
kryptos	# Posté le 29/08/2008 à 00:23:29
Groupe : Membres	Ca n'a rien de nouveau. Il s'agit juste d'une application du principe de programmation par contraintes. Mais j'avoue que c'est plutôt rusé que d'utiliser le gestionnaire de paquets http://zone-freegames.forumactif.com http://cbna.forumactif.com
Craw	# Posté le 29/08/2008 à 01:02:06
Rien n'est parfait ! Groupe : Membres	Le Zéro si mais c'est normal. Ensuite beau défi. Réfléchir c'est agir mentalement. Tout ce qui est vivant est mortel. Renier la vérité c'est mentir, renier le mensonge c'est aussi mentir. Craw
`Nex	# Posté le 29/08/2008 à 01:11:15
24H01 \| ±›Þ♀ Groupe : Membres	Bonne news. PS : Craw est plus newser ? Ἡροδότου Ἁλικαρνησσέος ἱστορίης ἀπόδεξις ἥδε, ὡς μήτε τὰ γενόμενα ἐξ ἀνθρώπων τῷ χρόνῳ ἐξίτηλα γένηται, μήτε ἔργα μεγάλα τε καὶ θωμαστά, τὰ μὲν Ἕλλησι τὰ δὲ βαρϐάροισι ἀποδεχθέντα, ἀκλεᾶ γένηται, τά τε ἄλλα καὶ δι' ἣν αἰτίην ἐπολέμησαν ἀλλήλοισι. Hérodote. Vidéo - Get Firefox.
Craw	# Posté le 29/08/2008 à 01:15:27
Rien n'est parfait ! Groupe : Membres	Non. Réfléchir c'est agir mentalement. Tout ce qui est vivant est mortel. Renier la vérité c'est mentir, renier le mensonge c'est aussi mentir. Craw
L@in-Ux	# Posté le 29/08/2008 à 01:40:35
Plop Groupe : Membres	Enorme tout simplement ! j'accepte d'un codeur que son appart soit en bordel, qu'il y ait des restes de pizza sur le canapé, ou bien carrément qu'il n'ait pas de canapé... mais le code doit être propre. Y'a des priorités dans la vie
litleboy	# Posté le 29/08/2008 à 02:35:26
Groupe : Membres	Simple, courte, mais complète, une très bonne news quoi Tout simplement j'adore ce site .
Diti	# Posté le 29/08/2008 à 02:57:03
Manchot empereur Groupe : Membres	POISSON D'AVRIIIIIL! Hein, quoi ? C'en est pas un ? Citation : Kyan Je ne dirai qu'un mot : ÉNORME ! CMB. “HAPPY FEET YIFF IS ARTISTIC, DAMMIT!!!1!1!” Jabber :
pinto	# Posté le 29/08/2008 à 03:44:53
Groupe : Membres	Citation : Diti POISSON D'AVRIIIIIL! Hein, quoi ? C'en est pas un ? Citation : Kyan Je ne dirai qu'un mot : ÉNORME ! CMB. Pas trop chiant à promener ? Sinon bonne news mais est ce que des gestionnaires de paquets vont utiliser cetravaille ?
NoHaR	# Posté le 29/08/2008 à 08:25:35
Wakarimashita yo Groupe : Membres	<coup de gueule> Bien que je trouve assez marrant l'idée d'aller au bout d'une petite boutade, pour montrer que la résolution des dépendances et contraintes des paquets .deb et la résolution d'un sudoku peuvent être formellement problématisées de la même manière, je ne trouve pas que ça soit si impressionnant que ça, et j'avoue aussi que ça m'énerve un peu : - En théorie des jeux, des trucs bien plus impressionnants que ça existent déjà, mais on n'en entend jamais parler. - Ce mec me fait penser à l'autre, qui est devenu une star sur le net, pour avoir utilisé les algorithmes de tracking les plus banals sur une wii-mote, et qui présente ça au monde comme la nouveauté du siècle alors que le tracking d'un capteur actif comme celui-ci est à la portée de n'importe quel hypothétique étudiant en M1 qui n'a que ça à foutre de s'acheter une wii-mote pour la démonter... Si ce genre de mecs avait pour principal effet d'intéresser/sensibiliser les gens à la théorie des jeux, l'IA ou la vision par ordinateur, je me dirais "tant mieux, on va être reconnus par un plus grand public", mais ce n'est pas le cas, et ça couvre de ridicule le travail sérieux de toute la communauté scientifique, qui, derrière, sont déjà à des années-lumière de ces applis... ("Ah wé, la théorie des jeux, c'est résoudre des sudokus avec le gestionnaire de paquets Debian...") </coup de gueule> La facilité : c'est ne pas essayer de ne pas vivre en contradiction avec les idées que l'on ne défend pas... Mon Tutoriel : Vision par Ordinateur Avancement : Nouveaux chapitres à l'horizon
souls killer	# Posté le 29/08/2008 à 08:43:04
I have a dream, today !! Groupe : Membres	NoHaR : je trouve dommage de voir du noir partout... Avec cette méthode de résolution, le plus grand nombre deviendra capable de comprendre comment fonctionnent général les gestionnaires de parquets, ce qui constitue un progrès. Et puis, c'est une idée pour le moins originale. "Qui mange du boeuf... Mange du boeuf Qui mange du porc... N'est pas musulman" Rédigez vos news !! \| le Manuel du Zér0 \| Rédigez des Cahiers des Charges pour vos projets, organisez-vous ![En refonte] \| Perdu sur le Web ?
wilshire	# Posté le 29/08/2008 à 08:58:47
Groupe : Membres	Le fait d'améliorer le gestionnaire de paquet via ce genre de programme me semble intéressant. Et je comprend NoHar. Meme si il est vrai que je n'ai pas tout compris
pierreyoda	# Posté le 29/08/2008 à 09:00:14
Vive le SiteDuZero!! Groupe : Membres	Pas mal! NoHaR : Certes, mais pas dans ce cas-là. Ça ne t'est jamais arrivé de faire un truc pour le fun? Bah là c'est pareil, sauf qu'on en parle... Mais je te comprends Mon site : cliquez ici. Mon site : cliquez ici.
souls killer	# Posté le 29/08/2008 à 09:27:37
I have a dream, today !! Groupe : Membres	Citation : wilshire Le fait d'améliorer le gestionnaire de paquet via ce genre de programme me semble intéressant. Et je comprend NoHar. Meme si il est vrai que je n'ai pas tout compris Donc, tu le comprends même si tu ne le comprends pas. Je suis déjà dehors. "Qui mange du boeuf... Mange du boeuf Qui mange du porc... N'est pas musulman" Rédigez vos news !! \| le Manuel du Zér0 \| Rédigez des Cahiers des Charges pour vos projets, organisez-vous ![En refonte] \| Perdu sur le Web ?
Natim	# Posté le 29/08/2008 à 09:30:26
Apprendre à coder c'est coder Groupe : Membres	<cpastroll> Faut pas dire que Slackware n'a pas de gestionnaire de packets. Et Archlinux, Zenwalk et compagnie sont des dérivés de Slackware ce qui montre bien que Slackware reste la référence en matière de bonne distribution. Nah ! On notera aussi qu'il l'a fait en Python </cpastroll>
lemirandais	# Posté le 29/08/2008 à 10:56:11
Ubuntu, Debian, Tiger USER Groupe : Membres	je testerais par curiosité A l'aide: serveur multi-utilisateur
shine-neko	# Posté le 29/08/2008 à 12:52:47
Saite ita no wa My Rosy Heart Groupe : Membres	Citation : Thunderseb Moais, faut quand même être motivé pour passer son temps à ça (enfin moi, déjà sur papier un sudoku m'énerve alors penser à une méthode pour le résoudre, très peu pour moi ) pluch 1 J'avoue que je déteste ça La v3 de Shine-Shiina est sortit Qui n'a jamais rêver d'apprendre a dessiner , Cuisiné japonnais dévorer de nouveaux manga fait par des copains et d'apprendre le japonais ? => La réponse se trouve ici
Attonde	# Posté le 29/08/2008 à 13:48:56
T'en fais pas, elle est moche. Groupe : Membres	Mdr ouai faut avoir du temps à perdre.. Excellente news, très original tout ça . YourBloug [\|\|\|\|\|50%\|\|\|\|\|] On recrute! Rébélion xD Blog Dev Powered by PuissanceWeb Développeur/Rédacteur de Shine-Shiina. Le développement du Mali ? Cf ma biographie . Beau goss cherche belle geekette, MP le !
NoHaR	# Posté le 29/08/2008 à 14:00:57
Wakarimashita yo Groupe : Membres	Bah du reste, c'est vrai que je trouve ça pas mal, c'est un exemple assez concret et marrant : la résolution en elle-même constitue un "cours" intéressant sur l'application de problèmes de ce type, et, il faut l'avouer, c'est original et ça parle à tous ceux qui utilisent des gestionnaires de paquets. Maintenant, mon coup de gueule, c'est plutôt du point de vue scientifique... M'enfin ! Ca reste une bonne news La facilité : c'est ne pas essayer de ne pas vivre en contradiction avec les idées que l'on ne défend pas... Mon Tutoriel : Vision par Ordinateur Avancement : Nouveaux chapitres à l'horizon
Regnareb	# Posté le 29/08/2008 à 14:03:45
Les gens sont cons. Groupe : Membres	Citation : Attonde Mdr ouai faut avoir du temps à perdre.. Du temps à perdre ? Aha. Ou bien l'envie de faire fonctionner ses méninges... Sortie de l'alpha d'Opera 10 ! Idiots finis : Wizard50 Dark-Ragnos zulon MyGB Pink Squirrel Zanpa Nesquik69 ?? Quaddxmas (aide)