WikiMath

Introduction

L'âne rouge est un casse-tête dont le but est d'amener l'âne à la barrière de son champ en contournant les autres animaux et en demandant à ceux-ci de se déplacer au mieux.

Ceci s'effectue en faisant glisser successivement des pièces rectangulaires (représentant les animaux) comme on le ferrait au jeu de taquin et ce, jusqu'à ce que que l'âne rouge (représenté par le grand carré rouge) se retrouve en face de l'ouverture du cadre.

Objectifs du projet

• Vous montrer à quel point Prolog est adapté pour résoudre simplement des problèmes d'intelligence artificielle (pour information, ma solution fait moins de 100 lignes)
• Vous prouver (si ce n'est déjà fait) que Logique et Informatique sont indissociables: chacune est au service de l'autre.
• ...

Organisation du projet :

• Le projet est à réaliser par binôme pour le 12 juin. Devront être rendus à cette date :
  1. le programme Prolog résolvant le problème;
  2. une synthèse d'une page justifiant les choix effectués, les originalités de l'implantation,...
• Le 18 juin, le projet sera défendu pendant quelques minutes. Je poserai des questions sur les choix effectués, les clauses développées, et je vous demanderai de résoudre d'autres petits problèmes similaires.

Ce que vous avez à développer

Configuration du système

Une configuration est l'état du problème à un instant donné. Vous devez définir comment vous allez mémoriser chaque configuration. On peut envisager la structure de liste contenant cinq listes :

  [[ja,ro,ro,ja],
   [ja,ro,ro,ja],
   [no,bl,bl,no],
   [no,ma,ma,no],
   [or,vi,vi,or]]).

La première liste donne les carrés de 1*1 qui sont sur la ligne la plus haute, la seconde..., la dernière liste donne les carrés de 1*1 qui sont sur la ligne la plus basse.

• Construire les prédicats

init(X)

qui est vrai si X est une configuration initiale ;

final(X)

qui est vrai si X est une configuration finale;

ligne(N,C,Ln)

qui est vrai si étant donné un nombre N compris entre 1 et 5, et une liste C à cinq éléments, Ln est le N ème élément de C ; intuitivement ce prédicat retourne la N ème ligne de la configuration C ;

colonne(N,L,En)

qui est vrai si étant donné un nombre N compris entre 1 et 4, et une liste L à quatre éléments, En est le N ème élément de L ;

case(L,C,Conf,E)

qui est vrai si dans la configuration Conf, à la L ème ligne et à la C ème colonne on trouve l'élément E ;

changeContenu(C1,E,L,C,C2)

qui est vrai si la configuration C2 est obtenue à partir de la configuration C1 en positionnant à la ligne L et la colonne C l'élément E.

Glisser d'une configuration à une autre

