home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c220 / 4.ddi / DEMOS / QUEENSA.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-16  |  2.3 KB  |  77 lines
  1. /* This program computes ALL solutions to the n-queens problem. */
  2. /* The board size is input at the beginning of execution.    */
  3.  
  4. /* From Wirth's Algorithms+Data Structures = Programs.          */
  5. /* This program is suitable for a code-generation benchmark,    */
  6. /* especially given common sub-expressions in array indexing.    */
  7. /* See the Programmer's Guide for how to get a machine code     */
  8. /* interlisting.  Also, use "pragma Memory_model(Small)"        */
  9. /* on the 8088/86/186/286 family to see the best results.    */
  10.  
  11. /* The next 4 lines are for the benefit of Lattic C, which lacks
  12.    the "void" type or enumerations.
  13.  
  14. #define void     /* */
  15.  
  16. #define False 0
  17. #define True 1
  18. #define Boolean char
  19.  
  20. #include <stdio.h>
  21.  
  22. typedef int Integer;
  23.  
  24. static Boardsize=0;
  25.  
  26. #define MaxBoardsize 20
  27.  
  28. #define Asub(I)  A[(I)-1]
  29. #define Bsub(I)  B[(I)-2]
  30. #define Csub(I)  C[(I)+MaxBoardsize-1]
  31. #define Xsub(I)  X[(I)-1]
  32.  
  33. static Boolean A[MaxBoardsize /* 1. .MaxBoardsize */];
  34. static Boolean B[MaxBoardsize+MaxBoardsize-1 /* 2..(MaxBoardsize+MaxBoardsize) */];
  35. static Boolean C[MaxBoardsize+MaxBoardsize-1 /*-(MaxBoardsize-1)..(MaxBoardsize-1) */];
  36. static Integer X[MaxBoardsize /* 1.. MaxBoardsize */];
  37.  
  38. static Solutions=0;
  39.  
  40. #if 0
  41. static void Print() {
  42.    Integer I;
  43.    for (I = 1; I <= Boardsize;)
  44.       printf("%4d",Xsub(I++));
  45.    printf("\n");
  46.    }
  47. #else
  48. /* Get rid of output provided above, for benchmarking;
  49.    change if 0 to if 1 above to see all the solutions:
  50. */
  51. #define Print()
  52. #endif
  53. static void Try(I) Integer I; {
  54.    Integer J;
  55.    for (J = 1; J <= Boardsize; J++)
  56.       if (Asub(J) && Bsub(I+J) && Csub(I-J)) {
  57.      Xsub(I) = J;
  58.      Asub(J) = False; Bsub(I+J) = False; Csub(I-J) = False;
  59.      if (I < Boardsize) Try(I+1); else {Print(); Solutions++;}
  60.      Asub(J) = True; Bsub(I+J) = True; Csub(I-J) = True;
  61.      }
  62.    }
  63.  
  64. void main () {
  65.    Integer J,I,iter;
  66.    printf("Boardsize; #iterations?");
  67.    scanf("%d %d",&Boardsize,&iter);
  68.    printf("Starting test...");
  69.    for (J = 0; J < iter; J++) {
  70.       for (I =    1; I <=  Boardsize; Asub(I++) = True);
  71.       for (I =    2; I <= Boardsize+Boardsize; Bsub(I++) = True);
  72.       for (I = -(Boardsize-1); I <=  Boardsize+1; Csub(I++) = True);
  73.       Try(1);
  74.       }
  75.    printf("End of test; %d solutions.\n",Solutions);
  76.    }
  77.