N-Queens without recursion (but with one goto)

Question

Compared to the recursive version e.g. on Rosetta, this is 5-10% faster and uses 50% less instructions (for N=12).

Only problem is the goto. Can it be avoided without using a function?

The two outer for-loops don't do much in terms of loop control. But this is how I could make it work.

Is there a more convincing non-recursive version? I searched quite a bit and most are recursive and/or longer.

/* N-Queens, non-recursive, with goto */
#include <stdio.h>
//const int N = 8; //92 solutions
const int N = 12; //14200 in 0.100 s
/* Print excluding last row, plus last col */
void pr_solution(int *bq, int col) {
 for (int i = 0; i < N - 1; i++)
 printf("%d:", bq[i]);
 printf("%d\n", col);
} 
void init_board(int bq[], int v) {
 for (int i = 0; i < N; i++)
 bq[i] = v;
}
int main() {
 int bq[N];
 init_board(bq, -1); 
 int row, col, rd, old;
 int cnt = 0;
 for (row = 0; row >= 0;) {
 
 for (col = bq[row];;) {
 NEXT_col:
 if (++col == N) 
 bq[row--] = -1;
 else {
 for (rd = 1; rd <= row; rd++)
 if ((old = bq[row-rd]) == col || old == col+rd || old == col-rd)
 goto NEXT_col;
 if (row == N - 1) {
 cnt++;
 row--;
 //pr_solution(bq, col); 
 }
 else 
 bq[row++] = col;
 }
 break;
 }
 }
 printf("%d SOLUTIONS (%dx%d)\n", cnt, N, N);
 return 0;
}

Answer 1

Only problem is the goto. Can it be avoided without using a function?

Candidate goto replacement

 for (col = bq[row];;) {
 //NEXT_col: // Delete
 if (++col == N) 
 bq[row--] = -1;
 else {
 for (rd = 1; rd <= row; rd++)
 if ((old = bq[row-rd]) == col || old == col+rd || old == col-rd)
 // goto NEXT_col; // Delete
 break; //ADD
 if (rd <= row) continue; // ADD
 if (row == N - 1) {
 cnt++;
 row--;
 //pr_solution(bq, col); 
 }
 else 
 bq[row++] = col;
 }
 break;
 }

if (rd <= row) continue; takes advantage that for (col = bq[row];;) lacks a test and increment.

Is there a more convincing non-recursive version?

I'd re-write the loop (perhaps a state machine) - need some time to think about it.

---

Later:

Code as written is quite tight. A very nice simple non-recursive solution.

Yet (at the risk of the ire of OP) lacks clarity making it unnecessarily difficult to optimize.

The style uses terse variable names like rd and bq which do not well convey their meaning. It is as if short variable names make faster code (it does not). init_board() does not initialize a board, but a single dimension of data. Use more meaningful names.

Use of incomplete for loops like for (col = bq[row];;) seems like a code golf goal than a clearer col = bq[row]; while (1).

Helper functions like pr_solution() rely on the global N, which instead could be passed in, facilitating clearer function flow and allowing use with more than one size.

Local variable instantiation would help see their limited impact.

For clarity, use {} even for one-line blocks.

Consider rectangles, not only squares. It adds clarity to code and offers other investigations for eventual optimization.

Some other ideas in code below too.

A first round cut:

int main(void) {
 for (int N = 1; N <= 8; N++) {
 const int ROW_N = N;
 const int COL_N = ROW_N;
 int queen_column[ROW_N];
 init_queen_column(ROW_N, queen_column, -1);
 long long count = 0;
 int parity[2] = { 0,0};
 int row = 0;
 while (row >= 0) {
 int col = queen_column[row];
 while (1) {
 if (++col == COL_N) {
 queen_column[row--] = -1;
 } else {
 int row_offset;
 for (row_offset = 1; row_offset <= row; row_offset++) {
 int old = queen_column[row - row_offset];
 int diff = old - col;
 if ((diff == 0) || diff == row_offset || diff == -row_offset) {
 break;
 }
 }
 if (row_offset <= row) { // From early break above
 continue; // ADD
 }
 if (row == ROW_N - 1) {
 count++;
 // print_solution(ROW_N, queen_column, col); // Print, then change state.
 row--;
 } else {
 parity[(row ^ col)&1]++; // Count parity for later optimization (stub code)
 queen_column[row++] = col;
 }
 }
 break;
 }
 }
 printf("%lld SOLUTIONS (%dx%d)\n", count, ROW_N, COL_N);
 }
 return 0;
}
1 SOLUTIONS (1x1)
0 SOLUTIONS (2x2)
0 SOLUTIONS (3x3)
2 SOLUTIONS (4x4)
10 SOLUTIONS (5x5)
4 SOLUTIONS (6x6)
40 SOLUTIONS (7x7)
92 SOLUTIONS (8x8)

