Backtracking VTU BCSL40A

N-Queens Problem

The N-Queens problem uses backtracking to place N queens on an N×N chessboard so that no two queens attack each other.

Time Complexity

O(N!)

Space Complexity

O(N)

Paradigm

Backtracking

Introduction

The N-Queens Problem is a classic backtracking problem: place N queens on an N×N chessboard such that no two queens threaten each other. A queen attacks any piece in the same row, column, or diagonal. For N=8, there are 92 distinct solutions. The problem elegantly demonstrates the backtracking paradigm — try a position, if it's safe proceed, else backtrack and try the next position.

Problem Statement

Given an N×N chessboard and N queens, find all arrangements of the queens such that no two queens share the same row, column, or diagonal.

Real World Applications

→ Constraint satisfaction problems in AI
→ VLSI circuit design — placing components without interference
→ Scheduling problems with conflict constraints
→ Parallel process allocation
→ Solving puzzle games

Algorithm Explanation

The iterative backtracking approach places queens row by row. col[r] stores the column of the queen in row r. Starting at row 1, column 0: increment col[r], check if placement is safe using place(r) — no two queens in same column or diagonal. If safe and r==n, a solution is found. If safe and r<n, move to next row. If unsafe or col[r]>n, backtrack to previous row.

Step-by-Step Procedure

1 Initialize col[1] = 0. Set r = 1.
2 Increment col[r] by 1.
3 If col[r] > n: backtrack — set r = r-1 and go to step 2.
4 If col[r] ≤ n and place(r) is safe:
5 If r == n: count solution, print board.
6 Else: move to next row r = r+1, set col[r] = 0.
7 If not safe, go back to step 2.
8 Repeat until r becomes 0 (all solutions found).

Complete C Program

Nqueen.c

View on GitHub ↗

#include<stdlib.h>
#include<stdio.h>

int col[30], count = 0;

int place(int r) {
    int i;
    for(i = 1; i < r; i++) {
        if(col[i] == col[r] || abs(i - r) == abs(col[i] - col[r]))
            return 0;
    }
    return 1;
}

void Nqueen(int n) {
    int r = 1, i, j;
    col[r] = 0;
    while(r != 0) {
        col[r] = col[r] + 1;
        while(col[r] <= n && !place(r))
            col[r] = col[r] + 1;
        if(col[r] <= n) {
            if(r == n) {
                count++;
                printf("Solution #%d\n", count);
                for(i = 1; i <= n; i++) {
                    for(j = 1; j <= n; j++) {
                        if(j == col[i]) printf("Q ");
                        else printf(". ");
                    }
                    printf("\n");
                }
                printf("\n");
            } else {
                r++;
                col[r] = 0;
            }
        } else {
            r--;
        }
    }
}

int main() {
    int n;
    printf("Enter the Number of Queens: ");
    scanf("%d", &n);
    Nqueen(n);
    printf("Total Solutions: %d\n", count);
    return 0;
}

Sample Input & Output

Sample Input

Expected Output

Solution #1
. Q . .
. . . Q
Q . . .
. . Q .

Solution #2
. . Q .
Q . . .
. . . Q
. Q . .

Total Solutions: 2

Dry Run / Trace

N=4. Try row 1:
col[1]=1: safe. Row 2:
col[2]=1: same col as row1, fail. col[2]=2: diagonal (|1-2|=|1-2|=1), fail. col[2]=3: safe. Row 3:
col[3]=1: diagonal with row2 (|2-3|=|3-1|=2, no; |1-3|=|1-1|=0, no). col[3]=1: col[3]=col[1]=1, fail. col[3]=2: diagonal with row1 (|1-3|=2, |1-2|=1, not equal), col 2 conflicts with row2 col 3? |2-3|=1=|2-3|=1, diagonal, fail. col[3]=3: conflicts with row2. col[3]=4: ... Eventually Solution #1: (2,4,1,3).

Advantages & Disadvantages

✓ Advantages

+ Demonstrates pure backtracking elegantly
+ Finds all solutions, not just one
+ O(N) space for column array
+ Iterative version avoids recursion stack overflow

✗ Disadvantages

− O(N!) time — exponential growth
− Not practical for large N (N > 20 takes very long)
− All solutions must be found sequentially

Viva Questions & Answers

Q1. How does the place() function check if a queen placement is safe?

It checks two conditions for all previous queens: (1) col[i] == col[r] — same column; (2) abs(i-r) == abs(col[i]-col[r]) — same diagonal.

Q2. How many solutions are there for the 8-Queens problem?

92 solutions.

Q3. Why is row conflict not checked in the place() function?

The algorithm places exactly one queen per row by design (col[r] is the column for row r), so row conflicts are impossible.

Q4. What is the difference between implicit and explicit constraints in N-Queens?

Explicit: no two queens in same row, column, or diagonal. Implicit: each queen must be on the board (1 ≤ col[r] ≤ n).

Q5. Can N-Queens be solved without backtracking?

Yes, there are constructive O(n) solutions based on mathematical formulas for placing queens. But backtracking finds all solutions and is the standard algorithmic approach.