home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / insidetp / 1990_04 / queen1.pas < prev    next >
Pascal/Delphi Source File  |  1990-03-19  |  2KB  |  93 lines
  1. {************************************************
  2. * QUEEN1 - the first 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 Queen1;
  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 Byte;
  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 : 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.  
  57.           Legal := TRUE;  {Legal until disproven}
  58.  
  59.           FOR J := 1 TO C DO
  60.  
  61.             BEGIN
  62.  
  63.               {-- Check row --}
  64.  
  65.               IF (Board[I,C-J] <> 0) THEN
  66.                 Legal := FALSE;
  67.  
  68.               {-- Check diagonal 1 --}
  69.  
  70.               IF ((I+J) < N) THEN
  71.                 IF (Board[I+J,C-J] <> 0) THEN
  72.                   Legal := FALSE;
  73.  
  74.               {-- Check diagonal 2 --}
  75.  
  76.               IF ((I-J) >= 0) THEN
  77.                 IF (Board[I-J,C-J] <> 0) THEN
  78.                   Legal := FALSE;
  79.             END;
  80.  
  81.           IF (Legal) THEN
  82.  
  83.             BEGIN
  84.               Board[I,C] := 1; {Put queen here}
  85.               Queens(C+1,N);   {Process next col}
  86.               Board[I,C] := 0  {Remove & try next}
  87.             END;
  88.         END;
  89.     END;
  90. END;
  91.  
  92. END.
  93.