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.