home *** CD-ROM | disk | FTP | other *** search
/ Oakland CPM Archive / oakcpm.iso / cpm / modula2 / knightst.mod < prev    next >
Encoding:
Text File  |  1987-01-08  |  1.3 KB  |  69 lines
  1. (* Find a path of a knight on a chess board which
  2.    covers all 64 squares. *)
  3.  
  4. MODULE knightstour;
  5.  
  6. FROM  InOut IMPORT WriteCard, WriteString, WriteLn;
  7.  
  8. CONST n = 5;
  9.       nsq = 25;
  10.  
  11. TYPE index = [1..n];
  12.      soi = SET OF index;
  13.  
  14. VAR i,j: index;
  15.     q: BOOLEAN;
  16.     s: soi;
  17.     a,b: ARRAY [1..8] OF INTEGER;
  18.     h: ARRAY [1..n],[1..n] OF INTEGER;
  19.  
  20. PROCEDURE try(i: INTEGER; x,y: index; VAR q: BOOLEAN);
  21. VAR k,u,v: INTEGER;
  22.     q1: BOOLEAN;
  23.  
  24. BEGIN
  25.   k := 0;
  26.   REPEAT
  27.     INC(k); q1 := FALSE;
  28.     u := INTEGER(x) + a[k];
  29.     v := INTEGER(y) + b[k];
  30.     IF (index(u) IN s) AND (index(v) IN s) THEN
  31.       IF h[u,v] = 0 THEN
  32.         h[u,v] := i;
  33.         IF i < nsq THEN
  34.           try(i+1,u,v,q1);
  35.           IF NOT q1 THEN h[u,v] := 0 END
  36.         ELSE
  37.           q1 := TRUE
  38.         END
  39.       END
  40.     END
  41.   UNTIL q1 OR (k = 8);
  42.   q := q1
  43. END try;
  44.  
  45. BEGIN
  46.   a[1] :=  2; b[1] :=  1;
  47.   a[2] :=  1; b[2] :=  2;
  48.   a[3] := -1; b[3] :=  2;
  49.   a[4] := -2; b[4] :=  1;
  50.   a[5] := -2; b[5] := -1;
  51.   a[6] := -1; b[6] := -2;
  52.   a[7] :=  1; b[7] := -2;
  53.   a[8] :=  2; b[8] := -1;
  54.   s := soi{1..5};
  55.   FOR i := 1 TO n DO
  56.     FOR j := 1 TO n DO h[i,j] := 0 END
  57.   END;
  58.   h[1,1] := 1; try(2,1,1,q);
  59.   IF q THEN
  60.     FOR i := 1 TO n DO
  61.       FOR j := 1 TO n DO WriteCard(h[i,j],5) END;
  62.       WriteLn
  63.     END
  64.   ELSE
  65.     WriteString('No Solution');
  66.     WriteLn
  67.   END
  68. END knightstour.
  69.