# N-Queens with backtracking in C

The n-queens problem is to place n queens on an n × n chessboard such that no two queens threaten each other by sharing the same row, column, or diagonal. For the usual 8 × 8 chessboard, there are $${64 \choose 8}$$ = 4,426,165,368 ways of placing the queens, but only 92 solutions. This is a classic problem for a backtracking algorithm.

typedef void(*queenfn)(unsigned int *, size_t);

static unsigned int promising(unsigned int *board, int i, size_t n)
{
int j;
unsigned int ok = 1;
for (j = 0; j < i && ok; j++) {
if (board[i] == board[j] || abs((int)board[i] - (int)board[j]) == i - j) {
ok = 0;
}
}
return ok;
}

static void n_queens_recursive(unsigned int *board, int i, size_t n, queenfn fun)
{
if (promising(board, i, n)) {
if (i == (int)n - 1) {
fun(board, n);
}
else if (i < (int)n - 1) {
unsigned int square;
for (square = 0; square < n; square++) {
board[i + 1] = square;
n_queens_recursive(board, i + 1, n, fun);
}
}
}
}

void n_queens(size_t n, queenfn fun)
{
unsigned int *board = malloc(n * sizeof(unsigned int));
if (board == NULL) {
return;
}
n_queens_recursive(board, -1, n, fun);
free(board);
}

void print(unsigned int *board, size_t n)
{
int i;
for (i = 0; i < n; i++) {
printf("%d ", board[i]);
}
printf("\n");
}

int main(void)
{
const unsigned int n = 8;
n_queens(n, print);
return 0;
}