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 appear.

Analogy: Imagine seating N guests at N tables in a row, where no guest can sit where they can see another guest directly in front, diagonally left, or diagonally right. You try seating one guest at a time and move back if a conflict arises.

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

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

Dry Run Walkthrough

Input: N=4, place 4 queens on 4x4 board

Goal: Find one valid arrangement where 4 queens do not attack each other

Step 1: Place queen at row 0, column 1

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

Why: Start placing queen in first row at first safe column

Step 2: Place queen at row 1, column 3

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

Why: Next row, find safe column avoiding attacks

Step 3: Try placing queen at row 2, column 0 - conflict found, backtrack

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

Why: Column 0 conflicts diagonally with queen at row 1, column 3

Step 4: Place queen at row 2, column 2

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

Why: Found safe column in row 2

Step 5: Try placing queen at row 3, column 0 - conflict, backtrack

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

Why: Column 0 conflicts diagonally with queen at row 2, column 2

Step 6: Try placing queen at row 3, column 1 - conflict, backtrack

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

Why: Column 1 conflicts vertically with queen at row 0, column 1

Step 7: Try placing queen at row 3, column 3 - conflict, backtrack

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

Why: Column 3 conflicts vertically with queen at row 1, column 3

Step 8: Backtrack to row 2, move queen to column 0

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

Why: Try next safe position in row 2 after failing row 3

Step 9: Place queen at row 3, column 2

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

Why: Found safe position for last queen

Result:

. Q . .
. . . Q
Q . . .
. . Q .
One valid solution found

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

