N Queens Problem in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of partial N Queens board placement

What is the printed board state after placing queens at positions (row, col): (0, 1), (1, 3) on a 4x4 board?

DSA C++

char board[4][4] = {{'.', '.', '.', '.'}, {'.', '.', '.', '.'}, {'.', '.', '.', '.'}, {'.', '.', '.', '.'}};
board[0][1] = 'Q';
board[1][3] = 'Q';
for(int i=0; i<4; i++) {
  for(int j=0; j<4; j++) {
    std::cout << board[i][j] << ' ';
  }
  std::cout << std::endl;
}

A [". Q . . ", ". Q . . ", ". . . . ", ". . . . "]

B ["Q . . . ", ". . Q . ", ". . . . ", ". . . . "]

C [". . Q . ", ". Q . . ", ". . . . ", ". . . . "]

D [". Q . . ", ". . . Q ", ". . . . ", ". . . . "]

💡 Hint

Remember the queen positions are set at (0,1) and (1,3).

The board is a 4x4 grid with '.' for empty and 'Q' for queen. Only positions (0,1) and (1,3) have queens.

🧠 Conceptual

intermediate

Number of solutions for 4 Queens

How many distinct solutions exist for the classic 4 Queens problem on a 4x4 chessboard?

A 1

B 4

C 2

D 8

💡 Hint

Try to visualize or recall the known count of solutions for 4 queens.

The 4 Queens problem has exactly 2 distinct solutions where no two queens attack each other.

🔧 Debug

advanced

Identify the error in this N Queens backtracking code snippet

What error will this code cause when trying to place queens on a 4x4 board? int board[4][4] = {0}; for(int i=0; i<=4; i++) { for(int j=0; j<=4; j++) { board[i][j] = 0; } }

A Runtime error: Array index out of bounds

B No error, code runs fine

C Compilation error: missing semicolon

D Logical error: board not initialized

💡 Hint

Check the loop conditions and array size carefully.

The loops use <=4 which tries to access index 4, but valid indices are 0 to 3, causing out of bounds error.

🚀 Application

advanced

Count solutions for 5 Queens using backtracking

What is the total number of distinct solutions for the 5 Queens problem on a 5x5 board?

A 10

B 5

C 8

D 12

💡 Hint

The number of solutions grows but is known for small boards.

The 5 Queens problem has 10 solutions.

❓ Predict Output

expert

Output of recursive call count in N Queens solver

Given this recursive function snippet counting calls for N=4, what is the final value of 'count' after solving all placements? int count = 0; void solve(int row, int n) { if(row == n) { count++; return; } for(int col=0; col

A 4

B 2

C 1

D 8

💡 Hint

The count increments only when a full valid placement is found.

For N=4, the total valid solutions found by backtracking is 2, so count will be 2.

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