tpProlog/anerouge_old/anerougeCoord.pl

   1 :- use_module(library(clpfd)).
   2 :- use_module(library(lists)).
   3
   4 /* accesseurs sur ligne et colonne*/
   5
   6
   7 repr(1,'j').
   8 repr(2,'j').
   9 repr(3,'j').
  10 repr(4,'j').
  11 repr(5,'r').
  12 repr(6,'r').
  13 repr(7,'r').
  14 repr(8,'r').
  15 repr(9,'m').
  16 repr(10,'m').
  17 repr(11,'n').
  18 repr(12,'n').
  19 repr(13,'n').
  20 repr(14,'n').
  21 repr(15,'b').
  22 repr(16,'b').
  23 repr(17,'w').
  24 repr(18,'w').
  25 repr(19,' ').
  26 repr(20,' ').
  27
  28
  29 piece(1,jaunea1).
  30 piece(2,jaunea2).
  31 piece(3,jauneb1).
  32 piece(4,jauneb2).
  33 piece(5,rouge1).
  34 piece(6,rouge2).
  35 piece(7,rouge3).
  36 piece(8,rouge4).
  37 piece(9,marron1).
  38 piece(10,marron2).
  39 piece(11,noira1).
  40 piece(12,noira2).
  41 piece(13,noirb1).
  42 piece(14,noirb2).
  43 piece(15,blanc1).
  44 piece(16,blanc2).
  45 piece(17,bois1).
  46 piece(18,bois2).
  47 piece(19,vide1).
  48 piece(20,vide2).
  49
  50 dir(d,1).
  51 dir(g,-1).
  52 dir(h,+1).
  53 dir(b,-1).
  54
  55
  56 piece_abs(1,1).
  57 piece_abs(2,1).
  58 piece_abs(3,1).
  59 piece_abs(4,1).
  60 piece_abs(5,5).
  61 piece_abs(6,5).
  62 piece_abs(7,5).
  63 piece_abs(8,5).
  64 piece_abs(9,9).
  65 piece_abs(10,9).
  66 piece_abs(11,11).
  67 piece_abs(12,11).
  68 piece_abs(13,11).
  69 piece_abs(14,11).
  70 piece_abs(15,15).
  71 piece_abs(16,15).
  72 piece_abs(17,9).
  73 piece_abs(18,9).
  74 piece_abs(19,19).
  75 piece_abs(20,19).
  76
  77 line_abs([],[]).
  78 line_abs([X|R],[Y|Rp]):-
  79     line_abs(R,Rp),
  80     piece_abs(X,Y).
  81
  82 conf_abs([],[]).
  83 conf_abs([X|R],[Y|Rp]):-
  84     conf_abs(R,Rp),
  85     line_abs(X,Y).
  86
  87 equiv(Conf1,Conf2):-
  88     conf_abs(Conf1,C),
  89     conf_abs(Conf2,C).
  90
  91
  92
  93 colonne(1,[A,_,_,_],A).
  94 colonne(2,[_,A,_,_],A).
  95 colonne(3,[_,_,A,_],A).
  96 colonne(4,[_,_,_,A],A).
  97
  98 ligne(1,[A,_,_,_,_],A).
  99 ligne(2,[_,A,_,_,_],A).
 100 ligne(3,[_,_,A,_,_],A).
 101 ligne(4,[_,_,_,A,_],A).
 102 ligne(5,[_,_,_,_,A],A).
 103
 104
 105
 106
 107
 108 /* retourne le contenu "Contenu_case" de la case
 109 situé à la colonne "Col" et la ligne "Lig" du jeux en cours
 110 "Contenu_jeu" */
 111
 112 case(Lig,Col,Conf,Contenu) :-
 113     ligne(Lig,Conf,Ligne),
 114     colonne(Col,Ligne,Contenu).
 115
 116
 117 changeContenuColonne(1,X,[_,B,C,D],[X,B,C,D]).
 118 changeContenuColonne(2,X,[A,_,C,D],[A,X,C,D]).
 119 changeContenuColonne(3,X,[A,B,_,D],[A,B,X,D]).
 120 changeContenuColonne(4,X,[A,B,C,_],[A,B,C,X]).
 121
 122
 123 changeContenuLigne(1,X,[_,B,C,D,E],[X,B,C,D,E]).
 124 changeContenuLigne(2,X,[A,_,C,D,E],[A,X,C,D,E]).
 125 changeContenuLigne(3,X,[A,B,_,D,E],[A,B,X,D,E]).
 126 changeContenuLigne(4,X,[A,B,C,_,E],[A,B,C,X,E]).
 127 changeContenuLigne(5,X,[A,B,C,D,_],[A,B,C,D,X]).
 128
 129
 130
 131 changeContenu(Conf1,Piece,Y,X,Conf2):-
 132     ligne(Y,Conf1,Ligne),
 133     changeContenuColonne(X,Piece,Ligne,Lignep),
 134     changeContenuLigne(Y,Lignep,Conf1,Conf2).
 135
 136
 137
 138
 139 /*equiv(X,X).
 140 equiv(X,Z):-
 141     equiv(X,Y),equiv(Y,Z).
 142 equiv(Conf1,Conf2):-
 143     ((piece(P1,jaunea1),piece(P2,jauneb1));
 144      (piece(P1,noira1),piece(P2,noirb1))),
 145     P1p is P1+1,
 146     P2p is P2+1,
 147     case(Lig1,Col1,Conf1,P1),
 148     Lig1p  is Lig1 +1,
 149     case(Lig2,Col2,Conf1,P2),
 150     Lig2p  is Lig2 +1,
 151     changeContenu(Conf1,P1,Lig2,Col2,Conf1b),
 152     changeContenu(Conf1b,P1p,Lig2p,Col2,Conf1c),
 153     changeContenu(Conf1c,P2,Lig1,Col1,Conf1d),
 154     changeContenu(Conf1d,P2p,Lig1p,Col1,Conf2).
 155
 156 equiv(Conf1,Conf2):-
 157     ((piece(P1,bois1),piece(P2,bois2));
 158      (piece(P1,marron1),piece(P2,marron2))),
 159     case(Lig1,Col1,Conf1,P1),
 160     case(Lig2,Col2,Conf1,P2),
 161     changeContenu(Conf1,P1,Lig2,Col2,Conf1b),
 162     changeContenu(Conf1b,P2,Lig1,Col1,Conf2).
 163 */
 164
 165
 166 mapto_el([],[]).
 167 mapto_el([Xp|Lp],[X|L]):-
 168     mapto_el(Lp,L),
 169     piece(Xp,X).
 170
 171 mapto([],[]).
 172 mapto([Xp|Lp],[X|L]):-
 173     mapto_el(Xp,X),
 174     mapto(Lp,L).
 175
 176
 177
 178
 179 initC([
 180     [jaunea1,rouge1,rouge2,jauneb1],
 181     [jaunea2,rouge3,rouge4,jauneb2],
 182     [noira1,blanc1,blanc2,noirb1],
 183     [noira2,bois1,bois2,noirb2],
 184     [marron1,vide1,vide2,marron2]]).
 185 /*
 186 initC([
 187     [jaunea1,rouge1,rouge2,jauneb1],
 188     [jaunea2,rouge3,rouge4,jauneb2],
 189     [blanc1,blanc2,marron1,noira1],
 190     [bois1,noirb1,bois2,noira2],
 191     [marron2,noirb2,vide1,vide2]]).
 192 */
 193 init(X):-
 194     initC(Y),mapto(X,Y).
 195
 196 /*final([
 197     [jaunea1,rouge1,rouge2,jauneb1],
 198     [jaunea2,rouge3,rouge4,jauneb2],
 199     [noira1,blanc1,blanc2,noirb1],
 200     [noira2,bois,bois,noirb2],
 201     [marron1,vide1,vide2,marron2]]).
 202
 203
 204 final([
 205     [_,_,_,_],
 206     [_,_,_,_],
 207     [_,_,_,_],
 208     [_,rouge1,rouge2,_],
 209     [_,rouge3,rouge4,_]]).
 210 */
 211
 212 finalC([
 213     [_,_,_,_],
 214     [_,_,_,_],
 215     [_,_,_,_],
 216     [_,noira1,noirb1,_],
 217     [_,noira2,noirb2,_]]).
 218
 219 final(X):-
 220     finalC(Y),
 221     mapto(X,Y).
 222
 223
 224
 225
 226 jauneaOK(Conf):-
 227     case(Lig,Col,Conf,P),
 228     piece(P,jaunea1),
 229     piece(Pp,jaunea2),
 230     Ligp is Lig +1,
 231     case(Ligp,Col,Conf,Pp).
 232 jaunebOK(Conf):-
 233     case(Lig,Col,Conf,P),
 234     piece(P,jauneb1),
 235     piece(Pp,jauneb2),
 236     Ligp is Lig +1,
 237     case(Ligp,Col,Conf,Pp).
 238 noiraOK(Conf):-
 239     case(Lig,Col,Conf,P),
 240     piece(P,noira1),
 241     piece(Pp,noira2),
 242     Ligp is Lig +1,
 243     case(Ligp,Col,Conf,Pp).
 244 noirbOK(Conf):-
 245     case(Lig,Col,Conf,P),
 246     piece(P,noirb1),
 247     piece(Pp,noirb2),
 248     Ligp is Lig +1,
 249     case(Ligp,Col,Conf,Pp).
 250 rougeOK(Conf):-
 251     case(Lig,Col,Conf,P1),
 252     piece(P1,rouge1),
 253     piece(P2,rouge2),
 254     piece(P3,rouge3),
 255     piece(P4,rouge4),
 256     Ligp is Lig +1,
 257     Colp is Col + 1,
 258     case(Lig,Colp,Conf,P2),
 259     case(Ligp,Col,Conf,P3),
 260     case(Ligp,Colp,Conf,P4).
 261 blancOK(Conf):-
 262     case(Lig,Col,Conf,P),
 263     piece(P,blanc1),
 264     piece(Pp,blanc2),
 265     Colp is Col+1,
 266     case(Lig,Colp,Conf,Pp).
 267
 268
 269
 270 couleurOK(Conf):-
 271     jauneaOK(Conf),jaunebOK(Conf),noiraOK(Conf),noirbOK(Conf),rougeOK(Conf),
 272     blancOK(Conf).
 273
 274
 275 /*** Une configuration est correcte si
 276      - chaque case est remplie
 277      - avec une piece différente
 278      - en respectant les contraintes de couleur
 279 ***/
 280 correct(Conf):-
 281     Conf = [[A1,A2,A3,A4],
 282             [B1,B2,B3,B4],
 283             [C1,C2,C3,C4],
 284             [D1,D2,D3,D4],
 285             [E1,E2,E3,E4]],
 286     ins([A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,D3,D4,E1,E2,E3,E4],
 287            1..20),
 288     all_distinct([A1,A2,A3,A4,B1,B2,B3,B4,C1,C2,C3,C4,D1,D2,D3,D4,E1,E2,E3,E4]),
 289     couleurOK(Conf).
 290
 291
 292
 293
 294
 295 /*glissement rouge*/
 296 /* vers la droite */
 297 glissement(PR1,d,Conf1,Conf2):-
 298     case(Lig,Col,Conf1,PR1),
 299     piece(PR1,rouge1),
 300     piece(PR2,rouge2),
 301     piece(PR3,rouge3),
 302     piece(PR4,rouge4),
 303     Ligp is Lig+1,
 304     Colp is Col+1,
 305     Colpp is Col+2,
 306     case(Lig,Colpp,Conf1,PV1),
 307     case(Ligp,Colpp,Conf1,PV2),
 308     ((piece(PV1,vide1),piece(PV1,vide2));
 309      (piece(PV2,vide2),piece(PV2,vide1))),
 310     changeContenu(Conf1,PR1,Lig,Colp,Conf1a),
 311     changeContenu(Conf1a,PR2,Lig,Colpp,Conf1b),
 312     changeContenu(Conf1b,PV1,Lig,Col,Conf1c),
 313     changeContenu(Conf1c,PR3,Ligp,Colp,Conf1d),
 314     changeContenu(Conf1d,PR4,Ligp,Colpp,Conf1e),
 315     changeContenu(Conf1e,PV2,Ligp,Col,Conf2).
 316
 317 /*vers la gauche */
 318 glissement(PR1,g,Conf1,Conf2):-
 319     case(Lig,Col,Conf1,PR1),
 320     piece(PR1,rouge1),
 321     piece(PR2,rouge2),
 322     piece(PR3,rouge3),
 323     piece(PR4,rouge4),
 324     Ligp is Lig+1,
 325     Colm is Col-1,
 326     Colp is Col+1,
 327     case(Lig,Colm,Conf1,PV1),
 328     case(Ligp,Colm,Conf1,PV2),
 329     ((piece(PV1,vide1),piece(PV2,vide2));
 330      (piece(PV1,vide2),piece(PV2,vide1))),
 331     changeContenu(Conf1,PR1,Lig,Colm,Conf1a),
 332     changeContenu(Conf1a,PR2,Lig,Col,Conf1b),
 333     changeContenu(Conf1b,PV1,Lig,Colp,Conf1c),
 334     changeContenu(Conf1c,PR3,Ligp,Colm,Conf1d),
 335     changeContenu(Conf1d,PR4,Ligp,Col,Conf1e),
 336     changeContenu(Conf1e,PV2,Ligp,Colp,Conf2).
 337
 338 /* vers le bas */
 339 glissement(PR1,b,Conf1,Conf2):-
 340     case(Lig,Col,Conf1,PR1),
 341     piece(PR1,rouge1),
 342     piece(PR2,rouge2),
 343     piece(PR3,rouge3),
 344     piece(PR4,rouge4),
 345     Ligp is Lig+1,
 346     Colp is Col+1,
 347     Ligpp is Lig+2,
 348     case(Ligpp,Col,Conf1,PV1),
 349     case(Ligpp,Colp,Conf1,PV2),
 350     ((piece(PV1,vide1),piece(PV2,vide2));
 351      (piece(PV1,vide2),piece(PV2,vide1))),
 352     changeContenu(Conf1,PR1,Ligp,Col,Conf1a),
 353     changeContenu(Conf1a,PR2,Ligp,Colp,Conf1b),
 354     changeContenu(Conf1b,PV1,Lig,Col,Conf1c),
 355     changeContenu(Conf1c,PR3,Ligpp,Col,Conf1d),
 356     changeContenu(Conf1d,PR4,Ligpp,Colp,Conf1e),
 357     changeContenu(Conf1e,PV2,Lig,Colp,Conf2).
 358
 359
 360 /* vers le haut */
 361 glissement(PR1,h,Conf1,Conf2):-
 362     case(Lig,Col,Conf1,PR1),
 363     piece(PR1,rouge1),
 364     piece(PR2,rouge2),
 365     piece(PR3,rouge3),
 366     piece(PR4,rouge4),
 367     Ligp is Lig+1,
 368     Colp is Col+1,
 369     Ligm is Lig-1,
 370     case(Ligm,Col,Conf1,PV1),
 371     case(Ligm,Colp,Conf1,PV2),
 372     ((piece(PV1,vide1),piece(PV2,vide2));
 373      (piece(PV1,vide2),piece(PV2,vide1))),
 374     changeContenu(Conf1,PR1,Ligm,Col,Conf1a),
 375     changeContenu(Conf1a,PR2,Ligm,Colp,Conf1b),
 376     changeContenu(Conf1b,PV1,Ligp,Col,Conf1c),
 377     changeContenu(Conf1c,PR3,Lig,Col,Conf1d),
 378     changeContenu(Conf1d,PR4,Lig,Colp,Conf1e),
 379     changeContenu(Conf1e,PV2,Ligp,Colp,Conf2).
 380
 381
 382
 383
 384
 385 /* glissement noir,jaune */
 386 /* vers la droite */
 387 glissement(Pc1,d,Conf1,Conf2):-
 388     case(Lig,Col,Conf1,Pc1),
 389     (piece(Pc1,noira1);piece(Pc1,noirb1);piece(Pc1,jaunea1);piece(Pc1,jauneb1)),
 390     Pc2 is Pc1 +1,
 391     Ligp is Lig+1,
 392     Colp is Col+1,
 393     case(Lig,Colp,Conf1,PV1),
 394     case(Ligp,Colp,Conf1,PV2),
 395     ((piece(PV1,vide1),piece(PV2,vide2));
 396      (piece(PV1,vide2),piece(PV2,vide1))),
 397     changeContenu(Conf1,Pc1,Lig,Colp,Conf1a),
 398     changeContenu(Conf1a,Pc2,Ligp,Colp,Conf1b),
 399     changeContenu(Conf1b,PV1,Lig,Col,Conf1c),
 400     changeContenu(Conf1c,PV2,Ligp,Col,Conf2).
 401
 402 /* vers la gauche */
 403 glissement(Pc1,g,Conf1,Conf2):-
 404     case(Lig,Col,Conf1,Pc1),
 405     (piece(Pc1,noira1);piece(Pc1,noirb1);piece(Pc1,jaunea1);piece(Pc1,jauneb1)),
 406     Pc2 is Pc1 +1,
 407     Ligp is Lig+1,
 408     Colp is Col-1,
 409     case(Lig,Colp,Conf1,PV1),
 410     case(Ligp,Colp,Conf1,PV2),
 411     ((piece(PV1,vide1),piece(PV2,vide2));
 412      (piece(PV1,vide2),piece(PV2,vide1))),
 413     changeContenu(Conf1,Pc1,Lig,Colp,Conf1a),
 414     changeContenu(Conf1a,Pc2,Ligp,Colp,Conf1b),
 415     changeContenu(Conf1b,PV1,Lig,Col,Conf1c),
 416     changeContenu(Conf1c,PV2,Ligp,Col,Conf2).
 417
 418
 419 /* vers le bas */
 420
 421 glissement(Pc1,b,Conf1,Conf2):-
 422     case(Lig,Col,Conf1,Pc1),
 423     (piece(Pc1,noira1);piece(Pc1,noirb1);piece(Pc1,jaunea1);piece(Pc1,jauneb1)),
 424     Pc2 is Pc1 +1,
 425     Ligp is Lig+1,
 426     Ligpp is Lig+2,
 427     case(Ligpp,Col,Conf1,PV),
 428     (piece(PV,vide1);piece(PV,vide2)),
 429     changeContenu(Conf1,Pc1,Ligp,Col,Conf1a),
 430     changeContenu(Conf1a,Pc2,Ligpp,Col,Conf1b),
 431     changeContenu(Conf1b,PV,Lig,Col,Conf2).
 432
 433 /* vers le haut */
 434 glissement(Pc1,h,Conf1,Conf2):-
 435     case(Lig,Col,Conf1,Pc1),
 436     (piece(Pc1,noira1);piece(Pc1,noirb1);piece(Pc1,jaunea1);piece(Pc1,jauneb1)),
 437     Pc2 is Pc1 +1,
 438     Ligp is Lig+1,
 439     Ligm is Lig-1,
 440     case(Ligm,Col,Conf1,PV),
 441     (piece(PV,vide1);piece(PV,vide2)),
 442     changeContenu(Conf1,Pc1,Ligm,Col,Conf1a),
 443     changeContenu(Conf1a,Pc2,Lig,Col,Conf1b),
 444     changeContenu(Conf1b,PV,Ligp,Col,Conf2).
 445
 446
 447
 448 /* glissement du blanc */
 449 /* vers la droite */
 450 glissement(PB1,d,Conf1,Conf2):-
 451     case(Lig,Col,Conf1,PB1),
 452     piece(PB1,blanc1),
 453     piece(PB2,blanc2),
 454     Colpp is Col+2,
 455     Colp is Col+1,
 456     case(Lig,Colpp,Conf1,PV),
 457     (piece(PV,vide1);piece(PV,vide2)),
 458     changeContenu(Conf1,PB1,Lig,Colp,Conf1a),
 459     changeContenu(Conf1a,PB2,Lig,Colpp,Conf1b),
 460     changeContenu(Conf1b,PV,Lig,Col,Conf2).
 461
 462 /* vers la gauche */
 463 glissement(PB1,g,Conf1,Conf2):-
 464     case(Lig,Col,Conf1,PB1),
 465     piece(PB1,blanc1),
 466     piece(PB2,blanc2),
 467     Colm is Col-1,
 468     Colp is Col+1,
 469     case(Lig,Colm,Conf1,PV),
 470     (piece(PV,vide1);piece(PV,vide2)),
 471     changeContenu(Conf1,PB1,Lig,Colm,Conf1a),
 472     changeContenu(Conf1a,PB2,Lig,Col,Conf1b),
 473     changeContenu(Conf1b,PV,Lig,Colp,Conf2).
 474
 475
 476 /*vers le bas */
 477 glissement(PB1,b,Conf1,Conf2):-
 478     case(Lig,Col,Conf1,PB1),
 479     piece(PB1,blanc1),
 480     piece(PB2,blanc2),
 481     Ligp is Lig+1,
 482     Colp is Col+1,
 483     case(Ligp,Col,Conf1,PV1),
 484     case(Ligp,Colp,Conf1,PV2),
 485     ((piece(PV1,vide1),piece(PV2,vide2));
 486      (piece(PV1,vide2),piece(PV2,vide1))),
 487     changeContenu(Conf1,PB1,Ligp,Col,Conf1a),
 488     changeContenu(Conf1a,PB2,Ligp,Colp,Conf1b),
 489     changeContenu(Conf1b,PV1,Lig,Col,Conf1c),
 490     changeContenu(Conf1c,PV2,Lig,Colp,Conf2).
 491
 492
 493 /*vers le haut*/
 494 glissement(PB1,h,Conf1,Conf2):-
 495     case(Lig,Col,Conf1,PB1),
 496     piece(PB1,blanc1),
 497     piece(PB2,blanc2),
 498     Ligm is Lig-1,
 499     Colp is Col+1,
 500     case(Ligm,Col,Conf1,PV1),
 501     case(Ligm,Colp,Conf1,PV2),
 502     ((piece(PV1,vide1),piece(PV2,vide2));
 503      (piece(PV1,vide2),piece(PV2,vide1))),
 504     changeContenu(Conf1,PB1,Ligm,Col,Conf1a),
 505     changeContenu(Conf1a,PB2,Ligm,Colp,Conf1b),
 506     changeContenu(Conf1b,PV1,Lig,Col,Conf1c),
 507     changeContenu(Conf1c,PV2,Lig,Colp,Conf2).
 508
 509
 510
 511 /* vers la gauche*/
 512 glissement(PC,g,Conf1,Conf2):-
 513     case(Lig,Col,Conf1,PC),
 514     (piece(PC,bois1);piece(PC,bois2);piece(PC,marron1);piece(PC,marron2)),
 515     Colp is Col-1,
 516     case(Lig,Colp,Conf1,PV),
 517     (piece(PV,vide1);piece(PV,vide2)),
 518     changeContenu(Conf1,PC,Lig,Colp,Conf1a),
 519     changeContenu(Conf1a,PV,Lig,Col,Conf2).
 520
 521 /* vers la droite */
 522 glissement(PC,d,Conf1,Conf2):-
 523     case(Lig,Col,Conf1,PC),
 524     (piece(PC,bois1);piece(PC,bois2);piece(PC,marron1);piece(PC,marron2)),
 525     Colp is Col+1,
 526     case(Lig,Colp,Conf1,PV),
 527     (piece(PV,vide1);piece(PV,vide2)),
 528     changeContenu(Conf1,PC,Lig,Colp,Conf1a),
 529     changeContenu(Conf1a,PV,Lig,Col,Conf2).
 530
 531
 532
 533 /* vers le haut*/
 534 glissement(PC,h,Conf1,Conf2):-
 535     case(Lig,Col,Conf1,PC),
 536     (piece(PC,bois1);piece(PC,bois2);piece(PC,marron1);piece(PC,marron2)),
 537     Ligp is Lig-1,
 538     case(Ligp,Col,Conf1,PV),
 539     (piece(PV,vide1);piece(PV,vide2)),
 540     changeContenu(Conf1,PC,Ligp,Col,Conf1a),
 541     changeContenu(Conf1a,PV,Lig,Col,Conf2).
 542
 543
 544 /* vers  le  bas */
 545 glissement(PC,b,Conf1,Conf2):-
 546     case(Lig,Col,Conf1,PC),
 547     (piece(PC,bois1);piece(PC,bois2);piece(PC,marron1);piece(PC,marron2)),
 548     Ligp is Lig+1,
 549     case(Ligp,Col,Conf1,PV),
 550     (piece(PV,vide1);piece(PV,vide2)),
 551     changeContenu(Conf1,PC,Ligp,Col,Conf1a),
 552     changeContenu(Conf1a,PV,Lig,Col,Conf2).
 553
 554
 555
 556 /*resoud(Conf,[Conf]) :- init(Conf).
 557
 558 resoud(Conf,[Conf|Historique]) :-
 559     correct(Conf),
 560     glissement(Conf,Confp),
 561     resoud(Confp,Historique),
 562     not(member(Conf,Historique)).
 563
 564
 565 test(Depl):-
 566     correct(X),
 567     final(X),
 568     resoud(X,Depl).
 569
 570 */
 571
 572 /* ajoute la nouvelle paire (Conf, deplacements) à la fin en s'assurant
 573    que la conf n'a pas encore été visitéé */
 574
 575 insert_fin((X,Y),[],[(X,Y)]).
 576 insert_fin((X,_),[(Y,K)|R1],[(Y,K)|R1]):-
 577     equiv(X,Y),!.
 578 insert_fin(X,[T|R1],[T|R2]):-
 579     insert_fin(X,R1,R2).
 580
 581 insert_fin_liste([],L,L).
 582 insert_fin_liste([X|R],L,Res):-
 583     insert_fin_liste(R,L,Resp),
 584     insert_fin(X,Resp,Res).
 585
 586
 587
 588 display_ligne([]).
 589 display_ligne([El|R]):-
 590     repr(El,Rep_el),
 591     write(Rep_el),
 592     display_ligne(R).
 593
 594 display_conf([]).
 595 display_conf([L|R]):-
 596     display_ligne(L),
 597     writeln(''),
 598     display_conf(R).
 599
 600 display_chemin(L):-
 601     write(L).
 602
 603 display_conf_chemin((Conf,Chemin)):-
 604     display_conf(Conf),display_chemin(Chemin).
 605
 606 display_conf_chemin_liste([]).
 607 display_conf_chemin_liste([CL|R]):-
 608     display_conf_chemin(CL),
 609     writeln(''),
 610     display_conf_chemin_liste(R).
 611
 612
 613
 614
 615
 616 /* Tous les successeurs d une configuration */
 617 successeurs((Confa,Chemins),L):-
 618     findall(
 619         (Confb,[(P,D)|Chemins]),
 620         glissement(P,D,Confa,Confb),
 621         L).
 622
 623
 624 successeurs_liste([],[]).
 625 successeurs_liste([Ca|Cs],ConfsSucc):-
 626     successeurs(Ca,L),
 627     successeurs_liste(Cs,ConfsSuccInter),
 628     insert_fin_liste(L,ConfsSuccInter,ConfsSucc).
 629
 630
 631     /* regarde si le premier parametre appartient
 632      à la liste donné en second parametre. Si c est le cas,
 633     retourne le chemin */
 634
 635
 636 appartient((Conf1,_),[(Conf2,_)|_]):-
 637     equiv(Conf1,Conf2),!.
 638 appartient((Conf1,C),[_|L]):-
 639     appartient((Conf1,C),L).
 640
 641 difference([],_,[]).
 642 difference([El|L1],L2,[El|Res]):-
 643     difference(L1,L2,Res),
 644     not(appartient(El,L2)).
 645 difference([El|L1],L2,Res):-
 646     difference(L1,L2,Res),
 647     appartient(El,L2).
 648
 649
 650
 651 but([(Conf,Chemin)|_],Chemin):-final(Conf).
 652 but([_|L],Chemin):-but(L,Chemin).
 653
 654
 655 largeur(Atraiter,_,Res):-
 656     but(Atraiter,Res),!.
 657 largeur(Atraiter,Visites,Res):-
 658     successeurs_liste(Atraiter,Succ),
 659     difference(Succ,Visites,Atraiter2),
 660     insert_fin_liste(Atraiter,Visites,Visites2),
 661     largeur(Atraiter2,Visites2,Res).
 662
 663
 664 resoud(Res):-
 665     init(X),
 666     largeur([(X,[])],[],Res).
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679 /*
 680 resoud(L,):-
 681     ne_contient_pas_la_conf_finalle(X,L,Chemin),
 682     successeurs_liste(L,Lp),
 683     resoud(Lp,Chemin).
 684
 685 */