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


précédentsommairesuivant

Performances

Performances de swi-prolog

Lorsque l'on exécute le programme précédent en swi-prolog et son équivalent en Sicstus Prolog, on s'aperçoit que le programme en Sicstus Prolog trouve la solution plus rapidement. Il apparait en effet que swi-prolog n'applique pas systématiquement la consistance d'arc. Ceci se ressent sur les temps d'exécution.

Pour que swi-prolog applique la consistance d'arc (réduction des domaines des variables à chaque ajout de contraintes), il faut utiliser la bibliothèque 'clp/clp_distinct' (consistance d'arc) en conjonction avec la bibliothèque 'clp/bounds'. Les performances se rapprochent alors de Sicstus Prolog.

Ceci nous montre l'importance de la réduction de domaine par propagation de contraintes pour la recherche de solutions.

La section suivante montre le programme modifié pour effectuer la consistance d'arc en swi-prolog.

Programme modifié

Notez les différences suivantes par rapport au programme précédent :

  • Inclusion de la bibliothèque 'clp/clp_distinct'
  • Utilisation du prédicat vars_in/3
  • Remplacement du prédicat all_different/1 (de clp/bounds) par all_distinct/1 (de clp/clp_distinct)

Par aileurs, on me rapporte que la bibliothèque 'clp/clp_distinct' n'est disponible qu'à partir de la version 5.5.37 de swi-prolog.



Programme swi-prolog modifié pour consistance d'arc
Sélectionnez

:- use_module(library('clp/bounds')).
:- use_module(library('clp/clp_distinct')).


/*
 Permet de résoudre un sudoku

 Entrée: +Grid: la grille de sudoku (0 => vide, [1-9] => ajoute une contrainte)
 Sortie: -Vars: une solution (permet de savoir si il existe plusieurs solutions)
*/

sudoku(Grid, Vars) :-

  % Definition des variables (grille de sudoku)
  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
   ],

  %%%%% REGLES DU JEU %%%%%

  % Les cases prennent des valeurs de 1 a 9
  Vars in 1..9,
  vars_in(Vars, 1, 9),


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

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


  %%%%% VALEUR DU PLATEAU %%%%%  
  grid(Grid, Vars),


  %%%%% RECHERCHE DE SOLUTIONS %%%%%
  label(Vars),

  printGrid(Vars).






/*
 Permet d'initaliser la grille de sudoku

 Pour chaque élément différent de 0, 
 ajoute la contrainte Var #= Val
*/


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


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




/*
 Un exemple de résolution
*/

sudokuExemple(Vars) :-
  sudoku(
    [ 8,0,4,0,0,0,2,0,9,
      0,0,9,0,0,0,1,0,0,
      1,0,0,3,0,2,0,0,7,
      0,5,0,1,0,4,0,8,0,
      0,0,0,0,3,0,0,0,0,
      0,1,0,7,0,9,0,2,0,
      5,0,0,4,0,3,0,0,8,
      0,0,3,0,0,0,4,0,0,
      4,0,6,0,0,0,3,0,1
    ], Vars
  ).







/*
  Fonction d'affichage du plateau.
*/

%%%% AFFICHAGE DU RESULTAT %%%%

printGrid(G) :- 
  printHSep(3),
  printGrid(G,1,1).


printGrid(G,L,10) :- 
  !,
  printHSep(L),
  L1 is L + 1,
  printGrid(G,L1,1).

printGrid([],_,_) :- !.


printGrid([T|Q],L,C) :- 
  write(T),
  printVSep(C),
  C1 is C + 1,
  printGrid(Q,L,C1).


printVSep(C) :- 
  mult3(C), !,
  write('|').

printVSep(_) :- write(',').


printHSep(L) :- 
  mult3(L), !,
  nl, write('==================='), nl,
  write('|').

printHSep(_) :-
  nl, write('|').


mult3(C) :- 
  T is (C mod 3),
  T == 0.

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.