Votre système doit évoluer itérativement de la configuration initiale (celle représentée ci-dessus) vers une configuration correspondant à un état final (l'âne rouge prêt de la barrière).

• Définir les prédicats :

changeContenu(C1,E,L,C,C2)

qui est vrai si la configuration C2 est obtenue à partir de la configuration C1 en positionnant à la ligne L et la colonne C l'élément E.

glissement(P,D,C1,C2)

qui est vrai lorsque en partant de la configuration C1 et en faisant glisser la pièce P dans la direction D, on aboutit sur la configuration C2.

• Effectuer des glissements successifs en exécutant des requêtes du type

    ?- init(ConfInitiale),glissement(ma,b,ConfInitiale,Confb).
    ?- init(CI),glissement(P,D,CI,C2),glissement(P2,D2,ConfInitiale,C3).

Énumérer tous les successeurs d'une configuration

Pour construire la liste de tous les successeurs d'une configuration, on peut utiliser le prédicat findall à trois arguments comme suit

  findall(Motif,But(X1,...,Xn),Liste)

Étant donné un prédicat de But(X1,...,Xn) entre les variables X1,...,Xn et un motif Motif portant sur une partie des variables X1,...,Xn, la liste Liste contient toutes les instances de Motif qui ont rendu le but vrai. Si le But n'a pas de solution, Liste est vide.

Par exemple dans le TP sur la récursivité, le predicat inside(X,Y) était vrai si la poupée X était à l'intérieur de la poupée Y. Pour récupérer la liste de toutes les poupées à l'intérieur de katarina il suffit d'effectuer la requête :

  ?- findall(X,inside(X,katarina),L).

• Construire le prédicat

successeurs(C,LC)

qui est vrai si la liste LC est celle de tous les successeurs de la configuration C.

Chemin dans le graphe d'exécution

Le programme développé doit trouver un cheminement entre l'état initial et un état final. Ces déplacements peuvent être mémorisés à l'aide d'une liste de paires ((X,Y),D) où (X,Y) sont les coordonnées de la pièce qui bouge et D est la direction dans laquelle cette pièce bouge.

• Modifier le prédicat successeurs développé ci-avant de sorte que

successeurs(C-Ch,LC)

est vrai lorsque C est la configuration dans laquelle le système est Ch est le chemin qu'il a fallu parcourir (depuis l'état initial) pour arriver à la configuration C et LC est la liste de toutes les paires (Cp-((X,Y),D)) où

• Cp est le successeur de C lorsqu'on
• fait bouger la pièce aux coordonnées (X,Y)
• dans la direction D

Les chemins peuvent être modélisés comme une liste [((Xn,Yn),Dn),...,((X3,Y3),D3),((X2,Y2),D2),((X1,Y1),D1)] qui stipule qu'on a

• d'abord déplacé la pièce situé en (X1,Y1) selon la direction D1 ;
• ensuite déplacé la pièce situé en (X2,Y2) selon la direction D2 ;
• ...
• enfin déplacé la pièce situé en (Xn,Yn) selon la direction Dn.

Ce qui vous est fourni

Le code Prolog effectuant un parcours en largeur d'abord vous est fourni ci-dessous.

Commencer par insérer en tête de votre fichier Prolog

  :-use_module(library(assoc)).

Insérer à la suite le programme suivant :

    de tous les successeurs des configurations de la liste L*/

    successeurs_liste(L,Sl):-
      maplist(successeurs,L,Lp),
      flatten(Lp,Lpp),
      list_to_assoc(Lpp,A),
      assoc_to_list(A,Sl).

    L3 est la liste de tous les éléments Conf-_ de L1 dont 
    Conf n appartient pas à L2 */ 

    list_minus([],_,[]).
    list_minus([Conf-_|L1],L2,Res):-
      member(Conf,L2),!,
      list_minus(L1,L2,Res).
    list_minus([El|L1],L2,[El|Res]):-
      list_minus(L1,L2,Res).

    filtre_conf(X-_,X).

    finale et si Ch est le chemin qui a mené a cette configuration */

    but([Conf-Chemin|_],Chemin):-final(Conf),!.
    but([_|L],Chemin):-but(L,Chemin).

    Atraiter est la liste des configurations-chemins qu il reste à visiter
    Visites est la liste des configurations déjà visités
    C est l entier représentant la profondeur de recherche
    Res est le chemin menant à une configuration finale */

    largeur(Atraiter,_,_,Res):-
      but(Atraiter,Res),!.
    largeur(Atraiter,Visites,C,Res):-
      Cp is C+1,
      writef("boucle %d \n",[C]),
      maplist(filtre_conf,Atraiter,V1),
      append(V1,Visites,Omis),
      successeurs_liste(Atraiter,Succ),
      list_minus(Succ,Omis,Atraiter2),
      largeur(Atraiter2,Omis,Cp,Res).

   Dans ce cas, la solution est affichée. */

   resoud(_):-
     get_time(T0),
     init(X),
     largeur([X-[]],[],0,Res),
     writeln(Res),
     get_time(T1),
     DT1 is T1 - T0,
     writef('Duree : % \n',[DT1]).