N Queens Problem in DSA C++ - Build from Scratch

N Queens Problem

📖 Scenario: Imagine you are organizing a chess tournament and need to place n queens on an n x n chessboard. The challenge is to place the queens so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal.

🎯 Goal: You will build a program that finds one valid way to place n queens on the board safely. The program will print the board showing where the queens are placed.

📋 What You'll Learn

Create a 2D vector called board of size n x n initialized with zeros

Create an integer variable called n and set it to 4

Write a function isSafe that checks if placing a queen at a given row and column is safe

Write a recursive function solveNQueens that tries to place queens column by column

Print the board with 1 representing a queen and 0 representing an empty space

💡 Why This Matters

🌍 Real World

The N Queens problem is a classic example of constraint satisfaction problems used in artificial intelligence and puzzle solving.

💼 Career

Understanding backtracking algorithms and recursion is important for software engineers working on complex problem solving, optimization, and game development.

1

Create the chessboard

Create an integer variable called n and set it to 4. Then create a 2D vector called board of size n x n initialized with zeros.

DSA C++

int n = 4;
std::vector> board(n, std::vector(n, 0));
// Your code here

Hint

Use std::vector to create a 2D vector with all zeros.

2

Write the safety check function

Write a function called isSafe that takes parameters board, row, and col. It should return true if placing a queen at board[row][col] is safe (no other queens in the same row, upper diagonal, or lower diagonal), otherwise false.

DSA C++

#include 
#include 

int n = 4;
std::vector> board(n, std::vector(n, 0));

bool isSafe(const std::vector>& board, int row, int col) {
    // Your code here
}

int main() {
    return 0;
}

Hint

Check the row on the left, upper diagonal, and lower diagonal for any queen.

3

Write the recursive solver function

Write a recursive function called solveNQueens that takes board and col as parameters. It should try to place queens column by column using isSafe. Return true if all queens are placed, otherwise false.

DSA C++

#include 
#include 

int n = 4;
std::vector> board(n, std::vector(n, 0));

bool isSafe(const std::vector>& board, int row, int col) {
    for (int i = 0; i = 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) return false;
    }
    for (int i = row, j = col; i = 0; i++, j--) {
        if (board[i][j] == 1) return false;
    }
    return true;
}

bool solveNQueens(std::vector>& board, int col) {
    // Your code here
}

int main() {
    return 0;
}

Hint

Try placing a queen in each row of the current column. Use recursion to place queens in the next columns.

4

Print the board with queens placed

In main, call solveNQueens(board, 0). Then print the board so that each row is on a new line and each cell is separated by a space. Use 1 to show a queen and 0 for empty cells.

DSA C++

#include 
#include 

int n = 4;
std::vector> board(n, std::vector(n, 0));

bool isSafe(const std::vector>& board, int row, int col) {
    for (int i = 0; i = 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1) return false;
    }
    for (int i = row, j = col; i = 0; i++, j--) {
        if (board[i][j] == 1) return false;
    }
    return true;
}

bool solveNQueens(std::vector>& board, int col) {
    if (col >= n) return true;
    for (int row = 0; row < n; row++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;
            if (solveNQueens(board, col + 1)) return true;
            board[row][col] = 0;
        }
    }
    return false;
}

int main() {
    solveNQueens(board, 0);
    // Your code here
}

Hint

Call solveNQueens(board, 0) first. Then use nested loops to print each row and column of the board.

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