home *** CD-ROM | disk | FTP | other *** search
/ Oakland CPM Archive / oakcpm.iso / cpm / modula2 / allq.mzd / ALLQ.MOD
Encoding:
Text File  |  1987-04-26  |  1.5 KB  |  59 lines
  1. MODULE AllQueens;
  2.  
  3. (* finds and prints all solutions of 8 queens problem *)
  4. (* from N. Wirth, adapted to Turbo Modula-2 by Glenn Brooke 4/2/87 *)
  5.  
  6. (*  This recursive program displays all 92 solutions to the 8 queens
  7.     problem.  Wirth is a clever programmer, and I have not added
  8.     any explanatory comments to his code.  Note : there are only
  9.     12 unique solutions to the problem -- you might be challenged
  10.     to rewrite the program to eliminate symmetrically redundant
  11.     solutions.   *)
  12.  
  13.  
  14. VAR
  15.   i : INTEGER;
  16.   a : ARRAY[1..8] OF BOOLEAN;
  17.   b : ARRAY[2..16] OF BOOLEAN;
  18.   c : ARRAY[-7..7] OF BOOLEAN;
  19.   x : ARRAY[1..8] OF INTEGER;
  20.   count : CARDINAL;
  21.  
  22. PROCEDURE print;
  23. (* displays each solutions *)
  24. VAR k : INTEGER;
  25. BEGIN
  26.   count := count + 1;
  27.   WRITE(count," *** ");
  28.   FOR k := 1 TO 8 DO
  29.      WRITE(x[k]," ")
  30.   END;
  31.   WRITELN;
  32. END print;
  33.  
  34. PROCEDURE Try(i : INTEGER);
  35. (* recursive; key part of the program *)
  36. VAR j : INTEGER;
  37. BEGIN
  38.   FOR j := 1 TO 8 DO
  39.     IF a[j] & b[i+j] & c[i-j] THEN
  40.       x[i] := j;
  41.       a[j] := FALSE;
  42.       b[i+j] := FALSE;
  43.       c[i-j] := FALSE;
  44.       IF i < 8 THEN Try(i+1) ELSE print END;
  45.       a[j] := TRUE;
  46.       b[i+j] := TRUE;
  47.       c[i-j] := TRUE;
  48.     END
  49.   END
  50. END Try;
  51.  
  52. BEGIN
  53.   FOR I := 1 TO 8 DO a[i] := TRUE END;
  54.   FOR I := 2 TO 16 DO b[i] := TRUE END;
  55.   FOR I := -7 TO 7 DO c[i] := TRUE END;
  56.   count := 0;
  57.   Try(1)
  58. END AllQueens.
  59.