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 VAR N,M,I,J:INTEGER,H1,H2,H3:CHAR;
\r
134 VAR INC: ARRAYOF ARRAYOF BOOLEAN;
\r
137 WRITE(" NUMBER OF VERTICES= ");
\r
139 IF N=0 THEN EXIT FI;
\r
140 WRITE(" NUMBER OF COLOURS= ");
\r
142 ARRAY INC DIM (1:N);
\r
143 FOR I:=1 TO N DO ARRAY INC(I) DIM (1:I); OD;
\r
144 WRITELN(" GIVE A GRAPH BY DEFINING SUCCESSIVE EDGES");
\r
145 WRITELN(" TO END A LIST WRITE 0");
\r
148 WRITELN(" VERTEX ",I:3," IS INCIDENT WITH VERTICES=");
\r
151 IF J>1 AND J<=N THEN INC(J,I):=TRUE ELSE EXIT FI;
\r
153 WRITELN(" END OF EDGES WITH VERTEX", I:3)
\r
155 WRITELN(" GRAPH HAS THE FOLLOWING INCIDENCE MATRIX");
\r
160 IF INC(I,J) THEN WRITE(1:2) ELSE WRITE(0:2) FI;
\r
164 PREF BACKTRACK BLOCK
\r
166 UNIT STATE: NODE CLASS(I,J,NC:INTEGER);
\r
168 (*I- VERTEX, J-COLOUR, NC-NUMBER OF COLOURS *)
\r
170 UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;
\r
172 RESULT:= I=N AND OKGO(THIS STATE)
\r
175 UNIT VIRTUAL LEAF: FUNCTION :BOOLEAN;
\r
177 RESULT:=I=N OR NOT OKGO(THIS STATE)
\r
180 UNIT OKGO: FUNCTION(V:STATE) : BOOLEAN;
\r
186 IF V=NONE THEN RESULT:=TRUE; EXIT FI;
\r
187 IF V.J=J AND INC(I,V.I) THEN EXIT FI;
\r
192 UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;
\r
201 UNIT VIRTUAL NEXTSON : FUNCTION :STATE;
\r
202 VAR V:STATE,NCK:INTEGER;
\r
208 IF V=NONE THEN NCK:=NCK+1; EXIT FI;
\r
209 IF V.J=K THEN EXIT FI;
\r
212 RESULT:=NEW STATE(THIS STATE,I+1,K,NCK);
\r
215 UNIT VIRTUAL EQUAL: FUNCTION(S:STATE):BOOLEAN;
\r
217 RESULT:=I=S.I AND J=S.J
\r
220 UNIT VIRTUAL COST: FUNCTION :REAL;
\r
234 UNIT DISPLAY: PROCEDURE(V:STATE);
\r
236 IF V=NONE THEN WRITELN(" NO SOLUTIONS"); RETURN FI;
\r
237 WRITELN("VERTEX COLOUR");
\r
239 WRITE(V.I); WRITE(" "); WRITELN(V.J);
\r
241 IF V=NONE THEN EXIT FI
\r
248 ROOT:=NEW STATE(NONE,1,1,1);
\r
249 WRITE("DO YOU WANT TO OPTIMIZE ");
\r
250 WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");
\r
251 WRITELN(" (ANSWER OPT OR ALL)");
\r
253 IF H1='O' AND H2='P' AND H3='T'
\r
257 IF FOUND=NONE THEN EXIT FI;
\r
258 IF OPT =/= NONE ANDIF OPT.COST<FOUND.COST
\r
266 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
267 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
268 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
270 WRITELN("NO SOLUTIONS");
\r
271 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
272 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
275 IF H1='A' AND H2='L' AND H3='L'
\r
279 CALL DISPLAY(FOUND);
\r
280 WRITELN("NUMBER OF NODES=",NUMBER_OF_NODES);
\r
281 WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
\r
282 WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
\r
283 IF FOUND=NONE THEN EXIT FI;
\r
284 WRITELN("DO YOU WANT TO CONTINUE?");
\r
286 IF H1=/='Y' ORIF H2=/='E' THEN EXIT FI;
\r
288 IF H3=/='S' THEN EXIT FI;
\r