bool isSafe(int row, int col, const vector<string>& board, int n) {
    // Check column for another queen
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    // Check upper left diagonal
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    // Check upper right diagonal
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

bool solveNQueens(int row, vector<string>& board, int n) {
    if (row == n) return true; // All queens placed

    for (int col = 0; col < n; col++) {
        if (isSafe(row, col, board, n)) {
            board[row][col] = 'Q'; // Place queen
            if (solveNQueens(row + 1, board, n)) return true; // Recurse
            board[row][col] = '.'; // Backtrack
        }
    }
    return false; // No safe position found
}

int main() {
    int n = 4;
    vector<string> board(n, string(n, '.'));
    if (solveNQueens(0, board, n)) {
        for (const string& row : board) {
            cout << row << "\n";
        }
    } else {
        cout << "No solution found\n";
    }
    return 0;
}

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

Try each column in current row to find safe spot

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

Check if placing queen here causes no attacks

board[row][col] = 'Q';

Place queen at safe position

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

Recurse to next row to place next queen

board[row][col] = '.';

Backtrack by removing queen if no solution found ahead

Output

.Q..

...Q

Q...

..Q.

Complexity Analysis

Time: O(N!) because each row tries N columns and backtracks, pruning reduces actual tries but worst case is factorial

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

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

Edge Cases

N=1 (smallest board)

Places single queen immediately, returns solution

DSA C++

if (row == n) return true;

N=2 or N=3 (no solutions exist)

Backtracks fully and returns no solution

DSA C++

return false; // No safe position found

Empty board initialization

Board filled with '.' to represent empty cells

DSA C++

vector<string> board(n, string(n, '.'));

When to Use This Pattern

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

Common Mistakes

Mistake: Not checking diagonals when verifying safe positions
Fix: Add checks for both upper left and upper right diagonals in isSafe function

Mistake: Not backtracking properly by resetting board cell after failed recursion
Fix: Reset board[row][col] = '.' after recursive call returns false

Summary

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

Use when you need to explore all safe placements with constraints and backtrack on conflicts.

Try placing queens row by row, checking columns and diagonals, and backtrack when stuck.

Practice

1. What is the main goal of the N Queens Problem in chess?

easy

A. Place N queens on an NxN board in the same column

B. Place N queens on an NxN board so that all queens attack each other

C. Place N queens on an NxN board in the same row

D. Place N queens on an NxN board so that no two queens attack each other

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing queens so that none can attack another, meaning no two queens share the same row, column, or diagonal.

2. Step 2: Analyze the options

   Place N queens on an NxN board so that no two queens attack each other correctly states the goal. Options B, C, and D contradict the problem's requirement by allowing attacks or placing queens in the same row or column.

3. Final Answer:

   Place N queens on an NxN board so that no two queens attack each other -> Option D

4. Quick Check:

   Goal = No two queens attack each other [OK]

Hint: Remember: Queens must not threaten each other on board [OK]

Common Mistakes:

• Thinking queens can share rows or columns
• Confusing attacking with protecting
• Ignoring diagonal attacks

2. Which of the following C++ function signatures is correct for a recursive function solving the N Queens Problem?

easy

A. void solveNQueens(vector<int> row, int positions)

B. bool solveNQueens(int row, vector<int>& positions)

C. int solveNQueens(int row, int positions[])

D. bool solveNQueens(int positions, vector<int> row)

Solution

1. Step 1: Identify correct parameter types for recursion

   The function should take the current row (int) and a reference to a vector holding queen positions to track placements.

2. Step 2: Check each option's signature

   bool solveNQueens(int row, vector<int>& positions) uses int and vector<int>& correctly. void solveNQueens(vector<int> row, int positions) swaps types incorrectly. int solveNQueens(int row, int positions[]) uses array but lacks reference semantics. bool solveNQueens(int positions, vector<int> row) swaps parameter order and types incorrectly.

3. Final Answer:

   bool solveNQueens(int row, vector<int>& positions) -> Option B

4. Quick Check:

   Correct signature uses int and vector reference [OK]

Hint: Recursive function needs current row and positions by reference [OK]

Common Mistakes:

• Passing vector by value causing performance issues
• Swapping parameter order
• Using wrong data types for parameters

3. What will be the output of the following code snippet for N=4?

void printBoard(const vector<int>& positions) {
  for (int row = 0; row < positions.size(); ++row) {
    for (int col = 0; col < positions.size(); ++col) {
      if (positions[row] == col) std::cout << "Q ";
      else std::cout << ". ";
    }
    std::cout << std::endl;
  }
}

int main() {
  vector<int> positions = {1, 3, 0, 2};
  printBoard(positions);
  return 0;
}

medium

A. . . Q .
Q . . .
. . . Q
. Q . .

B. Q . . .
. Q . .
. . Q .
. . . Q

C. . Q . .
. . . Q
Q . . .
. . Q .

D. . . . Q
Q . . .
. Q . .
. . Q .

Solution

1. Step 1: Understand positions vector meaning

   Each index is a row; value at index is the column where queen is placed. For positions = {1,3,0,2}, queens are at (0,1), (1,3), (2,0), (3,2).

2. Step 2: Visualize the board

   Row 0: Q at col 1 -> . Q . . Row 1: Q at col 3 -> . . . Q Row 2: Q at col 0 -> Q . . . Row 3: Q at col 2 -> . . Q .

3. Final Answer:

   . Q . . . . . Q Q . . . . . Q . -> Option C

4. Quick Check:

   Positions map to board rows and columns correctly [OK]

Hint: Positions vector index = row, value = queen column [OK]

Common Mistakes:

• Mixing row and column indices
• Printing Q in wrong columns
• Ignoring zero-based indexing

4. Identify the bug in this code snippet for checking if a queen can be placed safely:

bool isSafe(int row, int col, const vector<int>& positions) {
  for (int i = 0; i < row; ++i) {
    if (positions[i] == col || abs(positions[i] - col) == abs(i - row))
      return false;
  }
  return true;
}

medium

A. No bug; the function correctly checks safety

B. The diagonal check condition is incorrect

C. The loop should run until i <= row instead of i < row

D. The function does not check for column conflicts

Solution

1. Step 1: Analyze loop and conditions

   The loop checks all rows before current row. It returns false if any queen shares the same column or diagonal.

2. Step 2: Verify correctness of conditions

   positions[i] == col checks column conflict. abs(positions[i] - col) == abs(i - row) checks diagonal conflict correctly.

3. Final Answer:

   No bug; the function correctly checks safety -> Option A

4. Quick Check:

   Column and diagonal checks are correct [OK]

Hint: Check columns and diagonals with absolute difference [OK]

Common Mistakes:

• Loop running one step too far
• Incorrect diagonal condition
• Missing column conflict check

5. Given the N Queens Problem, which approach best improves performance for large N by reducing unnecessary checks?

hard

A. Use bitmasks to track columns and diagonals instead of arrays

B. Use nested loops to check every cell repeatedly

C. Store all board states in a list and check later

D. Place queens randomly and backtrack only if conflict

Solution

1. Step 1: Understand performance bottlenecks

   Checking columns and diagonals repeatedly slows down backtracking for large N.

2. Step 2: Evaluate optimization techniques

   Using bitmasks allows O(1) checks for columns and diagonals, reducing overhead significantly compared to arrays or repeated loops.

3. Step 3: Analyze other options

   Nested loops and storing all states increase time and memory. Random placement is inefficient and unreliable.

4. Final Answer:

   Use bitmasks to track columns and diagonals instead of arrays -> Option A

5. Quick Check:

   Bitmask optimization = faster checks [OK]

Hint: Bitmasks speed up column and diagonal checks [OK]

Common Mistakes:

• Using slow nested loops for checks
• Storing all states wastes memory
• Random placement lacks systematic pruning