home *** CD-ROM | disk | FTP | other *** search
/ Big Blue Disk 22 / bbd22.zip / QUEENS.PAS < prev    next >
Pascal/Delphi Source File  |  1988-01-26  |  2KB  |  63 lines
  1. {QUEENS.PAS = program to solve the
  2.  8-queens problem  by John Sigle  1/24/88 }
  3. PROGRAM EightQueens( Input, Output );
  4.  
  5. VAR K: INTEGER;
  6.     Success: Boolean;
  7.     InRow: ARRAY[1..8] OF BOOLEAN;
  8.     InDiag1: ARRAY[2..16] OF BOOLEAN;
  9.     InDiag2: ARRAY[-7..7] OF BOOLEAN;
  10.     QueenPos: ARRAY[1..8] OF INTEGER;
  11.  
  12.  
  13. PROCEDURE Try( Col: INTEGER );
  14.  
  15. VAR Row: INTEGER;
  16.  
  17. BEGIN { Try to place a queen in column Col }
  18.   Row := 0;
  19.   REPEAT   { Try each row }
  20.     Row := Row+1;
  21.     Success := FALSE;
  22.     IF {Test position} NOT (InDiag1[Col+Row]
  23.      OR InDiag2[Col-Row] OR InRow[Row]) THEN
  24.       BEGIN
  25.         { Set the queen }
  26.         QueenPos[Col] := Row;
  27.         InRow[Row] := TRUE;
  28.         InDiag1[Col+Row] := TRUE;
  29.         InDiag2[Col-Row] := TRUE;
  30.         IF Col<8 THEN
  31.           BEGIN { Try to place another }
  32.             Try( Col+1 );
  33.             IF NOT Success THEN
  34.               BEGIN  { Remove this queen }
  35.                 QueenPos[Col] := 0;
  36.                 InRow[Row] := FALSE;
  37.                 InDiag1[Col+Row] := FALSE;
  38.                 InDiag2[Col-Row] := FALSE
  39.               END
  40.           END
  41.         ELSE Success := TRUE
  42.       END
  43.   UNTIL Success OR (Row=8)
  44. END;   { of Try }
  45.  
  46. BEGIN    { Main program }
  47.  
  48.   { Initialize indicators }
  49.   FOR K := 1 TO 8 DO   InRow[K] := FALSE;
  50.   FOR K := 2 TO 16 DO  InDiag1[K] := FALSE;
  51.   FOR K := -7 TO 7 DO  InDiag2[K] := FALSE;
  52.   FOR K := 1 TO 8 DO   QueenPos[K] := 0;
  53.  
  54.   { Try to find a solution }
  55.   TRY( 1 );
  56.  
  57.   { Print the solution }
  58.   IF Success THEN
  59.     FOR K := 1 TO 8 DO  WRITE(QueenPos[K]);
  60.   WRITELN
  61.  
  62. END.  { of EightQueens }
  63.