N Queens Problem in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the chessboard with zeros.

DSA C++

int board[N][N] = {{0}};
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        board[i][j] = [1];
    }
}

Drag options to blanks, or click blank then click option'

A0

B1

C-1

DN

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 to initialize the board.

Using uninitialized values causing unpredictable behavior.

The chessboard should be initialized with 0 to indicate empty cells.

2fill in blank

medium

Complete the code to check if a queen can be placed safely in the given row and column.

DSA C++

bool isSafe(int board[N][N], int row, int col) {
    for (int i = 0; i < col; i++) {
        if (board[row][i] == [1]) {
            return false;
        }
    }
    return true;
}

Drag options to blanks, or click blank then click option'

A1

B0

C-1

DN

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of 1.

Checking the wrong direction or column.

We check if there is a queen (represented by 1) in the same row to the left.

3fill in blank

hard

Fix the error in the diagonal check for queen safety.

DSA C++

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] == [1]) {
        return false;
    }
}

Drag options to blanks, or click blank then click option'

A0

BN

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of 1 on the diagonal.

Incorrect loop conditions causing out-of-bounds errors.

Queens are marked with 1, so we check if any queen is on the upper left diagonal.

4fill in blank

hard

Fill both blanks to place a queen and then remove it during backtracking.

DSA C++

board[row][col] = [1];
if (solveNQUtil(board, col + 1)) {
    return true;
}
board[row][col] = [2]; // backtrack

Drag options to blanks, or click blank then click option'

A1

B0

C-1

DN

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 to place a queen.

Not resetting the cell to 0 during backtracking.

Place queen with 1 and remove it by setting back to 0 during backtracking.

5fill in blank

hard

Fill all three blanks to complete the recursive function call and return statement.

DSA C++

bool solveNQUtil(int board[N][N], int col) {
    if (col == [1]) {
        return [2];
    }
    for (int i = 0; i < [3]; i++) {
        if (isSafe(board, i, col)) {
            board[i][col] = 1;
            if (solveNQUtil(board, col + 1)) {
                return true;
            }
            board[i][col] = 0;
        }
    }
    return false;
}

Drag options to blanks, or click blank then click option'

AN

Btrue

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using false instead of true in base case return.

Incorrect loop range causing out-of-bounds errors.

When column equals N, all queens are placed, so return true. Loop runs from 0 to N-1 rows.

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