1 PROGRAM BACKTRACKING ;
\r
3 (*************************************************************************)
\r
4 (* Programme : BACKTRAC.LOG *)
\r
5 (* Date : 04/03/93 *)
\r
6 (* Auteur : SIMON Philippe LICENCE INFORMATIQUE 1992/93 *)
\r
8 (* Ce programme permet d'effectuer des op
\82rations de retour arri
\8are *)
\r
9 (* de fa
\87on intelligente. Pour cela 2 exemples de BACKTRACKING ont
\82t
\82 *)
\r
10 (* choisi. La Gestion du Planning d'une Semaine et le Probl
\8ame des Pions *)
\r
11 (* Noirs et Blancs. Le choix de ces 2 exemples ce faisant par un MENU *)
\r
13 (*************************************************************************)
\r
17 VAR choix,touche : integer,
\r
21 (*************************************************************************)
\r
22 (* METHODES USUELLES *)
\r
24 (* Cette partie contient des m
\82thodes usuelles de travail (BIBLIOTHEQUE) *)
\r
25 (*************************************************************************)
\r
28 UNIT eff : PROCEDURE ;
\r
29 (* envoie un ordre d'
\82ffacer l'
\82cran *)
\r
32 WRITE( chr(27), "[2J");
\r
36 UNIT GetCar : IIuwgraph FUNCTION : INTEGER;
\r
37 (* attend que l'utilisateur tape une touche et renvoie le code ASCII *)
\r
49 UNIT attendre : PROCEDURE(t : integer);
\r
50 (* Procedure permettant d'attendre pendant 't' seconde(s) *)
\r
56 while (ABS(j - TIME) < t) do od;
\r
60 (*--------------------------------------------------------------*)
\r
61 (* PROCEDURE li
\82es la gestion du MENU Principal *)
\r
62 (*--------------------------------------------------------------*)
\r
64 UNIT menu : PROCEDURE ;
\r
65 (* Appelle les m
\82thodes correspondantes au choix de l'utilisateur *)
\r
67 VAR boucle : BOOLEAN;
\r
75 WRITELN (" ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿");
\r
76 WRITELN (" ³ M E N U ³");
\r
78 WRITELN (" ³ 'BACKTRACKING INTELLIGENT' ³");
\r
81 WRITELN (" ³ 0.......... QUITTER ³");
\r
84 WRITELN (" ³ 1 ..... Gestion du planning de la ³");
\r
85 WRITELN (" ³ semaine. ³");
\r
87 WRITELN (" ³ 2 ..... Probl
\8ame des pions noirs ³");
\r
88 WRITELN (" ³ et blancs. ³");
\r
91 WRITELN (" ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ");
\r
93 WRITE (" Entrez votre choix : ");
\r
97 WHEN 0 : boucle := FALSE;
\r
109 (***************************************************************************)
\r
110 (* LA PARTIE GESTION DU PLANNING DE LA SEMAINE *)
\r
112 (* il s'agit ici de la DECLARATION de l'objet SEM *)
\r
113 (* (utilise la biblioth
\8aque Graphique IIugraph) *)
\r
114 (***************************************************************************)
\r
117 UNIT SEM : IIuwgraph CLASS;
\r
119 VAR i,cpt,ex,pl,et,arg,retour,val,N,N2,M : integer,
\r
120 exercice,plaisir,argent,etude,interv,interv2,interv3 : integer,
\r
121 MA,ME,JE,res : ARRAYOF integer,
\r
122 L1,L2,V1,V2 : ARRAYOF ARRAYOF integer,
\r
123 solution_possible : boolean;
\r
125 UNIT recurs : PROCEDURE(i : integer, res : ARRAYOF integer);
\r
126 (* recurs est la proc
\82dure principale, appel
\82e de fa
\87on recursive *)
\r
127 (* afin de cr
\82er l'arboresence de tous les cas possibles d'une *)
\r
128 (* Gestion de Semaine. A l'interieur de cette proc
\82dure nous avons *)
\r
129 (* 6 autres sous_proc
\82dures li
\82es aux 6 premiers jours de la *)
\r
130 (* semaine (LUNDI MARDI MERCREDI JEUDI VENDREDI). Chacune de ces *)
\r
131 (* proc
\82dures est propre
\85 un test,
\85 des affectation et
\85 des *)
\r
132 (* retours arri
\8ares particuliers. *)
\r
133 (* Chaque solution trouv
\82e est rang
\82e dans le tableau 'res'. *)
\r
140 UNIT lundi : PROCEDURE;
\r
141 (* La proc
\82dure lundi correspond en quelque sorte
\85 la racine *)
\r
142 (* de l'arbre de gestion de la semaine. Les affectations *)
\r
143 (* touchent ici les exercices, le plaisir, et l'argent. De plus *)
\r
144 (* on g
\8are, grace
\85 la variable retour, les retours arri
\8ares *)
\r
145 (* afin de calculer les branches de l'arbre
\85 \82laguer. *)
\r
153 (* on initialise les variables de travail li
\82es
\r
154 aux exercices, aux plaisirs, et
\85 l'argent *)
\r
155 ex := 0; pl := 0; arg := 0; et := 0;
\r
157 res(i+1) := L2(2,j);
\r
158 res(i+2) := L1(1,w) + L2(1,j);
\r
159 (* On incr
\82mente les variables de travail *)
\r
161 pl := pl + res(i+1);
\r
162 arg := arg + res(i+2);
\r
164 (* appel de la procedure recurs correspondant au mardi *)
\r
165 CALL recurs(i+1,res);
\r
167 (* On decrement les variable de travail *)
\r
169 pl := pl - res(i+1);
\r
170 arg := arg - res(i+2);
\r
172 (* retour = 4 ou 5 correspond au vendredi *)
\r
173 IF retour = 4 THEN w := (exercice - val)/interv2;
\r
176 IF retour = 5 THEN j := (plaisir - val);
\r
182 solution_possible := FALSE;
\r
185 UNIT mardi : PROCEDURE;
\r
186 (* La proc
\82dure mardi correspond
\85 la seconde tranche de l'arbre*)
\r
187 (* de gestion de la semaine. Les affectations touchent ici les *)
\r
189 (* On g
\8are, grace
\85 la variable retour, les retours arri
\8ares du *)
\r
190 (* mercredi afin de calculer les branches de l'arbre
\85 \82laguer. *)
\r
198 (* On incremente les variable de travail *)
\r
199 et := et + res(i+2);
\r
201 (* appel de la procedure recurs correspondant au mercredi *)
\r
202 CALL recurs(i+1,res);
\r
204 (* On decremente les variable de travail *)
\r
205 et := et - res(i+2);
\r
207 (* retour = 2 correspond au mercredi *)
\r
208 IF retour = 2 THEN w := (etude - val)/interv;
\r
209 IF w >= N THEN retour := 1;
\r
214 solution_possible := FALSE;
\r
219 UNIT mercredi : PROCEDURE;
\r
220 (* La proc
\82dure mercredi correspond
\85 la troisi
\8ame tranche de *)
\r
221 (* l'arbre de gestion de la semaine. Les affectations touchent *)
\r
222 (* ici les
\82tudes. *)
\r
223 (* On g
\8are, grace
\85 la variable retour, les retours arri
\8ares du *)
\r
224 (* jeudi afin de calculer les branches de l'arbre
\85 \82laguer. *)
\r
231 (* On incremente les variable de travail *)
\r
232 et := et + res(i+2);
\r
234 (* appel de la procedure recurs correspondant au jeudi *)
\r
235 CALL recurs(i+1,res);
\r
237 (* On decremente les variable de travail *)
\r
238 et := et - res(i+2);
\r
240 (* retour = 3 correspond au jeudi *)
\r
241 IF retour = 3 THEN w := (etude - val)/interv;
\r
242 IF w >= N THEN retour := 2;
\r
243 val := val + ME(N);
\r
248 solution_possible := FALSE;
\r
252 UNIT jeudi : PROCEDURE;
\r
253 (* La proc
\82dure jeudi correspond
\85 la quartri
\8ame tranche de *)
\r
254 (* l'arbre de gestion de la semaine. Les affectations touchent *)
\r
255 (* ici les
\82tudes. *)
\r
256 (* On g
\8are, grace
\85 la variable retour, les retours arri
\8ares du *)
\r
257 (* jeudi au mercredi afin de calculer les branches de l'arbre
\85 *)
\r
265 (* On incremente les variable de travail *)
\r
266 et := et + res(i+2);
\r
268 (* si aucun cas n'est trouv
\82 on indique un
\r
269 retour arri
\8are et on calcul grace
\85 la
\r
270 variable val et a l'indice de boucle w
\r
271 les branches
\85 \82laguer. *)
\r
273 IF w = N THEN retour := 3;
\r
275 ELSE w := (etude - et)/interv;
\r
276 IF w>=N THEN w := N - 1 FI;
\r
279 (* appel de la procedure recurs correspondant
\r
281 CALL recurs(i+1,res);
\r
283 (* On decremente les variable de travail *)
\r
284 et := et - res(i+2);
\r
287 solution_possible := FALSE;
\r
291 UNIT vendredi : PROCEDURE;
\r
292 (* La proc
\82dure vendredi correspond
\85 la cinqui
\8ame tranche de *)
\r
293 (* l'arbre de gestion de la semaine. Les affectations touchent *)
\r
294 (* ici les exercices, le plaisir, et l'argent. *)
\r
295 (* On g
\8are, grace
\85 la variable retour, les retours arri
\8ares du *)
\r
296 (* lundi afin de calculer les branches de l'arbre
\85 \82laguer. *)
\r
303 res(i+2) := V1(2,w);
\r
304 res(i+3) := V2(2,j);
\r
305 res(i+4) := V1(1,w) + V2(1,j);
\r
306 (* On incremente les variable de travail *)
\r
307 ex := ex + res(i+2);
\r
308 pl := pl + res(i+3);
\r
309 arg := arg + res(i+4);
\r
310 IF arg > argent THEN j := M;
\r
312 IF ex < exercice THEN
\r
313 (* si aucun cas n'est trouv
\82 on indique un
\r
314 retour arri
\8are et on calcul grace
\85 la
\r
315 variable val et
\85 l'indice de boucle w
\r
316 les branches
\85 \82laguer. *)
\r
318 IF w = N THEN retour := 4;
\r
321 ELSE w := ((exercice - ex)/interv2);
\r
322 IF w >= N THEN w := N-1 FI;
\r
326 IF pl < plaisir THEN
\r
327 (* si aucun cas n'est trouv
\82 on indique un
\r
328 retour arri
\8are et on calcul grace
\85 la
\r
329 variable val et a l'indice de boucle j
\r
330 les branches
\85 \82laguer. *)
\r
332 IF j = M THEN retour := 5;
\r
334 ELSE j := (plaisir - pl)/interv3;
\r
336 (* appel de la procedure recurs correspondant
\r
337 \85 une solution trouv
\82e *)
\r
338 ELSE CALL recurs(i+1,res);
\r
342 (* On decremente les variable de travail *)
\r
343 ex := ex - res(i+2);
\r
344 pl := pl - res(i+3);
\r
345 arg := arg - res(i+4);
\r
348 solution_possible := FALSE;
\r
356 solution_possible := TRUE;
\r
360 WHEN 1 : CALL lundi;
\r
362 WHEN 2 : CALL mardi;
\r
364 WHEN 3 : CALL mercredi;
\r
366 WHEN 4 : CALL jeudi;
\r
368 WHEN 5 : CALL vendredi;
\r
372 (* si une solution est trouv
\82e on l'imprime
\85 l'
\82cran *)
\r
373 IF solution_possible THEN CALL imprim(res) FI;
\r
378 (*------------------------------------------------------------------*)
\r
379 (* PROCEDURE li
\82es la gestion du MENU de la Gestion de la Semaine *)
\r
380 (*------------------------------------------------------------------*)
\r
382 UNIT menu_ps : PROCEDURE;
\r
386 WRITELN(" ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ");
\r
387 WRITELN(" ³ PLANNING DE LA SEMAINE AVEC CONTRAINTES ³ ");
\r
388 WRITELN(" ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ");
\r
389 WRITELN(" Chaque jour implique un choix particulier :");
\r
391 WRITELN(" * LUNDI :");
\r
393 WRITE(" $",L1(1,i):2," Exercice ",L1(2,i):2);
\r
394 IF i > M THEN WRITELN;
\r
395 ELSE WRITELN(" $",L2(1,i):2," Plaisir ",L2(2,i));
\r
399 WRITELN(" * MARDI MERCREDI JEUDI :");
\r
401 WRITELN(" Etude ",MA(i):2," ",ME(i):2," ",JE(i));
\r
404 WRITELN(" * VENDREDI :");
\r
406 WRITE(" $",V1(1,i):2," Exercice ",V1(2,i):2);
\r
407 IF i > M THEN WRITELN;
\r
408 ELSE WRITELN(" $",V2(1,i):2," Plaisir ",V2(2,i));
\r
412 WRITE(" CONTRAINTES : ");
\r
413 WRITE(" Exercice >= ",exercice:2," Argent ($) =< ",argent:2);
\r
414 WRITELN(" Etude >= ",etude:2," Plaisir >= ",plaisir:2);
\r
420 (*---------------------------------------------------------------------*)
\r
421 (* PROCEDURES li
\82es la gestion de l'AFFICHAGE
\85 l'
\82cran des resultats *)
\r
422 (*---------------------------------------------------------------------*)
\r
425 UNIT imprim : PROCEDURE(res : ARRAYOF integer);
\r
426 (* La proc
\82dure imprim permet d'afficher toutes les solutions *)
\r
427 (* possibles (les unes a la suite des autres) pages par pages
\85 *)
\r
428 (* l'
\82cran, sous forme de tableau de resultat. *)
\r
433 IF cpt = 0 THEN CALL eff;
\r
434 (* affichage de l'entete
\85 l'
\82cran *)
\r
437 WRITE ("³",res(1):4,"³",res(2):4,"³",res(3):4);
\r
438 WRITE ("³",res(4):6," ³",res(5):6," ³",res(6):6);
\r
439 WRITE (" ³",res(7):4,"³",res(8):4,"³",res(9):4);
\r
440 WRITE ("º",ex:4,"³",pl:4,"³",arg:4,"³",et:4,"³");
\r
443 IF cpt = 16 THEN WRITELN ("Appuyez sur une touche pour continuer...");
\r
451 UNIT entete : PROCEDURE;
\r
452 (* Affiche l'entete du tableau de resultat
\85 l'
\82cran. *)
\r
454 WRITELN("CONTRAINTES : ");
\r
455 WRITE("Exercice >= ",exercice:2," Argent ($) =< ",argent:2);
\r
456 WRITELN(" Etude >= ",etude:2," Plaisir >= ",plaisir:2);
\r
457 WRITE("ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÂÄÄÄÄÄÄÄÄÂÄÄÄÄÄ");
\r
458 WRITELN("ÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄËÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿");
\r
459 WRITE("³ LUNDI ³ MARDI ³MERCREDI³ JEUD");
\r
460 WRITELN("I ³ VENDREDI º TOTAL ³");
\r
461 WRITE("ÃÄÄÄÄÂÄÄÄÄÂÄÄÄÄÅÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÅÄÄÄÄÄ");
\r
462 WRITELN("ÄÄÄÅÄÄÄÄÂÄÄÄÄÂÄÄÄÄÎÄÄÄÄÂÄÄÄÄÂÄÄÄÄÂÄÄÄÄ´");
\r
463 WRITE("³Exer³Plai³ $ ³ Etude ³ Etude ³ Etud");
\r
464 WRITELN("e ³Exer³Plai³ $ ºExer³Plai³ $ ³Etud³");
\r
465 WRITE("ÃÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÅÄÄÄÄÄ");
\r
466 WRITELN("ÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÅÄÄÄÄ´");
\r
470 UNIT fin : PROCEDURE;
\r
471 (* Affiche la fin du tableau de resultat
\85 l'
\82cran. *)
\r
474 WRITE("ÀÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÄÄÄÄÁÄÄÄÄÄÄÄÄÁÄÄÄÄÄ");
\r
475 WRITELN("ÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÁÄÄÄÄÙ");
\r
476 WRITELN ("Appuyez sur une touche pour continuer...");
\r
482 PREF IIUWGraph block;
\r
484 (* Initialisation des tableaux et des variables de JEUX D'ESSAI *)
\r
489 (* D
\82claration d'intervalles *)
\r
493 ARRAY res DIM (1:9);
\r
494 ARRAY L1 DIM (1:N2);
\r
497 ARRAY L1(i) DIM (1:N);
\r
499 ARRAY L2 DIM (1:N2);
\r
502 ARRAY L2(i) DIM (1:M);
\r
504 ARRAY MA DIM (1:N);
\r
505 ARRAY ME DIM (1:N);
\r
506 ARRAY JE DIM (1:N);
\r
507 ARRAY V1 DIM (1:N2);
\r
510 ARRAY V1(i) DIM (1:N);
\r
512 ARRAY V2 DIM (1:N2);
\r
515 ARRAY V2(i) DIM (1:M);
\r
518 (* Initialisation des tableaux jeux d'essai du mardi,mercredi et
\r
519 jeudi concernant les
\82tudes. *)
\r
523 MA(i),ME(i),JE(i) := (i-1) * interv;
\r
526 (* Initialisation des tableaux jeux d'essai du lundi et vendredi
\r
527 concernant l'argent. *)
\r
529 L1(1,1),V1(1,1) := 0;
\r
530 L1(1,2),V1(1,2) := 0;
\r
531 L1(1,3),V1(1,3) := 0;
\r
532 L1(1,4),V1(1,4) := 20;
\r
534 (* Initialisation des tableaux jeux d'essai du lundi et vendredi
\r
535 concernant les exercices. *)
\r
539 L1(2,i),V1(2,i) := (i-1) * interv2;
\r
542 (* Initialisation des tableaux jeux d'essai du lundi et vendredi
\r
543 concernant les plaisirs ou divertissements. *)
\r
545 L2(1,1),V2(1,1) := 0;
\r
546 L2(1,2),V2(1,2) := 0;
\r
547 L2(1,3),V2(1,3) := 20;
\r
551 L2(2,i),V2(2,i) := (i-1) * interv3;
\r
554 (* Les contraintes d'une semaine
\82quilibr
\82e sont les suivantes : *)
\r
564 CALL recurs(1,res);
\r
572 (***************************************************************************)
\r
573 (* LA PARTIE GESTION DU JEU DES PIONS NOIRS ET BLANCS *)
\r
575 (* il s'agit ici de la DECLARATION de l'objet PION *)
\r
576 (* (utilise la biblioth
\8aque Graphique IIugraph) *)
\r
577 (***************************************************************************)
\r
580 UNIT PION : IIuwgraph CLASS;
\r
582 VAR n,i,M : integer,
\r
583 tab : ARRAYOF char,
\r
584 trouve,manuel: boolean;
\r
587 UNIT procent : PROCEDURE(A,B : char, P,NN : integer);
\r
588 (* La procedure procent permet de parcourir l'arbre des solutions *)
\r
589 (* en anticipant le meilleur des chemins c'est a dire en parcourant*)
\r
590 (* le moins de chemin possible. *)
\r
591 (* Les param
\8atres d'entr
\82s A et B prennent soit la valeur Noir et *)
\r
592 (* Blanc ou Blanc et Noir. Idem pour les 2 entier P et NN qui *)
\r
593 (* prennent en fonction de la couleur des pions soit la valeur 1 et*)
\r
594 (* M (2*n+1) ou -1 et 1. (P indique le sens de deplacement). *)
\r
599 UNIT proc : PROCEDURE(X : char);
\r
600 (* La proc
\82dure proc permet de connaitre si l'on se trouve dans *)
\r
601 (* position de blocage ou bien si l'on peut continuer dans ce *)
\r
602 (* chemin. (Cas o
\97 l'on place un pion
\85 cot
\82 d'un autre pion de *)
\r
603 (* m
\88me couleur). *)
\r
609 IF (j >= 1) AND (j <= M) THEN
\r
610 WHILE ((bo) AND (j <> NN+P))
\r
612 (* On test si tous les pions suivants sont
\r
613 de m
\88me couleur. Si oui alors on poursuit
\r
614 le chemin dans l'arbre, sinon on se trouve
\r
617 IF tab(j) <> X THEN bo := FALSE;
\r
626 UNIT affect2 : PROCEDURE;
\r
627 (* La proc
\82dure affect2 permet de d
\82placer un pion en sautant *)
\r
628 (* par dessus un pion de couleur adverse. *)
\r
629 (* Le sens du d
\82placement
\82tant indiquer par l'entier P. *)
\r
632 tab(i) := tab(i-2*P);
\r
635 (* appel de la proc
\82dure principale tentative *)
\r
638 tab(i-2*P) := tab(i);
\r
644 UNIT affect1 : PROCEDURE;
\r
645 (* La procedure affect1 permet de d
\82placer un pion d'une *)
\r
646 (* case en avant (pion avance dans la case vide). *)
\r
647 (* Le sens du d
\82placement
\82tant indiquer par l'entier P. *)
\r
650 tab(i) := tab(i-P);
\r
653 (* appel de la proc
\82dure principale tentative *)
\r
656 tab(i-P) := tab(i);
\r
663 (* On test si l'on se trouve en bordures du jeux (du tableau)
\r
664 C'est a dire que l'on verifie que les indices de tables
\r
665 sont toujours valide pour continuer les tests suivants. *)
\r
666 IF ((i-P) > 0) AND ((i-P) <= M) THEN
\r
668 (* On test si l'on peut avancer le pion dans la case vide en
\r
669 fonction de P (indique le sens du d
\82placement). *)
\r
670 IF tab(i-P) = A THEN
\r
672 (* On test si l'on se trouve en bordures du jeux, en
\r
673 fonction du sens du d
\82pacement. *)
\r
674 IF ((i+P) > 0) AND ((i+P) <= M) THEN
\r
676 (* On test si le pion situ
\82 apr
\8as la case vide est de
\r
677 m
\88me couleur que celui plac
\82 avant. *)
\r
678 IF tab(i+P) = A THEN
\r
679 (* Si oui on appele la proc
\82dure proc *)
\r
681 (* On test si l'on poursuit le chemin *)
\r
684 (* On test si l'on se trouve dans
\r
685 l'
\82tat final du jeux. (k=n) *)
\r
686 IF k = n THEN trouve := FALSE FI;
\r
687 IF trouve THEN CALL aff_retour_ar FI;
\r
690 (* Sinon on appele la proc
\82dure d'affectation
\r
691 affect1, et on poursuit le chemin. *)
\r
693 IF trouve THEN CALL aff_retour_ar FI;
\r
696 (* Sinon on appele la proc
\82dure d'affectation affect1 *)
\r
698 IF trouve THEN CALL aff_retour_ar FI;
\r
702 (* On test si l'on se trouve en bordures du jeux (du tableau)
\r
703 C'est a dire que l'on verifie que les indices de tables
\r
704 sont toujours valide pour continuer les tests suivants. *)
\r
705 IF ((i-2*P) > 0) AND ((i-2*P) <= M) THEN
\r
707 (* On test si l'on peut avancer le pion plac
\82 2 cases
\r
708 avant la case vide en sautant un pion de couleur
\r
709 adverse plac
\82 une case avant la case vide, toujours
\r
710 en fonction du sens P. *)
\r
711 IF (tab(i-2*P) = A) AND (tab(i-P) = B) THEN
\r
713 (* On test si l'on se trouve en bordures du jeux, en
\r
714 fonction du sens du d
\82pacement. *)
\r
715 IF ((i+P) > 0) AND ((i+P) <= M) THEN
\r
717 (* On test si le pion situ
\82 apr
\8as la case vide
\r
718 est de m
\88me couleur que celui plac
\82 2 cases
\r
719 avant la case vide. *)
\r
720 IF tab(i+P) = A THEN
\r
721 (* Si oui on appele la proc
\82dure proc *)
\r
723 (* On test si l'on poursuit le chemin *)
\r
726 (* On test si l'on se trouve dans
\r
727 l'
\82tat final du jeux. (k=n) *)
\r
728 IF k = n THEN trouve := FALSE; FI;
\r
729 IF trouve THEN CALL aff_retour_ar FI;
\r
732 (* Sinon appel de la proc
\82dure d'affectation
\r
733 affect2, et on poursuit le chemin. *)
\r
735 IF trouve THEN CALL aff_retour_ar FI;
\r
738 (* appel de la proc
\82dure d'affectation affect2 *)
\r
740 IF trouve THEN CALL aff_retour_ar FI;
\r
751 UNIT tentative : PROCEDURE;
\r
752 (* Cette proc
\82dure permet de parcourir l'arbre du jeux des pions. *)
\r
753 (* En faisant d'abord avancer les pions Noirs puis les pions Blancs*)
\r
754 (* Tant que l'
\82tat final n'est pas atteint on affiche l'
\82volution *)
\r
755 (* du d
\82placement dans l'arbre. *)
\r
760 (* On imprime le resultat a l'instant t *)
\r
762 (* On d
\82place les pions Noirs *)
\r
763 CALL procent('N','B',1,M);
\r
764 (* On d
\82place les pions Blancs *)
\r
765 CALL procent('B','N',-1,1);
\r
772 (*---------------------------------------------------------------------*)
\r
773 (* PROCEDURES li
\82es la gestion de l'AFFICHAGE
\85 l'
\82cran des resultats *)
\r
774 (*---------------------------------------------------------------------*)
\r
777 UNIT aff_retour_ar : PROCEDURE;
\r
778 (* Proc
\82dure permettant d'indiquer
\85 l'
\82cran que l'on effectue *)
\r
779 (* un retour arri
\8are (BACKTRACKING). *)
\r
783 CALL move(150,220); CALL draw(360,220);
\r
784 CALL move(150,260); CALL draw(360,260);
\r
785 CALL move(150,220); CALL draw(150,260);
\r
786 CALL move(360,220); CALL draw(360,260);
\r
787 CALL move(180,237);
\r
788 CALL outstring("RETOUR ARRIERE ...");
\r
795 UNIT imprim : PROCEDURE;
\r
796 (* Proc
\82dure permettant d'afficher de mani
\8are graphique les *)
\r
797 (* pions Noirs et Blancs dans un tableaux proportionnel au *)
\r
798 (* nombre de pions. *)
\r
799 (* Les proc
\82dures graphiques utilis
\82es : outstring, move, draw *)
\r
802 VAR l,col,xi,touche : integer;
\r
806 CALL outstring("LE PROBLEME DES PIONS NOIRS ET BLANCS");
\r
808 (* Affichage du tableau de jeux *)
\r
809 CALL move(70,80); CALL draw(70+60*(2*n+1),80);
\r
810 CALL move(70,120); CALL draw(70+60*(2*n+1),120);
\r
811 FOR l := 0 TO ((n+1)*2-1) DO
\r
812 CALL move(70+(60*l),80); CALL draw(70+(60*l),120);
\r
815 (* Affichage des pions Noirs et Blancs *)
\r
818 xi := 100 + ((l-1) * 60);
\r
820 THEN IF tab(l) = 'B' THEN col := 15;
\r
823 CALL cirb(xi,100,20,10,10,15,col,2,2);
\r
828 CALL outstring("Appuyez sur une touche pour continuer...");
\r
830 ELSE CALL attendre(2);
\r
835 UNIT menu_p : PROCEDURE;
\r
836 VAR choix : integer;
\r
841 WRITELN(" ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ");
\r
842 WRITELN(" ³ PROBLEME DES PIONS NOIRS ET BLANCS ³ ");
\r
843 WRITELN(" ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ");
\r
845 WRITELN (" A partir d'un etat initial qui est le suivant :");
\r
846 WRITELN (" NNN*BBB");
\r
847 WRITELN (" Il faut aboutir
\85 un etat final qui est le suivant :");
\r
848 WRITELN (" BBB*NNN");
\r
850 WRITELN (" Sachant que l'on
\85 des r
\8agles fix
\82es :");
\r
851 WRITELN (" ÄÄ> <ÄÄ");
\r
852 WRITELN (" - Les sens sont fix
\82s : NNN*BBB");
\r
853 WRITELN (" - Un pion peut avancer dans une case vide '*' si :");
\r
854 WRITELN (" * Elle est juste devant. ");
\r
855 WRITELN (" * Il l'atteint en sautant par dessus un pion");
\r
856 WRITELN (" de couleur adverse.");
\r
858 WRITELN (" D
\82sirez vous un traitement :");
\r
860 WRITELN (" 1 ......... MANUEL");
\r
861 WRITELN (" 2 ......... AUTOMATIQUE");
\r
863 WRITE (" Votre choix : ");
\r
865 IF choix = 2 THEN manuel := FALSE FI;
\r
867 WRITELN; WRITELN; WRITELN; WRITELN;
\r
869 WHILE ((n < 2) OR (n > 4))
\r
871 WRITE(" Donnez le Nombre de Pions (2,3 ou 4) : ");
\r
879 (* On utilise pour repr
\82senter de fa
\87on graphique
\85 l'
\82cran les pions *)
\r
880 (* Noirs et Blancs la Biblioth
\82que graphique IIugraph. *)
\r
882 PREF IIUWGraph block;
\r
887 (* initialisation
\85 l'
\82tat initial du tableau de jeux en fonction *)
\r
888 (* du nombres de pions entr
\82s pr
\82alablement. ex: NNN BBB *)
\r
890 ARRAY tab DIM (1:(n*2)+1);
\r
892 FOR i := 1 TO n DO tab(i) := 'N' OD;
\r
894 FOR i := (n+2) TO (n*2)+1 DO tab(i) := 'B' OD;
\r
898 (* La variable M repr
\82sente l'indice maximum du tableau du jeux *)
\r
899 (* en fonction du nombres de pions. ex: si n=3 ÄÄ> M=7 *)
\r
903 (* Appel de la proc
\82dure principale 'tentative' de parcours
\r
912 (*******************************)
\r
913 (*** PROGRAMME PRICIPAL *****)
\r
914 (*******************************)
\r
917 (* Appel du menu principal *)
\r