3 UNIT BACKTRACK: CLASS;
\r
5 VAR ROOT:NODE,SEARCH:SE,FOUND,OPT:NODE,
\r
6 NUMBER_OF_NODES,NUMBER_OF_LEAVES,NUMBER_OF_ANSWERS:INTEGER;
\r
9 UNIT NODE: COROUTINE(FATHER:NODE);
\r
10 VAR NSONS,LEVEL, MY_NUMBER: INTEGER , DEADEND:BOOLEAN;
\r
11 UNIT VIRTUAL LEAF: FUNCTION :BOOLEAN;
\r
13 UNIT VIRTUAL ANSWER :FUNCTION :BOOLEAN;
\r
15 UNIT VIRTUAL LASTSON: FUNCTION : BOOLEAN;
\r
17 UNIT VIRTUAL NEXTSON: FUNCTION : NODE;
\r
19 UNIT VIRTUAL EQUAL : FUNCTION (W:NODE):BOOLEAN;
\r
21 UNIT VIRTUAL COST: FUNCTION :REAL;
\r
23 UNIT VIRTUAL Display: PROCEDURE;
\r
26 MY_NUMBER := NUMBER_OF_NODES;
\r
27 NUMBER_OF_NODES := NUMBER_OF_NODES+1;
\r
30 LEVEL:=FATHER.LEVEL+1
\r
34 call this NODE.DISPLAY;
\r
37 UNIT OK: FUNCTION (V:NODE):BOOLEAN;
\r
40 IF V=NONE THEN RESULT:=FALSE; RETURN FI;
\r
41 RESULT:=TRUE; W:=V.FATHER;
\r
44 IF V.EQUAL(W) THEN RESULT:=FALSE; RETURN FI;
\r
49 UNIT PURGE: PROCEDURE (V:NODE);
\r
52 IF V=NONE THEN RETURN FI;
\r
54 W:=V.FATHER; KILL(V);
\r
55 IF W=NONE THEN RETURN FI;
\r
57 IF W.NSONS =/= 0 THEN RETURN FI;
\r
64 UNIT ELEM: CLASS (NEXT:ELEM, V:NODE);
\r
67 UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);
\r
69 TOP:=NEW ELEM(TOP,V);
\r
72 UNIT VIRTUAL DELETE: FUNCTION :NODE;
\r
78 E:=TOP; TOP:=TOP.NEXT; KILL(E);
\r
82 UNIT SE: COROUTINE ;
\r
83 VAR I:INTEGER,V,W:NODE;
\r
85 RETURN; CALL INSERT(ROOT);
\r
88 IF V=NONE THEN EXIT FI;
\r
92 NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;
\r
94 IF OPT=NONE ORIF V.COST < OPT.COST
\r
99 (* HERE THE USER OF BACKTRACK MAY UNDERTAKE SOME ACTIONS
\r
100 ON THE ANSWER NODES. IF NOT NECESSARY DO ATTACH *)
\r
104 NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;
\r
108 W:=V.NEXTSON; V.NSONS:=V.NSONS+1;
\r
109 (* NUMBER_OF_NODES:=NUMBER_OF_NODES+1; *)
\r
112 W.DEADEND:=W.LEAF;
\r
115 IF V.LASTSON THEN EXIT FI;
\r
124 UNIT KILLALL :PROCEDURE;
\r
129 IF V=NONE THEN RETURN FI;
\r
137 KILL(SEARCH); CALL KILLALL;
\r
144 (* Q - BOAT CAPACITY, N- NUMBER OF CANNIBALS, N- NUMBER OF MISSIONARIES *)
\r
147 open(f,text,unpack("stsearch.his"));
\r
151 writeln("N Cannibals and N Missionars are to traverse a river in a boat");
\r
153 WRITE(" N= (tape 0 to stop program)");
\r
155 IF N=0 THEN EXIT FI;
\r
156 writeln("Cannibals & Missionars - program STSEARCH.LOG of 26.05.94 ");
\r
157 WRITELN(f," N= ",N);
\r
158 WRITE(" BOAT CAPACITY=");
\r
160 WRITELN(f,"Boat capacity=",Q);
\r
161 PREF BACKTRACK BLOCK
\r
163 (* M- NUMBER OF MISSIONARIES, C- NUMBER OF CANNIBALS ON THE BOAT *)
\r
165 UNIT STATE: NODE CLASS(ML,CL:INTEGER);
\r
166 VAR MR,CR:INTEGER, LEFT:BOOLEAN;
\r
168 (* ML- NUMBER OF MISSIONARIES ON THE LEFT BANK OF THE RIVER
\r
169 MR- NUMBER OF MISSIONARIES ON THE RIGHT BANK OF THE RIVER
\r
170 CL- NUMBER OF CANNIBALS ON THE LEFT BANK OF THE RIVER
\r
171 CR- NUMBER OF CANNIBALS ON THE RIGHT BANK OF THE RIVER
\r
172 LEFT- TRUE IFF THE BOAT IS ON THE LEFT BANK OF THE RIVER *)
\r
174 UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;
\r
176 RESULT:=ML=0 AND CL=0
\r
179 UNIT VIRTUAL LEAF: FUNCTION : BOOLEAN;
\r
181 IF ML<0 ORIF MR<0 ORIF CL<0 ORIF CR<0 ORIF
\r
182 ML>N ORIF MR>N ORIF CL>N ORIF CR>N ORIF
\r
183 ML<CL AND ML>0 ORIF MR<CR AND MR>0
\r
190 UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;
\r
194 RESULT:=TRUE; M:=0; C:=0;
\r
198 UNIT VIRTUAL NEXTSON : FUNCTION :STATE;
\r
219 RESULT:=NEW STATE(THIS STATE,ML-M,CL-C)
\r
222 RESULT:=NEW STATE(THIS STATE,ML+M,CL+C)
\r
226 UNIT VIRTUAL EQUAL: FUNCTION(S:STATE):BOOLEAN;
\r
228 RESULT:=LEFT=S.LEFT AND ML=S.ML AND CL=S.CL;
\r
231 UNIT VIRTUAL COST: FUNCTION :REAL;
\r
236 UNIT VIRTUAL DISPLAY: PROCEDURE;
\r
243 ARRAY AT DIM (0:I);
\r
247 AT(J):=W; W:=W.FATHER
\r
250 WRITE(f,"State no:",MY_NUMBER:4);
\r
251 if FATHER <> none then WRITE(f," son of state: ",FATHER.MY_NUMBER:4) fi;
\r
252 if ANSWER then WRITELN(f, " SOLUTION!")
\r
253 else if LEAF then WRITELN(f," DEADEND")
\r
254 else if not OK(V) then WRITELN(f," REDUNDANT STATE")
\r
260 WRITELN(f,"MOVE NUMBER LEFT SIDE DIRECTION RIGHT SIDE");
\r
263 WRITE(f,J); WRITE(f," ");
\r
265 WRITE(f,W.ML,W.CL," ");
\r
272 WRITELN(f," ",W.MR,W.CR);
\r
279 LEFT:=LEVEL MOD 2 = 0;
\r
280 MR:=N-ML; CR:=N-CL;
\r
288 UNIT DISPLAY: PROCEDURE(V:STATE);
\r
289 VAR J,I:INTEGER, W:STATE,AT: ARRAYOF STATE;
\r
291 IF V=NONE THEN WRITELN(" NO MORE SOLUTIONS"); RETURN FI;
\r
293 ARRAY AT DIM (0:I);
\r
297 AT(J):=W; W:=W.FATHER
\r
299 WRITELN("MOVE NUMBER LEFT SIDE DIRECTION RIGHT SIDE");
\r
302 WRITE(J); WRITE(" ");
\r
304 WRITE(W.ML,W.CL," ");
\r
311 WRITELN(" ",W.MR,W.CR);
\r
317 ROOT:=NEW STATE(NONE,N,N);
\r
318 WRITE("DO YOU WANT TO OPTIMIZE ");
\r
319 WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");
\r
320 WRITELN(" (ANSWER OPT OR ALL)");
\r
322 IF H1='O' AND H2='P' AND H3='T'
\r
326 IF FOUND=NONE THEN EXIT FI;
\r
327 (* IF OPT =/= NONE ANDIF OPT.COST<FOUND.COST
\r
335 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
336 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
337 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
339 WRITELN("NO SOLUTIONS");
\r
340 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
341 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
344 IF H1='A' AND H2='L' AND H3='L'
\r
348 CALL DISPLAY(FOUND);
\r
349 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
350 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
351 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
352 IF FOUND=NONE THEN EXIT FI;
\r
353 WRITELN("DO YOU WANT TO CONTINUE?");
\r
355 IF H1=/='Y' ORIF H2=/='E' THEN EXIT FI;
\r
357 IF H3=/='S' THEN EXIT FI;
\r
361 END; (* of prefixed block*)
\r
364 writeln("the tree is in the file STSEARCH.HIS");
\r
366 END; (* of program *)
\r