N Queens Problem in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the N Queens Problem?

To place N queens on an N×N chessboard so that no two queens attack each other. This means no two queens share the same row, column, or diagonal.

beginner

Which data structure is commonly used to represent the chessboard in the N Queens Problem?

A 2D array or vector of size N×N, where each cell can hold a value indicating if a queen is placed there or not.

intermediate

How do we check if placing a queen at a given position is safe?

We check three directions: the same column above, the upper left diagonal, and the upper right diagonal for any existing queens.

beginner

What algorithmic technique is primarily used to solve the N Queens Problem?

Backtracking, which tries placing queens row by row and backtracks if a conflict is found.

intermediate

Why is backtracking efficient for the N Queens Problem compared to brute force?

Because it stops exploring a path as soon as it finds a conflict, avoiding unnecessary checks and reducing the search space.

In the N Queens Problem, what does a 'safe' position mean?

A No other queen is in the same row, column, or diagonal

B No other queen is in the same row only

C No other queen is in the same column only

D No other queen is in the same diagonal only

A safe position means no queen attacks another, so no queens share the same row, column, or diagonal.

Which of these is NOT a direction checked when placing a queen safely?

A Same column above

B Lower left diagonal

C Upper right diagonal

D Upper left diagonal

We only check above the current row because queens are placed row by row from top to bottom.

What is the time complexity of the N Queens Problem using backtracking in the worst case?

A O(N!)

B O(N^2)

C O(2^N)

D O(N)

Backtracking explores permutations of queen placements, leading to factorial time complexity in the worst case.

Which of these is a key step in backtracking for N Queens?

A Place all queens at once

B Place queens only in the first column

C Place queens randomly

D Place a queen and move to next row if safe

Backtracking places queens row by row, moving forward only if the position is safe.

What happens when backtracking finds no safe position in a row?

A It stops the program

B It restarts from the first row

C It removes the last placed queen and tries a new position

D It places a queen anyway

Backtracking removes the last queen placed and tries alternative positions to find a solution.

Explain how backtracking solves the N Queens Problem step-by-step.

Think about placing queens row by row and undoing moves when stuck.

Describe how to check if a queen can be safely placed on the board.

Remember queens attack vertically and diagonally.

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