Though I’ve already implemented the basic recursive N queens solution, I’m trying to learn more about backtracking by studying and implementing Knuth’s “Algorithm B (Basic backtrack)” for the case of the N queens problem in C. If you want to read it, it’s here (https://cs.stanford.edu/~knuth/fasc5b.ps.gz). This is the code I have written so far, and it works well. It’s a straightforward translation of what he wrote into C using goto statements (with a few parts changed to account for zero-indexed arrays instead of one-indexed arrays).

// x and a are both N elements long, while b and c are 2*N-1 elements long.
// It is assumed that these arrays are zeroed before this routine is called.
static void queens(int x[], bool a[], bool b[], bool c[], const size_t n) {
    size_t col, row = 0;

advance_row:
    if (row >= n) {
        // e.g. print "a1 b4 c1 d3" if n is 4
        print_positions(x, n);
        goto backtrack;
    }
    col = 0;
try_column:
    if (!a[col] && !b[col+row-1] && !c[col-row+n]) {
        a[col] = true;
        b[col+row-1] = true;
        c[col-row+n] = true;
        x[row] = col;
        row++;
        goto advance_row;
    }
try_again:
    if (col < n-1) {
        col++;
        goto try_column;
    }
backtrack:
    if (row != 0) {
        --row;
        col = x[row];
        c[col-row+n] = false;
        b[col+row-1] = false;
        a[col] = false;
        goto try_again;
    }
}

From what I can tell, this algorithm has an irreducible control flow graph (CFG). I drew a CFG of Algorithm B to illustrate below. Because of this, I expect it to be impossible to implement using just while-loops, for-loops, and if-statements, though I have tried. I expect that some state will need to be kept in a variable, but I don’t know how to represent this graph like that.

What I’ve tried and what happened: although I haven’t written any versions without the use of the goto statement, I have tried to replace the use of a couple goto statements in this code. This is one of the versions of the function I have made, but note that it is incorrect; for n = 4, it prints the first 2 solutions correctly, but prints 58 more incorrect solutions.

static void queens(int x[], bool a[], bool b[], bool c[], const size_t n) {
    for (size_t row = 0, col = 0; ; col++) {
        while (!a[col] && !b[col+row-1] && !c[col-row+n]) {
            a[col] = true;
            b[col+row-1] = true;
            c[col-row+n] = true;
            x[row] = col;
            row++;
            if (row >= n) {
                print_positions(x, n);
                goto backtrack;
            }
            col = 0;
        }
        if (col < n - 1) {
            continue;
        }
    backtrack:
        if (row == 0) break;
        else do {
            --row;
            col = x[row];
            c[col-row+n] = false;
            b[col+row-1] = false;
            a[col] = false;
            if (col < n - 1) {
                break;
            }
        } while (row != 0);
    }
}