#define true 1
#define false 0
+#define static
+
//static int *row;
// queen in column c is at row[c]
int j = 0;
boolean res;
+#if 0
+ if(0 >= i)
+ return true;
+
+ do {
+ int rj = r[j];
+ if ((rj == ri) || ((myabs(ri-rj)) == (i-j))) {
+ res = false;
+ return(res);
+ }
+ j = j+1;
+ } while(j < i);
+
+ res = true;
+ return(res);
+#else
while (j < i) {
- if ((r[j] == ri) || ((myabs(ri-r[j])) == (i-j))) {
+ int rj = r[j];
+ if ((rj == ri) || ((myabs(ri-rj)) == (i-j))) {
res = false;
return(res);
}
res = true;
return(res);
+#endif
}
int solve (int n) {
// return the number of solutions to the n-queens problem
int c = 0;
int res = 0;
- int *row;
+ int *row;
row = malloc(sizeof(*row) * n);
row[0] = -1;
while (c >= 0) {
- int ri;
-#if 1
+ int rc = row[c];
+
do {
- row[c] = ri = row[c]+1;
- } while ((ri < n) && (!place_ok(c, row, ri)));
-#else
- row[c] = row[c]+1;
- while ((row[c] < n) && (!place_ok(c, row))) {
- row[c] = row[c]+1;
- }
-#endif
- if (row[c] < n) { // successfully placed at (c,row[c])
+ rc++;
+ } while ((rc < n) && (!place_ok(c, row, rc)));
+
+ if (rc < n) { // successfully placed at (c,row[c])
+ row[c] = rc;
+
if (c == n-1)
res = res+1;
else {
c = c+1;
row[c] = -1;
}
+ continue;
}
- else // dead end, track back
- c = c-1;
+
+ row[c] = rc;
+ c = c-1;
}
free(row);