N Queens Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of N Queens Board Representation

What is the printed board state after placing 4 queens in the following positions on a 4x4 chessboard? Positions are given as (row, column): (0,1), (1,3), (2,0), (3,2). The board prints 'Q' for queen and '.' for empty cells.

DSA C

char board[4][4] = {
  {'.', 'Q', '.', '.'},
  {'.', '.', '.', 'Q'},
  {'Q', '.', '.', '.'},
  {'.', '.', 'Q', '.'}
};

for (int i = 0; i < 4; i++) {
  for (int j = 0; j < 4; j++) {
    printf("%c ", board[i][j]);
  }
  printf("\n");
}

A

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

B

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

C

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

D

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

💡 Hint

Visualize the board row by row, placing 'Q' at the given column index and '.' elsewhere.

The board is a 4x4 grid. Each row has exactly one queen at the specified column. The rest are empty cells represented by '.'. The output prints each row with spaces between characters and a newline after each row.

🧠 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 place queens row by row and count valid arrangements.

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

🔧 Debug

advanced

Identify the Bug in the Safety Check Function

Given the following C function to check if a queen can be safely placed at (row, col), which option correctly identifies the bug?

DSA C

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

A The function assumes 'N' is globally defined but it is not passed or defined inside the function.

B The function incorrectly checks the entire row instead of only columns before 'col'.

C The function does not check the column to the right of 'col', so queens can attack from there.

D The function misses checking the diagonal from top-right to bottom-left.

💡 Hint

Check variable scope and parameters used inside the function.

The function uses 'N' but it is not passed as a parameter or defined globally, causing a compilation error.

🚀 Application

advanced

Backtracking Steps Count for 4 Queens

How many times is the backtracking function called when solving the 4 Queens problem using the standard backtracking approach?

A 24

B 40

C 10

D 15

💡 Hint

Count all recursive calls including failed attempts.

The standard backtracking algorithm for 4 Queens calls the recursive function 24 times in total.

❓ Predict Output

expert

Output of N Queens Solution Count for N=5

What is the output of the following C code that counts the number of solutions for the 5 Queens problem?

DSA C

#include <stdio.h>
#define N 5

int count = 0;

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

void solveNQUtil(int board[][N], int col) {
  if (col == N) {
    count++;
    return;
  }
  for (int i = 0; i < N; i++) {
    if (isSafe(board, i, col)) {
      board[i][col] = 1;
      solveNQUtil(board, col + 1);
      board[i][col] = 0;
    }
  }
}

int main() {
  int board[N][N] = {0};
  solveNQUtil(board, 0);
  printf("%d\n", count);
  return 0;
}

A 8

B 10

C 5

D 12

💡 Hint

Recall the known number of solutions for 5 Queens problem.

The 5 Queens problem has exactly 10 distinct solutions, so the code prints 10.

Practice

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

easy

A. Place N queens on an NxN chessboard so that all queens attack each other

B. Find the shortest path for a queen to move across the board

C. Count the total number of queens on the board

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

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing N queens on an NxN chessboard so that no two queens threaten each other.

2. Step 2: Identify the correct goal

   This means no two queens share the same row, column, or diagonal.

3. Final Answer:

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

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember: Queens must not attack each other [OK]

Common Mistakes:

• Thinking queens can attack each other
• Confusing the problem with counting queens
• Ignoring diagonal attacks

2. Which of the following is the correct way to declare a 2D array for the chessboard in C for the N Queens Problem with size N?

easy

A. int board[];

B. int board[N][N];

C. int board[N];

D. int board(N,N);

Solution

1. Step 1: Recall C syntax for 2D arrays

   In C, a 2D array is declared as type name[size1][size2]; where both sizes are specified.

2. Step 2: Match the correct declaration

   int board[N][N]; uses int board[N][N]; which correctly declares a 2D array for the chessboard.

3. Final Answer:

   int board[N][N]; -> Option B

4. Quick Check:

   2D array syntax = int board[N][N]; [OK]

Hint: Use int board[N][N] for 2D arrays in C [OK]

Common Mistakes:

• Using 1D array for 2D board
• Incorrect syntax like int board(N,N);
• Not specifying both dimensions

3. What will be the output of the following code snippet for N=4 when printing the board after placing queens at positions (0,1), (1,3), (2,0), (3,2)?

int board[4][4] = {0};
board[0][1] = 1;
board[1][3] = 1;
board[2][0] = 1;
board[3][2] = 1;
for(int i=0; i<4; i++) {
  for(int j=0; j<4; j++) {
    printf("%d ", board[i][j]);
  }
  printf("\n");
}

medium

A. 0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1

B. 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

C. 0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

D. 0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0

Solution

1. Step 1: Place queens on the board as per given positions

   Set board[0][1], board[1][3], board[2][0], board[3][2] to 1; others remain 0.

2. Step 2: Print the board row-wise

   Row 0: 0 1 0 0 Row 1: 0 0 0 1 Row 2: 1 0 0 0 Row 3: 0 0 1 0

3. Final Answer:

   0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 -> Option C

4. Quick Check:

   Positions match output [OK]

Hint: Map queen positions to 1s in 2D array [OK]

Common Mistakes:

• Mixing row and column indices
• Printing without spaces or newlines
• Incorrect initialization of board

4. Identify the error in this C function snippet for checking if a queen can be placed at board[row][col]:

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

medium

A. The function assumes N is a global constant but it may not be

B. The function incorrectly checks columns beyond the current row

C. The function misses checking the lower diagonals

D. The function does not check the current row for queens

Solution

1. Step 1: Analyze the use of N in function parameter

   The function uses int board[][N] but N is not passed as a parameter or defined locally.

2. Step 2: Understand C array parameter rules

   In C, array sizes must be known or passed explicitly; assuming N as global can cause errors if not defined.

3. Final Answer:

   The function assumes N is a global constant but it may not be -> Option A

4. Quick Check:

   Array size N must be known [OK]

Hint: Always pass array size explicitly or define globally [OK]

Common Mistakes:

• Ignoring array size requirements in C
• Assuming N is always global
• Missing checks for diagonals

5. Given the backtracking approach to solve the N Queens Problem, which of the following best describes the role of recursion in the solution?

hard

A. Recursion tries to place queens row by row and backtracks when no safe position is found

B. Recursion counts the total number of queens placed on the board

C. Recursion moves queens randomly until all are placed

D. Recursion only checks if the board is full without placing queens

Solution

1. Step 1: Understand backtracking in N Queens

   Backtracking uses recursion to place queens one row at a time, checking safety.

2. Step 2: Identify recursion behavior

   If no safe position is found in a row, recursion backtracks to previous row to try other positions.

3. Final Answer:

   Recursion tries to place queens row by row and backtracks when no safe position is found -> Option A

4. Quick Check:

   Backtracking = recursive trial and error [OK]

Hint: Think recursion as trial and error with backtracking [OK]

Common Mistakes:

• Thinking recursion places queens randomly
• Confusing recursion with counting
• Ignoring backtracking step