MODULE AllQueens;
(* finds and prints all solutions of 8 queens problem *)
(* from N. Wirth, adapted to Turbo Modula-2 by Glenn Brooke 4/2/87 *)
(* This recursive program displays all 92 solutions to the 8 queens
problem. Wirth is a clever programmer, and I have not added
any explanatory comments to his code. Note : there are only
12 unique solutions to the problem -- you might be challenged
to rewrite the program to eliminate symmetrically redundant
solutions. *)
VAR
i : INTEGER;
a : ARRAY[1..8] OF BOOLEAN;
b : ARRAY[2..16] OF BOOLEAN;
c : ARRAY[-7..7] OF BOOLEAN;
x : ARRAY[1..8] OF INTEGER;
count : CARDINAL;
PROCEDURE print;
(* displays each solutions *)
VAR k : INTEGER;
BEGIN
count := count + 1;
WRITE(count," *** ");
FOR k := 1 TO 8 DO
WRITE(x[k]," ")
END;
WRITELN;
END print;
PROCEDURE Try(i : INTEGER);
(* recursive; key part of the program *)
VAR j : INTEGER;
BEGIN
FOR j := 1 TO 8 DO
IF a[j] & b[i+j] & c[i-j] THEN
x[i] := j;
a[j] := FALSE;
b[i+j] := FALSE;
c[i-j] := FALSE;
IF i < 8 THEN Try(i+1) ELSE print END;
a[j] := TRUE;
b[i+j] := TRUE;
c[i-j] := TRUE;
END
END
END Try;
BEGIN
FOR I := 1 TO 8 DO a[i] := TRUE END;
FOR I := 2 TO 16 DO b[i] := TRUE END;
FOR I := -7 TO 7 DO c[i] := TRUE END;
count := 0;
Try(1)
END AllQueens.