queens.c (1699B)
1 /* From CLisp */ 2 3 /* Compute the number of solutions to the n-queens problem on a nxn 4 checkboard. */ 5 6 /* dynamic data structures are not needed for such a simple problem */ 7 #define nmax 100 8 9 int queens (int n) /* function definition in ISO/ANSI C style */ 10 { /* Compute the solutions of the n-queens problem. Assume n>0, n<=nmax. 11 We look for a function D:{1,...,n} -> {1,...,n} such that 12 D, D+id, D-id are injective. We use backtracking on D(1),...,D(n). 13 We use three arrays which contain information about which values 14 are still available for D(i) resp. D(i)+i resp. D(i)-i. */ 15 int dtab[nmax]; /* values D(1),...D(n) */ 16 int freetab1[nmax+1]; /* contains 0 if available for D(i) in {1,...,n} */ 17 int freetab2[2*nmax+1]; /* contains 0 if available for D(i)+i in {2,...,2n} */ 18 int freetab3a[2*nmax-1]; /* contains 0 if available for D(i)-i in {-(n-1),...,n-1} */ 19 #define freetab3 (&freetab3a[nmax-1]) 20 /* clear tables */ 21 { int i; for (i=1; i<=n; i++) { freetab1[i] = 0; } } 22 { int i; for (i=2; i<=2*n; i++) { freetab2[i] = 0; } } 23 { int i; for (i=-(n-1); i<n; i++) { freetab3[i] = 0; } } 24 {int counter = 0; 25 int i = 0; /* recursion depth */ 26 int* Dptr = &dtab[0]; /* points to next free D(i) */ 27 entry: /* enter recursion */ 28 i++; 29 if (i > n) { 30 counter++; 31 } else { 32 int j; 33 for (j = 1; j <= n; j++) { 34 if (freetab1[j]==0 && freetab2[j+i]==0 && freetab3[j-i]==0) { 35 freetab1[j]=1; freetab2[j+i]=1; freetab3[j-i]=1; 36 *Dptr++ = j; 37 goto entry; 38 comeback: 39 j = *--Dptr; 40 freetab1[j]=0; freetab2[j+i]=0; freetab3[j-i]=0; 41 } 42 } 43 } 44 i--; 45 if (i>0) goto comeback; 46 return counter; 47 }} 48