home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c220 / 4.ddi / DEMOS / QUEENS.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-16  |  1.8 KB  |  61 lines
  1. /* From Wirth's Algorithms+Data Structures = Programs. */
  2. /* This program is suitable for a code-generation      */
  3. /* benchmark, especially given common sub-expressions  */
  4. /* in array indexing.  See the Programmer's Guide for  */
  5. /* how to get a machine code interlisting.             */
  6.  
  7. pragma    Title("Eight Queens problem.");
  8.  
  9. #include <stdio.h>
  10.  
  11. typedef enum{False,True} Boolean;
  12. typedef int Integer;
  13.  
  14. #define Asub(I)  A[(I)-1] /* C's restriction that array*/
  15. #define Bsub(I)  B[(I)-2] /* indices start at zero     */
  16. #define Csub(I)  C[(I)+7] /* prompts definition of     */
  17. #define Xsub(I)  X[(I)-1] /* macros to do subscripting.*/
  18.                 /* Pascal equivalents:     */
  19. static Boolean A[ 8 /* 1.. 8 */]; /* A:array[ 1.. 8] of Boolean    */
  20. static Boolean B[15 /* 2..16 */]; /* B:array[ 2..16] of Boolean    */
  21. static Boolean C[15 /*-7.. 7 */]; /* C:array[-7.. 7] of Boolean    */
  22. static Integer X[ 8 /* 1.. 8 */]; /* X:array[ 1.. 8] of Integer    */
  23.  
  24. void Try(Integer I, Boolean *Q) {
  25.    Integer J = 0;
  26.    do {
  27.       J++; *Q = False;
  28.       if (Asub(J) && Bsub(I+J) && Csub(I-J)) {
  29.      Xsub(I) = J;
  30.      Asub(J) = False; 
  31.      Bsub(I+J) = False; 
  32.      Csub(I-J) = False;
  33.      if (I < 8) {
  34.         Try(I+1,Q);
  35.         if (!*Q) {
  36.            Asub(J) = True; 
  37.            Bsub(I+J) = True; 
  38.            Csub(I-J) = True;
  39.            }
  40.         }
  41.      else *Q = True;
  42.      }
  43.       }
  44.    while (!(*Q || J==8));
  45.    }
  46. pragma Page(1); /* Page eject requested. */
  47. void main () {
  48.    Integer I; Boolean Q;
  49.    printf("%s\n","go");
  50.    for (I =  1; I <=  8; Asub(I++) = True);
  51.    for (I =  2; I <= 16; Bsub(I++) = True);
  52.    for (I = -7; I <=  7; Csub(I++) = True);
  53.    Try(1,&Q);
  54. pragma Skip(3); /* Skip 3 lines. */
  55.    if (Q)
  56.       for (I = 1; I <= 8;) {
  57.      printf("%4d",Xsub(I++));
  58.      }
  59.    printf("\n");
  60.    }
  61.