PROGRAM BACKTRACKING;
  UNIT BACKTRACK: CLASS;
    HIDDEN SE;
    VAR  ROOT:NODE,SEARCH:SE,FOUND:NODE,
	 NUMBER_OF_LEAVES,NUMBER_OF_ANSWERS:INTEGER;

    UNIT NODE: CLASS(FATHER:NODE);
      VAR NSONS,LEVEL: INTEGER , DEADEND:BOOLEAN;
      UNIT VIRTUAL LEAF:  FUNCTION :BOOLEAN;
      END LEAF;
      UNIT VIRTUAL ANSWER :FUNCTION :BOOLEAN;
      END ANSWER;
      UNIT VIRTUAL LASTSON: FUNCTION : BOOLEAN;
      END LASTSON;
      UNIT VIRTUAL NEXTSON: FUNCTION : NODE;
      END NEXTSON;
      UNIT VIRTUAL EQUAL : FUNCTION (W:NODE):BOOLEAN;
      END EQUAL;
      UNIT VIRTUAL COST: FUNCTION :REAL;
      END COST;
    BEGIN
      IF FATHER =/= NONE
      THEN
	LEVEL:=FATHER.LEVEL+1
      ELSE
	LEVEL:=0
      FI;
   END NODE;

    UNIT OK: FUNCTION (V:NODE):BOOLEAN;
      VAR W:NODE;
    BEGIN
      IF V=NONE THEN RESULT:=FALSE; RETURN FI;
      RESULT:=TRUE; W:=V.FATHER;
      WHILE W =/= NONE
      DO
	IF V.EQUAL(W) THEN RESULT:=FALSE; RETURN FI;
	W:=W.FATHER
      OD
    END OK;

    UNIT PURGE: PROCEDURE (V:NODE);
      VAR W: NODE;
    BEGIN
      IF V=NONE THEN RETURN FI;
      DO
	W:=V.FATHER; KILL(V);
	IF W=NONE THEN RETURN FI;
	W.NSONS:=W.NSONS-1;
	IF W.NSONS =/= 0 THEN RETURN FI;
	V:=W
      OD;
    END PURGE;

    UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);
    END INSERT;

    UNIT VIRTUAL DELETE : FUNCTION :NODE;
    END DELETE;

    UNIT SE: COROUTINE ;
      VAR I:INTEGER,V,W:NODE;
    BEGIN
      RETURN; CALL INSERT(ROOT);
      DO
	V:=DELETE;
	IF V=NONE THEN EXIT FI;
	IF V.ANSWER
	THEN
	  NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;
	  FOUND:=V; DETACH; CALL PURGE(V);
	ELSE
	  IF V.DEADEND
	  THEN
	    NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;
	    CALL PURGE(V);
	  ELSE
	    DO
	      W:=V.NEXTSON; V.NSONS:=V.NSONS+1;
	      IF OK(W)
	      THEN
		W.DEADEND:=W.LEAF; CALL INSERT(W);
	      FI;
	      IF V.LASTSON THEN EXIT FI;
	    OD;
	  FI;
	FI;
      OD;
      FOUND:=NONE;
    END SE;

    UNIT OPTIMIZE: FUNCTION: NODE;
      VAR V,W:NODE;
    BEGIN
      CALL INSERT(ROOT);
      DO
	V:=DELETE;
	IF V=NONE THEN EXIT FI;
	IF V.ANSWER
	THEN
	  NUMBER_OF_ANSWERS:=NUMBER_OF_ANSWERS+1;
	  IF RESULT=NONE ORIF  RESULT.COST > V.COST
	  THEN
	    CALL PURGE(RESULT);  RESULT:=V
	  FI;
	ELSE
	  IF V.DEADEND
	  THEN
	    NUMBER_OF_LEAVES:=NUMBER_OF_LEAVES+1;
	    CALL PURGE(V)
	  ELSE
	    DO
	      W:=V.NEXTSON; V.NSONS:=V.NSONS+1;
	      IF OK(W)
	      THEN
		W.DEADEND:=W.LEAF; CALL INSERT(W);
	      FI;
	      IF V.LASTSON THEN EXIT FI;
	    OD;
	  FI
	FI;
      OD;
    END OPTIMIZE;


    UNIT KILLALL :PROCEDURE;
      VAR V:NODE;
    BEGIN
      DO
	V:=DELETE;
	IF V=NONE THEN RETURN FI;
	CALL PURGE(V);
      OD;
    END KILLALL;

  BEGIN
    SEARCH:=NEW SE;
    INNER;
    KILL(SEARCH);
  END BACKTRACK;

  UNIT DFS :BACKTRACK CLASS;
    VAR TOP:ELEM;

    UNIT ELEM: CLASS (NEXT:ELEM, V:NODE);
    END ELEM;

    UNIT VIRTUAL INSERT: PROCEDURE(V:NODE);
    BEGIN
      TOP:=NEW ELEM(TOP,V);
    END INSERT;

    UNIT VIRTUAL DELETE: FUNCTION :NODE;
      VAR E:ELEM;
    BEGIN
      IF TOP =/= NONE
      THEN
	RESULT:=TOP.V;
	E:=TOP; TOP:=TOP.NEXT; KILL(E);
      FI;
    END DELETE;

  END DFS;

  VAR N,BC:INTEGER,H1,H2,H3:CHAR;
  BEGIN
   DO
    WRITE(" N= ");
    READLN(N);
    IF N=0 THEN EXIT FI;
    WRITE(" BOAT CAPACITY=");
    READLN(BC);

    PREF DFS BLOCK
    VAR M,C:INTEGER;  (* BC - BOAT CAPACITY, N- NUMBER OF CANNIBALS
					     N- NUMBER OF MISSIONARS *)
    UNIT STATE: NODE CLASS(M1,C1:INTEGER);
      VAR M2,C2:INTEGER, LEFT:BOOLEAN;
	    (* M1,M2 NUMBER OF MISSIONARS ON BOTH SIDES OF THE RIVER
	       C1,C2 NUMBER OF CANNIBALS ON BOTH SIDES OF THE RIVER *)

      UNIT VIRTUAL ANSWER: FUNCTION: BOOLEAN;
      BEGIN
	RESULT:=M1=0 AND C1=0
      END ANSWER;

      UNIT VIRTUAL LEAF: FUNCTION : BOOLEAN;
      BEGIN
	IF  M1<0 ORIF M2<0 ORIF C1<0 ORIF C2<0 ORIF
	    M1>N ORIF M2>N ORIF C1>N ORIF C2>N ORIF
	    M1<C1 AND M1>0 ORIF M2<C2 AND M2>0
	THEN
	  RESULT:=TRUE
	FI
      END LEAF;


      UNIT VIRTUAL LASTSON: FUNCTION :BOOLEAN;
      BEGIN
	IF C=0 AND M=BC
	THEN
	  RESULT:=TRUE; M:=0; C:=0;
	FI;
      END;

      UNIT VIRTUAL NEXTSON : FUNCTION :STATE;
      BEGIN
	C:=C+1;
	IF M=0
	THEN
	  IF C>BC
	  THEN
	    C:=0; M:=1
	  FI
	ELSE
	  IF M<C ORIF M+C>BC
	  THEN
	    C:=0; M:=M+1;
	  FI
	FI;
	IF LEFT
	THEN
	  IF C+M<BC
	  THEN
	    RESULT:=NONE
	  ELSE
	    RESULT:=NEW STATE(THIS STATE,M1-M,C1-C)
	  FI
	ELSE
	  RESULT:=NEW STATE(THIS STATE,M1+M,C1+C)
	FI;
      END NEXTSON;

      UNIT VIRTUAL EQUAL: FUNCTION(W:STATE):BOOLEAN;
      BEGIN
	RESULT:=LEFT=W.LEFT AND M1=W.M1 AND C1=W.C1;
      END EQUAL;

      UNIT VIRTUAL COST: FUNCTION :REAL;
      BEGIN
	RESULT:=LEVEL
      END COST;


    BEGIN
      LEFT:=LEVEL MOD 2 = 0;
      M2:=N-M1; C2:=N-C1;
    END STATE;


    UNIT DISPLAY: PROCEDURE(V:STATE);
      VAR J,I:INTEGER, W:STATE,AT: ARRAYOF STATE;
    BEGIN
      IF V=NONE THEN WRITELN(" NO MORE SOLUTIONS"); RETURN FI;
      I:=V.LEVEL;
      ARRAY AT DIM (0:I);
      W:=V;
      FOR J:=I DOWNTO 0
      DO
	AT(J):=W; W:=W.FATHER
      OD;
      WRITELN("MOVE NUMBER    LEFT SIDE  DIRECTION   RIGHT SIDE");
      FOR J:=0 TO I
      DO
	WRITE(J); WRITE("     ");
	W:=AT(J);
	WRITE(W.M1,W.C1,"      ");
	IF W.LEFT
	THEN
	  WRITE("->");
	ELSE
	  WRITE("<-");
	FI;
	WRITELN("    ",W.M2,W.C2);
      OD;
      KILL(AT);
    END DISPLAY;

    BEGIN
      ROOT:=NEW STATE(NONE,N,N);
      WRITE("DO YOU WANT TO OPTIMIZE ");
      WRITELN("OR TO PRINT ALL THE SOLUTIONS ?");
      WRITELN(" (ANSWER OPT OR ALL)");
      READLN(H1,H2,H3);
      IF H1='O' AND H2='P' AND H3='T'
      THEN
	FOUND:=OPTIMIZE;
	IF FOUND =/= NONE
	THEN
	  CALL DISPLAY(FOUND);
	  WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
	  WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
	ELSE
	  WRITELN(" NO SOLUTIONS");
	  WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
	FI;
	CALL KILLALL;
      ELSE
	IF H1='A' AND H2='L' AND H3='L'
	THEN
	  DO
	    ATTACH(SEARCH);
	    CALL DISPLAY(FOUND);
	    WRITELN("NUMBER OF LEAVES=",NUMBER_OF_LEAVES);
	    WRITELN("NUMBER OF ANSWERS=",NUMBER_OF_ANSWERS);
	    IF FOUND=NONE THEN EXIT FI
	  OD;
	  CALL KILLALL;
	FI
      FI;
    END;
  OD;



  END;

END