N-QUEENS – FULL EXAM-READY PACKAGE

(Backtracking Classic – 15–20 Marks Guaranteed!)

N-QUEENS – FULL EXAM-READY PACKAGE

N-QUEENS – FULL EXAM-READY PACKAGE
(Backtracking Classic – 15–20 Marks Guaranteed!)

N-QUEENS PROBLEM

Place N queens on N×N chessboard such that no two queens attack each other
→ No two queens in same row, column, or diagonal

4-QUEENS SOLUTION (MOST ASKED IN EXAM – Draw This!)

N = 4

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

Queen Positions: (1,2), (2,4), (3,1), (4,3)

BACKTRACKING STATE-SPACE TREE (Draw This – 8 Marks!)

                col=1
               /     \
          Q in row1   no solution
             ↓
            col=2
           /     \
      Q in row2   Q in row3 → conflict
         ↓
        col=3
       /     \
  Q in row4   Q in row2 → conflict
     ↓
    col=4 → SUCCESS!

FULL C CODE – N-QUEENS (100% Working + Print Board)

#include<stdio.h>
#define MAX 20

int board[MAX][MAX], n;

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

int isSafe(int row, int col) {
    // Check column
    for(int i=0; i<row; i++)
        if(board[i][col]) return 0;

    // Check upper-left diagonal
    for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)
        if(board[i][j]) return 0;

    // Check upper-right diagonal
    for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++)
        if(board[i][j]) return 0;

    return 1;
}

void nQueens(int row) {
    if(row == n) {
        printf("Solution found:\n");
        printBoard();
        return;
    }

    for(int col=0; col<n; col++) {
        if(isSafe(row, col)) {
            board[row][col] = 1;        // Place queen
            nQueens(row+1);             // Recurse
            board[row][col] = 0;        // Backtrack
        }
    }
}

int main() {
    printf("Enter N: ");
    scanf("%d", &n);

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            board[i][j] = 0;

    printf("N-Queens Solutions for N=%d:\n\n", n);
    nQueens(0);

    return 0;
}

Output for N=4:

Solution found:
. Q . . 
. . . Q 
Q . . . 
. . Q . 

Solution found:
. . Q . 
Q . . . 
. . . Q 
. Q . .

8-QUEENS ONE SOLUTION (Most Asked to Draw)

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

TIME COMPLEXITY

Worst case: O(N!)
With pruning: much faster in practice

EXAM QUICK CHEAT SHEET (Draw in 2 mins)

N	Number of Solutions
4	2
5	10
6	4
7	40
8	92

15-MARKS SOLVED QUESTION

Q: Solve 4-Queens problem using backtracking. Show state-space tree and one solution.

Answer:
1. Explain isSafe() checks → 4 marks
2. Draw 4×4 board with solution → 5 marks
3. Show partial state-space tree → 4 marks
4. Write code/recursive calls → 2 marks
→ 15/15

You now have bulletproof N-Queens – code + diagram + solution!

Want Branch and Bound for 0/1 Knapsack next?
Or Sudoku Solver, Rat in a Maze, or Hamiltonian Cycle?
Say the word — you're absolutely UNSTOPPABLE now!

Last updated: Nov 28, 2025

N-QUEENS – FULL EXAM-READY PACKAGE

(Backtracking Classic – 15–20 Marks Guaranteed!)