1 PROGRAM BACKTRACKING;
\r
2 UNIT BACKTRACK: CLASS;
\r
4 VAR ROOT:NODE,SEARCH:SE,FOUND,OPT:NODE,
\r
5 NUMBER_OF_NODES,NUMBER_OF_LEAVES,NUMBER_OF_ANSWERS:INTEGER;
\r
7 UNIT NODE: COROUTINE(FATHER:NODE);
\r
8 VAR NSONS,LEVEL: INTEGER , DEADEND:BOOLEAN;
\r
9 UNIT VIRTUAL LEAF: FUNCTION :BOOLEAN;
\r
11 UNIT VIRTUAL ANSWER :FUNCTION :BOOLEAN;
\r
13 UNIT VIRTUAL LASTSON: FUNCTION : BOOLEAN;
\r
15 UNIT VIRTUAL NEXTSON: FUNCTION : NODE;
\r
17 UNIT VIRTUAL EQUAL : FUNCTION (W:NODE):BOOLEAN;
\r
19 UNIT VIRTUAL COST: FUNCTION :REAL;
\r
24 LEVEL:=FATHER.LEVEL+1
\r
30 UNIT OK: FUNCTION (V:NODE):BOOLEAN;
\r
33 IF V=NONE THEN RESULT:=FALSE; RETURN FI;
\r
34 RESULT:=TRUE; W:=V.FATHER;
\r
37 IF V.EQUAL(W) THEN RESULT:=FALSE; RETURN FI;
\r
42 UNIT PURGE: PROCEDURE (V:NODE);
\r
45 IF V=NONE THEN RETURN FI;
\r
47 W:=V.FATHER; KILL(V);
\r
48 IF W=NONE THEN RETURN FI;
\r
50 IF W.NSONS =/= 0 THEN RETURN FI;
\r
57 UNIT ELEM: CLASS (NEXT:ELEM, V:NODE);
\r
60 UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);
\r
62 TOP:=NEW ELEM(TOP,V);
\r
65 UNIT VIRTUAL DELETE: FUNCTION :NODE;
\r
71 E:=TOP; TOP:=TOP.NEXT; KILL(E);
\r
75 UNIT SE: COROUTINE ;
\r
76 VAR I:INTEGER,V,W:NODE;
\r
78 RETURN; CALL INSERT(ROOT);
\r
81 IF V=NONE THEN EXIT FI;
\r
85 NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;
\r
87 IF OPT=NONE ORIF V.COST < OPT.COST
\r
92 (* HERE THE USER OF BACKTRACK MAY UNDERTAKE SOME ACTIONS
\r
93 ON THE ANSWER NODES. IF NOT NECESSARY DO ATTACH *)
\r
97 NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;
\r
101 W:=V.NEXTSON; V.NSONS:=V.NSONS+1;
\r
102 NUMBER_OF_NODES:=NUMBER_OF_NODES+1;
\r
105 W.DEADEND:=W.LEAF; CALL INSERT(W);
\r
107 IF V.LASTSON THEN EXIT FI;
\r
116 UNIT KILLALL :PROCEDURE;
\r
121 IF V=NONE THEN RETURN FI;
\r
129 KILL(SEARCH); CALL KILLALL;
\r
133 UNIT BESTSEARCH: BACKTRACK CLASS;
\r
134 (* BESTSEARCH USES A PRIORITY QUEUE FOR NODES.
\r
135 QUEUE IS ORGANIZED AS A HEAP IN THE ARRAY A.
\r
136 THE FIRST ELEMENT A(1) IS THE LEAST ONE. *)
\r
137 HIDDEN A,B,X,K,M,I,J;
\r
138 VAR A,B:ARRAYOF EX_NODE, X : EX_NODE, K,M,I,J:INTEGER;
\r
139 (*M- CURRENT ARRAY A LENTGTH
\r
140 K- CURRENT HEAP LENGTH
\r
143 UNIT EX_NODE : NODE CLASS;
\r
144 UNIT VIRTUAL LESS : FUNCTION (X: EX_NODE) : BOOLEAN;
\r
148 UNIT VIRTUAL DELETE: FUNCTION :EX_NODE;
\r
151 IF K=0 THEN RETURN FI;
\r
152 RESULT:=A(1); X:=A(K); K:=K-1;
\r
159 ARRAY B DIM (1: M DIV 2);
\r
160 FOR I:=1 TO K DO B(I):=A(I) OD;
\r
161 KILL(A); M:=M DIV 2; A:=B
\r
166 IF J+1 <= K ANDIF A(J+1).LESS( A(J))
\r
170 IF X.LESS( A(J)) THEN EXIT FI;
\r
171 A(I):=A(J); I:=J; J:=2*I
\r
177 UNIT VIRTUAL INSERT : PROCEDURE(X: EX_NODE);
\r
181 ARRAY A DIM (1:2); M:=2;
\r
185 ARRAY B DIM(1:2*M); FOR I:=1 TO M DO B(I):=A(I) OD;
\r
186 KILL(A); M:=2*M; A:=B;
\r
189 IF K=1 THEN A(1):=X; RETURN; FI;
\r
193 IF A(I).LESS( X ) THEN EXIT FI;
\r
194 A(J):=A(I); J:=I; I:= J DIV 2
\r
206 VAR N,Q:INTEGER,H1,H2,H3:CHAR;
\r
207 (* Q - BOAT CAPACITY, N- NUMBER OF CANNIBALS, N- NUMBER OF MISSIONARIES *)
\r
211 WRITE(" NUMBER OF PERSONS ");
\r
212 WRITE(" (IF END OF SESSION WRITE 0) =");
\r
214 IF N=0 THEN EXIT FI;
\r
215 WRITE(" BOAT CAPACITY=");
\r
218 PREF BESTSEARCH BLOCK
\r
220 (* M- NUMBER OF MISSIONARIES, C- NUMBER OF CANNIBALS ON THE BOAT *)
\r
222 UNIT STATE: EX_NODE CLASS(ML,CL:INTEGER);
\r
223 VAR MR,CR:INTEGER, LEFT:BOOLEAN;
\r
225 (* ML- NUMBER OF MISSIONARIES ON THE LEFT BANK OF THE RIVER
\r
226 MR- NUMBER OF MISSIONARIES ON THE RIGHT BANK OF THE RIVER
\r
227 CL- NUMBER OF CANNIBALS ON THE LEFT BANK OF THE RIVER
\r
228 CR- NUMBER OF CANNIBALS ON THE RIGHT BANK OF THE RIVER
\r
229 LEFT- TRUE IFF THE BOAT IS ON THE LEFT BANK OF THE RIVER *)
\r
231 UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;
\r
233 RESULT:=ML=0 AND CL=0
\r
236 UNIT VIRTUAL LEAF: FUNCTION : BOOLEAN;
\r
238 IF ML<0 ORIF MR<0 ORIF CL<0 ORIF CR<0 ORIF
\r
239 ML>N ORIF MR>N ORIF CL>N ORIF CR>N ORIF
\r
240 ML<CL AND ML>0 ORIF MR<CR AND MR>0
\r
247 UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;
\r
251 RESULT:=TRUE; M:=0; C:=0;
\r
255 UNIT VIRTUAL NEXTSON : FUNCTION :STATE;
\r
276 RESULT:=NEW STATE(THIS STATE,ML-M,CL-C)
\r
279 RESULT:=NEW STATE(THIS STATE,ML+M,CL+C)
\r
283 UNIT VIRTUAL EQUAL: FUNCTION(S:STATE):BOOLEAN;
\r
285 RESULT:=LEFT=S.LEFT AND ML=S.ML AND CL=S.CL;
\r
288 UNIT VIRTUAL COST: FUNCTION :REAL;
\r
293 UNIT VIRTUAL LESS: FUNCTION (S:STATE): BOOLEAN;
\r
295 RESULT:=ML+CL<S.ML+S.CL
\r
301 LEFT:=LEVEL MOD 2 = 0;
\r
302 MR:=N-ML; CR:=N-CL;
\r
305 IF BOOL1 THEN CALL DISPLAY(THIS STATE) FI;
\r
311 UNIT DISPLAY: PROCEDURE(V:STATE);
\r
312 VAR J,I:INTEGER, W:STATE,AT: ARRAYOF STATE;
\r
314 IF V=NONE THEN WRITELN(" NO MORE SOLUTIONS"); RETURN FI;
\r
316 ARRAY AT DIM (0:I);
\r
320 AT(J):=W; W:=W.FATHER
\r
322 WRITELN("MOVE NUMBER LEFT SIDE DIRECTION RIGHT SIDE");
\r
325 WRITE(J); WRITE(" ");
\r
327 WRITE(W.ML,W.CL," ");
\r
334 WRITELN(" ",W.MR,W.CR);
\r
342 ROOT:=NEW STATE(NONE,N,N);
\r
343 WRITE("DO YOU WANT TO OPTIMIZE ");
\r
344 WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");
\r
345 WRITELN(" (ANSWER OPT OR ALL)");
\r
347 IF H1='O' AND H2='P' AND H3='T'
\r
351 IF FOUND=NONE THEN EXIT FI;
\r
352 IF OPT =/= NONE ANDIF OPT.COST<FOUND.COST
\r
360 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
361 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
362 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
364 WRITELN("NO SOLUTIONS");
\r
365 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
366 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
369 IF H1='A' AND H2='L' AND H3='L'
\r
371 WRITELN("DO YOU WANT TO PRINT PARTIAL RESULTS?");
\r
373 IF H1='Y' AND H2='E' AND H3='S'
\r
379 CALL DISPLAY(FOUND);
\r
380 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
381 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
382 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
383 IF FOUND=NONE THEN EXIT FI;
\r
384 WRITELN("DO YOU WANT TO CONTINUE?");
\r
386 IF H1=/='Y' ORIF H2=/='E' THEN EXIT FI;
\r
388 IF H3=/='S' THEN EXIT FI;
\r