Programmation Logique avec Contraintes en Prolog : résolution d'un sudoku


précédentsommaire

Extension du problème

Pour des raisons de simplicité et afin de faciliter la compréhension, nous avons limité notre problème à la résolution de sudoku de 3x3x3.

Cependant, il est tout à fait possible d'étendre le problème à la résolution de sudoku de 4x4x4, 5x5x5 ou de taille quelconque (n x n x n). Dans ce cas, il faut prévoir :

  • Un prédicat pour la génération des variables du problème
  • Des prédicats pour connaître la liste des lignes, colones et carrés et ainsi pouvoir ajouter les contraintes all_different
  • Le domaine des variables, qui va de 1 à n²

Différences entre swi-prolog et Sicstus Prolog

Dans notre article, nous avons mis en avant certaines différences entre swi-prolog et Sicstus Prolog, la première étant le prix puisque swi-prolog est gratuit alors que Sicstus Prolog ne l'est pas.

D'un point de vue technique, on note aussi quelques différences, parmi lesquelles :

  • Une différence dans le nom des bibliothèques
  • Des différences dans les API, comme la présence du prédicat domain/3 dans Sicstus Prolog
  • Le prédicat labeling/2 de Sictus Prolog propose plus d'options que le label/1 de swi-prolog

Au niveau performances, le solveur de Sictus parait plus optimisé. Comme nous l'avons vu, le solveur de swi-prolog n'effectue pas de consistance d'arc par défaut, ce qui ralentit la recherche de solution. Sicstus Prolog applique la consistance d'arc sans modification du code, inclu d'autres optimisations et offre plus d'options dans la recherche de solutions.

Dans un contexte industriel, l'acquisition d'une licence Sicstus Prolog peut être envisagée, après étude approfondie. Dans le cadre de petits projets ou de prototypage, swi-prolog peut suffire. (Note: je suis neutre, je n'ai pas d'actions chez Sicstus Prolog !)

Conclusion sur le langage

De manière à illustrer le pincipe de la Programmation Logique avec Contraintes, ainsi que les différentes étapes de sa mise en oeuvre (définition des variables, de leur domaine, spécification des contraintes, recherche de solutions), nous avons pris un exemple simple : la résolution d'un sudoku. Cependant, il est tout à fait possible en Prolog de spécifier des contraintes beaucoup plus complexes, faisant notamment intervenir des formules mathématiques (ex: X*X + 5*Y*Y #<= 2*Z*Z + Delta)

Il existe bien entendu de nombreuses bibliothèques permettant de faire de la Programmation par Contraintes dans de nombreux langages. Néanmoins, toutes n'offrent pas la même richesse d'expression que le langage Prolog (que ce soit dans la spécification des contraintes ou dans le méchanisme de "retour arrière" (backtracking) des prédicats Prolog).

Par ailleurs, il est très simple d'interfacer un programme Prolog avec un autre langage (comme par exemple C++ ou Java), ce qui rend cette solution très attrayante. De plus, contrairement aux idées reçues, l'exécution d'un programme Prolog n'est pas lente du tout, d'autant que la réduction de domaine par consistance d'arc améliore grandement les performances.

Au final, Prolog nous a permis de développer un programme pour la résolution de sudoku à la fois simple, clair, rapide, propre, très court (environ 200 lignes) et utilisable en conjonction avec d'autres langages.

En outre, cet article aura également été l'occasion de faire un rapide comparatif entre swi-prolog et Sicstus Prolog, notamment dans le domaine de la Programmation Logique avec Contraintes.



En résumé, voici quelques uns des avantages de la Programmation Logique avec Contraintes dans la résolution de certains problèmes :

  • Moins de programmation
  • Une programmation simple et claire
  • Moins de risque de bugs (car programmation simple et claire)
  • Exécution rapide (grâce à la propagation des contraintes)

Pour toutes ces raisons, la Programmation Logique avec Contraintes est susceptible d'intéresser les entreprises souhaitant trouver une méthode simple pour résoudre des problèmes parfois complexes et faisant intervenir beaucoup de contraintes. Ces mêmes entreprises pourraient être intéressées par :

  • la grande expressivité du langage Prolog
  • sa facilité d'intégration à un programme écrit dans un autre langage

Remerciements

Je tiens à remercier Trap D pour l'intérêt qu'il a porté à la relecture de cet article et les vérifications effectuées.

Je tiens également à remercier Adjanakis pour m'avoir montré certaines solutions existantes dans d'autres langages (C++, Java) en matière de Programmation avec Contraintes, ce qui m'a permis de faire la comparaison avec Prolog. Ces solutions étant assez spécifiques, je n'en citerai qu'une, pour Java: choco, accompagnée d'un exemple de résolution de sudoku avec choco.


précédentsommaire

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2006 pcaboche. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.