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


précédentsommairesuivant

Les règles du sudoku

Un plateau de sudoku est composé d'une grille de 9 cases de coté. Ce plateau est divisé en "carrés" de 3 cases de coté. Certaines des cases du plateau sont vides, d'autres ont déjà des valeurs associées.

Image non disponible



Le but du jeu de sudoku est simple: il faut compléter la grille en respectant les règles suivantes :

  • Chaque case du plateau peut prendre une valeur allant de 1 à 9
  • Les cases de chaque ligne ont toutes une valeur différente
  • Les cases de chaque colonne ont toutes une valeur différente
  • Les cases de chaque carré ont toutes une valeur différente

Pour résoudre ce problème, nous allons écrire un programme Prolog faisant intervenir de la Programmation Logique avec Contraintes.

Programmation Logique avec Contraintes

Le terme "Programmation Logique avec Contraintes" (PLC) se traduit en Anglais par Constraint Logic Programming, abrégé CLP. C'est l'une des fonctionnalités qu'offre le langage Prolog (abréviation de PROgrammation LOGique).

Le but de ce didacticiel est d'écrire un programme en Prolog afin de résoudre un sudoku en utilisant la Programmation Logique avec Contraintes.

Le langage Prolog

Si vous n'avez jamais programmé en Prolog, vous pouvez découvrir ce langage grâce à mon didacticiel portant sur le sujet :
Le langage Prolog

Vous pouvez également consulter cette page :
http://fr.wikipedia.org/wiki/Prolog

swi-prolog

Pour écrire notre programme, nous allons utiliser swi-prolog. Pourquoi? Parce que contrairement à Sictus Prolog (qui propose également des solveurs de contraintes), swi-prolog a l'immense mérite d'être gratuit (c'est vrai que ça aide !).

Cet article illustrera donc la Programmation Logique avec Contraintes en swi-prolog, mais nous exposerons également les quelques différences avec Sicstus Prolog.

Bibliothèque utilisée

Il existe plusieurs bibliothèques différentes suivant le type de problème à résoudre ainsi que suivant l'implémentation.

Avec swi-prolog
  • solveur sur domaine fini ('clp/bounds')
  • solveur sur les réels ('clpr')
  • consistance d'arc ('clp/clp_distinct')
Avec Sicstus Prolog
  • solveur sur domaine fini (clpfd)
  • solveur sur les entiers (clpq)
  • solveur sur les réels (clpr)

Pour écrire notre programme, nous allons utiliser le solveur sur domaine fini de swi-prolog (clp/bounds). Pour utiliser cette bibliothèque on ajoute la ligne suivante en début de fichier :

 
Sélectionnez
:- use_module(library('clp/bounds')).



Si on avait voulu utiliser la bibliothèque correspondante dans Sicstus Prolog, on aurait fait cette inclusion à la place :

Sictus Prolog
Sélectionnez
:- use_module(library(clpfd)).

précédentsommairesuivant

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.