N-Queens Problem in C – Backtracking Solution with All Solutions

The N-Queens problem asks: place N chess queens on an N×N board so that no two queens share a row, column, or diagonal. The standard C solution uses backtracking — place queens one row at a time, try every column in that row, recurse if the placement is safe, and undo (backtrack) if a dead end is reached. For N=4, there are exactly 2 solutions. For N=8, there are 92. This page gives a clean C89 implementation with an explicit safety check and a step-by-step explanation of how the recursion and backtracking work together.

The Key Representation: queens[] Array

Rather than a full N×N boolean grid, store only one integer per row:

int queens[N];   /* queens[row] = col means the queen in row 'row' sits in column 'col' */

This works because the constraint "one queen per row" is enforced by the algorithm itself — we place exactly one queen per row, row by row. The column and diagonal constraints are what the is_safe() function checks.

The Safety Check

Two queens at (i, queens[i]) and (row, col) conflict if:

• Same column: queens[i] == col
• Same diagonal (\): queens[i] - col == i - row — both are on the same top-left to bottom-right diagonal when their row difference equals their column difference
• Same diagonal (/): queens[i] - col == row - i — on the same top-right to bottom-left diagonal when the differences are negatives of each other

Equivalently: |queens[i] - col| == |i - row| catches both diagonals in one expression, but the two separate checks avoid needing abs().

Backtracking Trace for N=4

Row 0, try col 0: safe → place. queens=[0,_,_,_]
  Row 1, try col 0: col conflict → skip
  Row 1, try col 1: diagonal conflict → skip
  Row 1, try col 2: safe → place. queens=[0,2,_,_]
    Row 2, try col 0: diagonal conflict → skip
    Row 2, try col 1: diagonal conflict → skip
    Row 2, try col 2: col conflict → skip
    Row 2, try col 3: diagonal conflict → skip
    Row 2: no column works → BACKTRACK to row 1
  Row 1, try col 3: safe → place. queens=[0,3,_,_]
    Row 2, try col 0: diagonal conflict → skip
    Row 2, try col 1: safe → place. queens=[0,3,1,_]
      Row 3: no column works → BACKTRACK to row 2
    Row 2: no more columns → BACKTRACK to row 1
  Row 1: no more columns → BACKTRACK to row 0
Row 0, try col 1: safe → place. queens=[1,_,_,_]
  Row 1, try col 3: safe → place. queens=[1,3,_,_]
    Row 2, try col 0: safe → place. queens=[1,3,0,_]
      Row 3, try col 2: safe → place. queens=[1,3,0,2]
        Row 4 == N: SOLUTION FOUND ✓

The first complete solution is queens=[1,3,0,2], which maps to the board:

. Q . .
. . . Q
Q . . .
. . Q .

C Program: N-Queens Using Backtracking

/* N-Queens problem — backtracking solution
 * Compile: gcc -ansi -Wall -Wextra nqueens.c -o nqueens */
#include <stdio.h>
#define MAXN 12

/* queens[row] = col means the queen in 'row' sits in column 'col'. */

/* Return 1 if placing at (row, col) conflicts with no earlier queen. */
int is_safe(int queens[], int row, int col)
{
    int i;
    for (i = 0; i < row; i++) {
        if (queens[i] == col)            return 0;  /* same column  */
        if (queens[i] - col == i - row)  return 0;  /* diagonal \   */
        if (queens[i] - col == row - i)  return 0;  /* diagonal /   */
    }
    return 1;
}

void print_board(int queens[], int n, int num)
{
    int i, j;
    printf("Solution %d:\n", num);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%c ", queens[i] == j ? 'Q' : '.');
        printf("\n");
    }
    printf("\n");
}

/* Try each column in the current row; recurse on success. */
void solve(int queens[], int row, int n, int *count)
{
    int col;
    if (row == n) {
        (*count)++;
        if (n <= 8) print_board(queens, n, *count);
        return;
    }
    for (col = 0; col < n; col++) {
        if (is_safe(queens, row, col)) {
            queens[row] = col;          /* place */
            solve(queens, row + 1, n, count);
            /* backtrack: the next iteration overwrites queens[row] */
        }
    }
}

int main(void)
{
    int queens[MAXN];
    int n, count = 0;

    printf("Enter N (1-%d): ", MAXN);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAXN) {
        printf("Invalid.\n"); return 1;
    }
    if (n > 8) printf("(boards suppressed for N>8, counting only)\n\n");

    solve(queens, 0, n, &count);
    printf("N = %d : %d solution%s\n", n, count, count == 1 ? "" : "s");
    return 0;
}

Sample Output (N=4)

Enter N (1-12): 4
Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .

Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

N = 4 : 2 solutions

Solution Counts by Board Size

N	Solutions	Notes
1	1	Trivial — one queen on a 1×1 board
2	0	Any two queens on a 2×2 board attack each other
3	0	No valid arrangement exists
4	2	Smallest non-trivial solution
5	10
6	4	Fewer than N=5 — not monotonically increasing
7	40
8	92	Classic problem; 12 "fundamental" solutions ignoring symmetry
10	724
12	14200	Maximum supported by this program

Code Explanation

• Row-by-row placement: The algorithm always maintains the invariant that queens in rows 0..row−1 are already valid — no two attack each other. is_safe() only needs to check the new queen against rows 0..row−1, never against other future rows, because they are empty.
• The diagonal formula: On the main diagonal (top-left to bottom-right), every cell satisfies row − col = constant. On the anti-diagonal, row + col = constant. The checks queens[i] − col == i − row and queens[i] − col == row − i detect these two diagonal families without needing absolute values or separate row/column arithmetic.
• Backtracking without an explicit undo: After the recursive call solve(queens, row+1, n, count) returns, the loop's next iteration calls is_safe(queens, row, col+1) and, if safe, writes queens[row] = col+1. This overwrite is the undo — there is no need to set queens[row] = -1 or similar cleanup. The value in queens[row] is meaningless until overwritten by the next safe column assignment.
• Passing count by pointer: Using int *count avoids a global variable. Every recursive call shares the same counter through the pointer. This is the idiomatic C pattern for accumulating results across a recursive search.
• Print only for N≤8: N=8 produces 92 boards (manageable); N=12 produces 14,200 (stdout flood). The guard if (n <= 8) suppresses board printing for large N while still computing the correct count.

Frequently Asked Questions

Related Programs

• DFS in C – Depth-First Search (same recursive exploration pattern)
• Tower of Hanoi in C – Recursive Problem
• Pascal's Triangle in C
• Factorial in C – Recursion

Recommended books:
The C Programming Language — K&R (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Test your C recursion knowledge: C Aptitude Questions — or try our C Programming Quiz App on Android.