N Queens Problem in DSA C

Mental Model

Place N queens on an NxN chessboard so that no two queens attack each other. We try positions row by row, backtracking when conflicts arise.

Analogy: Imagine seating N guests at N tables in a row, where no two guests can see each other directly across or diagonally. You seat one guest per table and move to the next, changing seats if conflicts happen.

Board (4x4 example):
. . . .
. . . .
. . . .
. . . .

'.' means empty, 'Q' means queen placed.

Dry Run Walkthrough

Input: N=4, find one valid arrangement of 4 queens

Goal: Place 4 queens so none attack each other on a 4x4 board

Step 1: Place queen at row 0, column 0

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

Why: Start placing queen in first row at first column

Step 2: Row 1: col 0 vertical conflict, col 1 upper-left diag conflict, col 2 safe - place

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

Why: col 2 has no vertical or diagonal conflicts with row 0

Step 3: Row 2: all columns conflict (vertical or diagonal), backtrack to row 1

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

Why: No safe position in row 2, remove queen from row 1 col 2 and try next

Step 4: Backtrack fully from row 0 col 0 branch (no more cols in row 1), place row 0 col 1

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

Why: Previous branch failed, next column in row 0 is safe

Step 5: Row 1: cols 0-2 conflict, col 3 safe - place

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

Why: col 3 safe from row 0 col 1

Step 6: Row 2 col 0 safe (no vertical conflict now) - place

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

Why: col 0 clear of conflicts

Step 7: Row 3 col 2 safe - place, solution found

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

Why: Last queen placed successfully

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>
#define N 4

bool isSafe(int board[N][N], int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 1) return false; // check column
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) return false; // check upper left diagonal
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 1) return false; // check upper right diagonal
    }
    return true;
}

bool solveNQueens(int board[N][N], int row) {
    if (row == N) return true; // all queens placed
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1; // place queen
            if (solveNQueens(board, row + 1)) return true; // recurse
            board[row][col] = 0; // backtrack
        }
    }
    return false; // no safe position found
}

void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (board[i][j] == 1) printf("Q ");
            else printf(". ");
        }
        printf("\n");
    }
}

int main() {
    int board[N][N] = {0};
    if (solveNQueens(board, 0)) {
        printBoard(board);
    } else {
        printf("No solution found\n");
    }
    return 0;
}

for (int col = 0; col < N; col++) {

try each column in current row to place queen

if (isSafe(board, row, col)) {

check if placing queen here causes no conflicts

board[row][col] = 1; // place queen

place queen tentatively

if (solveNQueens(board, row + 1)) return true;

recurse to next row to place next queen

board[row][col] = 0; // backtrack

remove queen if no solution found ahead

if (row == N) return true;

all queens placed successfully

Output

. Q . . 

. . . Q 

Q . . . 

. . Q . 

Complexity Analysis

Time: O(N!) because each row tries all columns and backtracks on conflicts

Space: O(N^2) for the board storage and O(N) recursion stack for rows

vs Alternative: Brute force tries all board positions (O(2^(N^2))) which is much slower

Edge Cases

N=1 (smallest board)

Places single queen successfully without conflicts

DSA C

if (row == N) return true;

No solution (e.g., N=2 or N=3)

Backtracks fully and prints 'No solution found'

DSA C

return false; // no safe position found

Empty board initialization

Board starts with all zeros, no queens placed

DSA C

int board[N][N] = {0};

When to Use This Pattern

When asked to place items on a grid with constraints and no conflicts, use backtracking to try options row by row and backtrack on conflicts.

Common Mistakes

Mistake: Not checking diagonals for conflicts
Fix: Add checks for upper left and upper right diagonals in isSafe function

Mistake: Not backtracking properly by resetting board cell
Fix: Set board[row][col] back to 0 if recursion fails

Summary

Find a way to place N queens on an NxN board so none attack each other.

Use backtracking when you need to explore all safe placements with constraints.

Try placing queens row by row, backtrack when no safe spot is found in a row.