home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / insidetp / 1990_04 / queen3.pas < prev    next >
Pascal/Delphi Source File  |  1990-03-19  |  2KB  |  97 lines
  1. {************************************************
  2. * QUEEN3 - the third attempt at solving the     *
  3. * queens problem.                               *
  4. *                                               *
  5. * INP:    c - the column # to place a queen in    *
  6. *       n - the maximum column (& row) number   *
  7. * USES: Soln - updates this solution counter    *
  8. *       whenever a queen is successfully placed *
  9. *       in the n'th column.                     *
  10. ************************************************}
  11.  
  12. UNIT Queen3;
  13.  
  14. INTERFACE
  15.  
  16. CONST
  17.   MaxBrd = 25;
  18.  
  19. VAR
  20.   {Chess brd}
  21.   Board : ARRAY[0..MaxBrd+1,0..MaxBrd+1] OF Integer;
  22.   Solns : Integer;
  23.  
  24. PROCEDURE InitBoard;
  25. PROCEDURE Queens(C,N: Integer);
  26.  
  27.  
  28. IMPLEMENTATION
  29.  
  30.  
  31. PROCEDURE InitBoard;
  32.   BEGIN
  33.     FillChar(Board,SizeOf(Board),#0);
  34.     Solns := 0
  35.   END;
  36.  
  37.  
  38. PROCEDURE Queens;
  39.  
  40. VAR
  41.   I,J,K : Integer;
  42.   Legal : Boolean;
  43.  
  44. BEGIN
  45.   {Have we found a solution?}
  46.  
  47.   IF C=N THEN
  48.     Inc(Solns)
  49.   ELSE
  50.  
  51.    {Check each spot in the column}
  52.  
  53.    BEGIN
  54.      FOR I:= 0 TO N-1 DO
  55.        BEGIN
  56.        { Is square attacked by other queen?}
  57.          IF (Board[I,C] = 0) THEN
  58.            BEGIN
  59.              { No: take this square, and mark }
  60.              { all attacked squares to the right}
  61.              Board[I,C] := -1;
  62.              K := 1;
  63.              FOR J := C+1 TO N-1 DO
  64.                BEGIN
  65.                  Inc(Board[I,J]);  { On same row  }
  66.                  IF (I+K < N) THEN { On + diagonal}
  67.                     Inc(Board[I+K,J]);
  68.                  IF (I-K>=0) THEN  { On - diagonal}
  69.                     Inc(Board[I-K,J]);
  70.                  Inc(K)
  71.                END;
  72.  
  73.              { Now, compute rest of solution    }
  74.  
  75.              Queens(C+1,N);
  76.  
  77.              { Unmark this square, & all squares}
  78.              { attacked by this queen           }
  79.              Board[I,C] := 0;
  80.              K := 1;
  81.              FOR J := C+1 TO N-1 DO
  82.                BEGIN
  83.                  Dec(Board[I,J]);  {On same row}
  84.                  IF (I+K < N) THEN {On + diagonal}
  85.                    Dec(Board[I+K,J]);
  86.                  IF (I-K >= 0) THEN { On - diagonal}
  87.                    Dec(Board[I-K][J]);
  88.                  Inc(K)
  89.                END;
  90.            END;
  91.        END;
  92.    END;
  93. END;
  94.  
  95.  
  96. END.
  97.