---

Other idea to speed things up

1. Keep track of the count of queen placement on black (and/or white) squares. Once that exceeds about half of N, time to unwind as subsequent forward iterations will all fail.

2. Look for patterns. Example: Symmetry. A solution that starts with the first queen on column 0 will have as many solutions as column N-1. Looks like run time can be halved in some fashion.

• user236420: I DID rewrite the loop - dropped it, see answer. Now there is mostly lf-else, and this makes it more state-machiney.

Answer 2

void pr_solution(int *bq, int col) {
void init_board(int bq[], int v) {

These could be declared with static linkage.

---

int main() {

Prefer int main(void) to make this declaration a prototype (takes no arguments, rather than unspecified arguments).

---

int row, col, rd, old;

All of these could have smaller scope. E.g.

for (int row = 0; row >= 0;) {

It's always best to declare and initialise at the same time, rather than leaving a window where the variable exists but is not initialised.

---

 //pr_solution(bq, col);

Commented-out code is prone to becoming inconsistent. Either remove it, or uncomment it (and perhaps provide a command-line argument to enable/disable).

Answer 3

The second for-loop does so little, it can be replaced by a label, IF you stick with the goto:

for (row = 0; row >= 0;) {
 col = bq[row];
 NEXT_col:
 if (++col == N)
 bq[row--] = -1;
 else {
 for (rd = 1; rd <= row; rd++)
 if ((old = bq[row-rd]) == col || abs(old - col) == rd)
 goto NEXT_col;
 if (row == N - 1) {
 cnt++;
 row--;
 }
 else
 bq[row++] = col;
 }
}

No more break at the end. That was the other thing that for-loop did: getting broken at the end. The first thing was: being jumped at with continue (or goto).

I am quite happy now - it is still a "goto", but now it makes sense.

As they say about this N-Queens problem: simple, but not trivial.

Answer 4

It turns out that keeping track of the threats in a 2D-array is twice as fast. Now instead of incrementing the column, and checking later, the next column is found by a function.

The main loop is freed from the diagonal-checking. But now it has to add and also remove threats when a queen is moved.

/* Returns zeroed n*n array */
int **init_threats(int n) {
 int r;
 int **t2d = malloc(n * sizeof*t2d);
 for (r = 0; r < n; r++)
 t2d[r] = calloc(n, sizeof**t2d);
 return t2d;
}
/* Only needs a row from "threats[][]" */
int next_free(int *r, int after) {
 for (int c = after + 1; c < N; c++)
 if (r[c] == 0)
 return c;
 return -1;
}
/* Cumulative threats - they can overlap */
void change_thr(int chg, int r, int c, int **threats) {
 int tr, diag;
 for (tr = r + 1; tr < N; tr++) { 
 threats[tr][c] += chg;
 diag = c + tr - r;
 if (diag < N)
 threats[tr][diag] += chg; 
 diag = c - (tr - r);
 if (diag >= 0)
 threats[tr][diag] += chg; 
 }
}
int main() {
 int queen[N];
 init_board(queen, -1); 
 int **threats = init_threats(N);
 int row = 0, cnt = 0;
 int col;
 while (row >= 0) {
 col = next_free(threats[row], queen[row]);
 if (row == N - 1) { 
 if (col >= 0) 
 cnt++;
 row--;
 } else {
 if (queen[row] >= 0)
 change_thr(-1, row, queen[row], threats); 
 if (col >= 0) {
 change_thr(1, row, col, threats); 
 queen[row++] = col;
 } else 
 queen[row--] = -1;
 }
 } 
 printf("%d SOLUTIONS (%d-Queens)\n", cnt, N);
 return 0;
}