1 PROGRAM BACKTRACKING;
\r
2 UNIT BACKTRACK: CLASS;
\r
4 VAR ROOT:NODE,SEARCH:SE,FOUND:NODE,
\r
5 NUMBER_OF_LEAVES,NUMBER_OF_ANSWERS:INTEGER;
\r
7 UNIT NODE: CLASS(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
55 UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);
\r
58 UNIT VIRTUAL DELETE : FUNCTION :NODE;
\r
61 UNIT SE: COROUTINE ;
\r
62 VAR I:INTEGER,V,W:NODE;
\r
64 RETURN; CALL INSERT(ROOT);
\r
67 IF V=NONE THEN EXIT FI;
\r
70 NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;
\r
71 FOUND:=V; DETACH; CALL PURGE(V);
\r
75 NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;
\r
79 W:=V.NEXTSON; V.NSONS:=V.NSONS+1;
\r
82 W.DEADEND:=W.LEAF; CALL INSERT(W);
\r
84 IF V.LASTSON THEN EXIT FI;
\r
92 UNIT OPTIMIZE: FUNCTION: NODE;
\r
98 IF V=NONE THEN EXIT FI;
\r
101 NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;
\r
102 IF RESULT=NONE ORIF RESULT.COST > V.COST
\r
104 CALL PURGE(RESULT); RESULT:=V
\r
109 NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;
\r
113 W:=V.NEXTSON; V.NSONS:=V.NSONS+1;
\r
116 W.DEADEND:=W.LEAF; CALL INSERT(W);
\r
118 IF V.LASTSON THEN EXIT FI;
\r
126 UNIT KILLALL :PROCEDURE;
\r
131 IF V=NONE THEN RETURN FI;
\r
142 UNIT DFS :BACKTRACK CLASS;
\r
145 UNIT ELEM: CLASS (NEXT:ELEM, V:NODE);
\r
148 UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);
\r
150 TOP:=NEW ELEM(TOP,V);
\r
153 UNIT VIRTUAL DELETE: FUNCTION :NODE;
\r
159 E:=TOP; TOP:=TOP.NEXT; KILL(E);
\r
165 VAR N,BC:INTEGER,H1,H2,H3:CHAR;
\r
170 IF N=0 THEN EXIT FI;
\r
171 WRITE(" BOAT CAPACITY=");
\r
175 VAR M,C:INTEGER; (* BC - BOAT CAPACITY, N- NUMBER OF CANNIBALS
\r
176 N- NUMBER OF MISSIONARS *)
\r
177 UNIT STATE: NODE CLASS(M1,C1:INTEGER);
\r
178 VAR M2,C2:INTEGER, LEFT:BOOLEAN;
\r
179 (* M1,M2 NUMBER OF MISSIONARS ON BOTH SIDES OF THE RIVER
\r
180 C1,C2 NUMBER OF CANNIBALS ON BOTH SIDES OF THE RIVER *)
\r
182 UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;
\r
184 RESULT:=M1=0 AND C1=0
\r
187 UNIT VIRTUAL LEAF: FUNCTION : BOOLEAN;
\r
189 IF M1<0 ORIF M2<0 ORIF C1<0 ORIF C2<0 ORIF
\r
190 M1>N ORIF M2>N ORIF C1>N ORIF C2>N ORIF
\r
191 M1<C1 AND M1>0 ORIF M2<C2 AND M2>0
\r
198 UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;
\r
202 RESULT:=TRUE; M:=0; C:=0;
\r
206 UNIT VIRTUAL NEXTSON : FUNCTION :STATE;
\r
227 RESULT:=NEW STATE(THIS STATE,M1-M,C1-C)
\r
230 RESULT:=NEW STATE(THIS STATE,M1+M,C1+C)
\r
234 UNIT VIRTUAL EQUAL: FUNCTION(W:STATE):BOOLEAN;
\r
236 RESULT:=LEFT=W.LEFT AND M1=W.M1 AND C1=W.C1;
\r
239 UNIT VIRTUAL COST: FUNCTION :REAL;
\r
246 LEFT:=LEVEL MOD 2 = 0;
\r
247 M2:=N-M1; C2:=N-C1;
\r
251 UNIT DISPLAY: PROCEDURE(V:STATE);
\r
252 VAR J,I:INTEGER, W:STATE,AT: ARRAYOF STATE;
\r
254 IF V=NONE THEN WRITELN(" NO MORE SOLUTIONS"); RETURN FI;
\r
256 ARRAY AT DIM (0:I);
\r
260 AT(J):=W; W:=W.FATHER
\r
262 WRITELN("MOVE NUMBER LEFT SIDE DIRECTION RIGHT SIDE");
\r
265 WRITE(J); WRITE(" ");
\r
267 WRITE(W.M1,W.C1," ");
\r
274 WRITELN(" ",W.M2,W.C2);
\r
280 ROOT:=NEW STATE(NONE,N,N);
\r
281 WRITE("DO YOU WANT TO OPTIMIZE ");
\r
282 WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");
\r
283 WRITELN(" (ANSWER OPT OR ALL)");
\r
285 IF H1='O' AND H2='P' AND H3='T'
\r
290 CALL DISPLAY(FOUND);
\r
291 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
292 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
294 WRITELN(" NO SOLUTIONS");
\r
295 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
299 IF H1='A' AND H2='L' AND H3='L'
\r
303 CALL DISPLAY(FOUND);
\r
304 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
305 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
306 IF FOUND=NONE THEN EXIT FI
\r