00050 .PR POINT .PR
00110 # QUEEN #
00120 .COMMENT THIS PROGRAM PLACES 8 QUEENS ON A CHESSBOARD
00130 SUCH THAT NO TWO QUEENS ATTACK ONE ANOTHER. THE METHOD USED
00140 IS OF RECURSIVE DESCENT : ALL VALID POSSIBILITIES
00150 ON A GIVEN ROW ARE TRIED - EACH PRODUCES ANOTHER BRANCH OF
00160 POSSIBILITIES ON FURTHER ROWS. IF A QUEEN MAY BE PLACED ON THE
00170 LAST ROW THEN THIS IS A SOLUTION AND IS OUTPUT.
00180 NOTE: TO SAVE MACHINE TIME SIMPLE REFLECTIONS ARE PRODUCED
00190 MECHANICALLY IF EXHAUSTIVE SOLUTIONS ARE ONLY FOUND FOR
00200 THE QUEEN ON THE FIRST ROW POSITIONS 1,2,3,4. THE
00210 SYMMETRY OF THE CHESSBOARD MEANS THAT SOLUTIONS WITH
00220 THE QUEEN IN ROW 1 IN POSITIONS 5,6,7,8 CORRESPOND 1-1
00230 WITH THESE.
00240 .COMMENT
00250 ##
00260 .BEGIN
00270 .LOC .INT ROW := 0, COUNTSOLN := 0;
00280 .LOC[1:8].INT RESULT;
00282 .LOC[1:8, -6:15].BOOL ALLOWS;
00290 ##
00300 .PROC SOLUTIONHEAD = .VOID:
00310   .BEGIN PRINT((NEWLINE, "SOLUTION", WHOLE(COUNTSOLN, -5), ":- ")); COUNTSOLN +:=1 .END;
00320 ##
00330 .PROC PLACE = (.INT POSITION).VOID:
00340   .COMMENT THIS IS A RECURSIVE PROCEDURE.
00350   IT ALLOCATES ALL POSSIBLE VALUES IN THE CURRENT ROW AS DEFINED
00360   BY EACH ROW. AFTER CONSIDERING WHICH SQUARES ARE NOT PERMISSIBLE
00370   (BECAUSE ALREADY ATTACKED), IT OUTPUTS ANY SOLUTIONS IT FINDS
00380   (I.E. WHEN WE REACH THE LAST ROW).
00390   .COMMENT
00400   .BEGIN
00420     ROW +:= 1; RESULT[ROW] := POSITION;
00422     .REF [] .BOOL ALLOW = ALLOWS[ROW, ];
00430     .IF ROW=8
00440     .THEN #WE HAVE FOUND SOLUTION NUMBER COUNTSOLN
00450           SO OUTPUT IT#
00460       SOLUTIONHEAD;
00470       .FOR K .TO 8 .DO PRINT(.REPR(RESULT[K]+.ABS"0")) .OD;
00480       SOLUTIONHEAD;
00490       .FOR K .TO 8 .DO PRINT(.REPR(9-RESULT[K]+.ABS"0")) .OD
00500     .ELSE
00510       .FOR I .TO 8 .DO ALLOW[I] := .TRUE .OD;
00520         #DISALLOW ATTACKED SQUARES#
00530       .FOR I .TO ROW
00540       .DO .INT RES = RESULT[I];
00550         ALLOW[RES] := .FALSE;
00560         ALLOW[RES+ROW+1-I] := .FALSE;
00570         ALLOW[RES-ROW-1+I] := .FALSE
00580       .OD;
00590         #CONSTRUCT ANOTHER LEVEL WHERE POSSIBLE#
00600       .FOR I .TO 8 .DO .IF ALLOW[I] .THEN PLACE(I) .FI .OD
00610     .FI;
00620     #NOW UP A LEVEL#
00630     ROW -:= 1
00640   .END; #OF PLACE#
00650 ##
00660 #INITIALISE OUTPUT#
00670 PRINT(("PLACEMENT OF QUEENS SUCH THAT NO TWO"
00680        " ATTACK EACH OTHER", NEWLINE));
00690 .FOR J .TO 4 .DO PLACE(J) .OD;
00700 #TIDY UP OUTPUT#
00710 PRINT(("LIST COMPLETE", NEWLINE))
00720 .END