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


précédentsommairesuivant

Résolution du problème

Etapes de résolution

La résolution d'un problème en PLC repose toujours sur les mêmes étapes :

  • Déclaration des variables
  • Définition des domaines
  • Spécification des contraintes
  • Recherche de solutions

Nous allons détailler chacune de ces étapes dans les sections suivantes.

Déclaration des variables

La Programmation Logique avec Contraintes (PLC) consiste en la représentation de problèmes sous forme d'un ensemble de variables soumises à des contraintes.

La première étape consiste à déclarer ces variables.

Le plateau de jeu est constitué de 81 cases pouvant prendre des valeurs comprises entre 1 et 9. Nous représenterons donc le plateau à l'aide de 81 variables, dont le nom sera constitué de:

  • Une lettre pour la ligne (A-I)
  • Un chiffre pour la colone (1-9)

Pour des raisons de commodité (faciliter la définition du domaine de variables), ces variables seront stockées dans une liste:

 
Sélectionnez
Vars = 
 [
    A1,A2,A3,A4,A5,A6,A7,A8,A9,
    B1,B2,B3,B4,B5,B6,B7,B8,B9,
    C1,C2,C3,C4,C5,C6,C7,C8,C9,
    D1,D2,D3,D4,D5,D6,D7,D8,D9,
    E1,E2,E3,E4,E5,E6,E7,E8,E9,
    F1,F2,F3,F4,F5,F6,F7,F8,F9,
    G1,G2,G3,G4,G5,G6,G7,G8,G9,
    H1,H2,H3,H4,H5,H6,H7,H8,H9,
    I1,I2,I3,I4,I5,I6,I7,I8,I9
 ],

Définition des domaines

Une fois les variables déclarées, il est nécessaire de définir leur domaine.

D'après les règles du sudoku, chaque case a une valeur comprise entre 1 et 9.

En swi-prolog, on définit les domaines des variables de la manière suivante :

 
Sélectionnez
Vars in 1..9,


En Sicstus Prolog, on peut définir les domaines de deux manières :

 
Sélectionnez
Vars in 1..9,

ou :

Sicstus Prolog
Sélectionnez
domain(Vars, 1, 9),

Spécification des contraintes

La spécification des contraintes a un double but :

  • Spécifier les contraintes à respecter lors de la recherche de solutions
  • Réduire les domaines des variables avant résolution (consistance d'arc)

Si, lors de la propagation des contraintes et de la réduction des domaines, l'une des variables venait à avoir un domaine vide, le prédicat échouerait et l'exécution s'arrêterait car aucune solution ne pourrait être trouvée. Ceci se fait de manière automatique.


On spécifie des contraintes grâce aux opérateurs #=, #\=, #<, #=<... (les mêmes opérateurs qu'en Prolog, mais avec un # devant).

On spécifie également des contraintes grâce à des prédicats tels que all_different/1. C'est d'ailleurs ce dernier qui va nous permettre de traduire des règles du sudoku telles que "les éléments d'une ligne sont tous différents" :

 
Sélectionnez
  % Tous les chiffres d'une ligne sont differents
  all_different([A1,A2,A3,A4,A5,A6,A7,A8,A9]),
  all_different([B1,B2,B3,B4,B5,B6,B7,B8,B9]),
  all_different([C1,C2,C3,C4,C5,C6,C7,C8,C9]),
  all_different([D1,D2,D3,D4,D5,D6,D7,D8,D9]),
  all_different([E1,E2,E3,E4,E5,E6,E7,E8,E9]),
  all_different([F1,F2,F3,F4,F5,F6,F7,F8,F9]),
  all_different([G1,G2,G3,G4,G5,G6,G7,G8,G9]),
  all_different([H1,H2,H3,H4,H5,H6,H7,H8,H9]),
  all_different([I1,I2,I3,I4,I5,I6,I7,I8,I9]),

  % Tous les chiffres d'une colonne sont differents
  all_different([A1,B1,C1,D1,E1,F1,G1,H1,I1]),
  all_different([A2,B2,C2,D2,E2,F2,G2,H2,I2]),
  all_different([A3,B3,C3,D3,E3,F3,G3,H3,I3]),
  all_different([A4,B4,C4,D4,E4,F4,G4,H4,I4]),
  all_different([A5,B5,C5,D5,E5,F5,G5,H5,I5]),
  all_different([A6,B6,C6,D6,E6,F6,G6,H6,I6]),
  all_different([A7,B7,C7,D7,E7,F7,G7,H7,I7]),
  all_different([A8,B8,C8,D8,E8,F8,G8,H8,I8]),
  all_different([A9,B9,C9,D9,E9,F9,G9,H9,I9]),

  % Tous les chiffres d'un carre sont differents
  all_different([A1,A2,A3,B1,B2,B3,C1,C2,C3]),
  all_different([A4,A5,A6,B4,B5,B6,C4,C5,C6]),
  all_different([A7,A8,A9,B7,B8,B9,C7,C8,C9]),
  all_different([D1,D2,D3,E1,E2,E3,F1,F2,F3]),
  all_different([D4,D5,D6,E4,E5,E6,F4,F5,F6]),
  all_different([D7,D8,D9,E7,E8,E9,F7,F8,F9]),
  all_different([G1,G2,G3,H1,H2,H3,I1,I2,I3]),
  all_different([G4,G5,G6,H4,H5,H6,I4,I5,I6]),
  all_different([G7,G8,G9,H7,H8,H9,I7,I8,I9]),



Ensuite, il faudra initialiser le sudoku avec les valeurs initiales du plateau. Pour cela, on écrit un prédicat grid/2 avec comme arguments la valeur du plateau (sous forme d'une liste) et la liste des variables de notre système.

Si la valeur d'une case est à découvrir, on met 0 comme valeur sur le plateau. Si la valeur dans la liste est différente de 0, alors on ajoute la contrainte Variable #= Valeur

Ceci nous donne le prédicat suivant :

 
Sélectionnez
grid([],[]) :- !.
grid([0|Q1],[_|Q2]) :-
  !,
  grid(Q1,Q2).


grid([Val|Q1],[Var|Q2]) :-
  !,
  Var #= Val,
  grid(Q1,Q2).

Maintenant, nous avons tout ce qu'il nous faut pour effectuer la recherche de solutions.

Recherche de solutions

L'étape précédente a permis la réduction des domaines des variables (quand cela est possible), ce qui facilite la recherche de solutions.

La recherche de solutions consiste à faire la chose suivante:

  • Choisir l'une des variables
  • Assigner à cette variable une valeur de son domaine
  • Réduire les domaines des autres variables par propagation de contraintes
  • Recommencer avec une autre variable ou revenir en arrière si aucune solution n'existe
  • Lorsque toutes les variables ont été affectées, retourner la solution

Le choix des variables peut influencer sur le temps de recherche d'une solution. Ce choix se fait en se basant sur certaines heuristiques, comme par exemple choisir en premier la variable ayant le plus petit domaine (c'est pour cela que la réduction de domaine par consistance d'arc est une étape importante). D'autres heuristiques existent, comme par exemple choisir en premier la variable la plus fortement contrainte. Ces heuristiques peuvent être combinées entre elles.

Ce processus se fait de manière automatique par l'usage du prédicat label/1 :

 
Sélectionnez
label(Vars),



Avec Sictus Prolog, le prédicat est différent: il s'agit de labeling/2 et a deux arguments, le premier étant une liste d'options pour la recherche de solutions (la liste vide [] correspondant aux options par défaut) :

Sicstus Prolog
Sélectionnez
labeling([ffc,step,up,all], Vars),

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.