N Queens Problem in DSA C#

Mental Model

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

Analogy: Imagine placing N guards in a square garden so that none can see each other along rows, columns, or diagonals.

Board 4x4 empty:
. . . .
. . . .
. . . .
. . . .

Dry Run Walkthrough

Input: board size N=4

Goal: Place 4 queens on the 4x4 board so no two queens threaten each other

Step 1: Place queen at row 0, column 1

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

Why: Start placing first queen in first row at column 1

Step 2: Place queen at row 1, column 3

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

Why: Place second queen in second row avoiding attacks from first queen

Step 3: Place queen at row 2, column 0

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

Why: Find safe spot in third row avoiding attacks

Step 4: Place queen at row 3, column 2

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

Why: Place fourth queen safely, solution found

Result:

Final board:
. Q . .
. . . Q
Q . . .
. . Q .

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class NQueens {
    static void Main() {
        int n = 4;
        var solutions = SolveNQueens(n);
        foreach (var board in solutions) {
            PrintBoard(board);
            Console.WriteLine();
        }
    }

    static List<List<string>> SolveNQueens(int n) {
        var results = new List<List<string>>();
        var board = new char[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                board[i, j] = '.';
        Backtrack(0, board, results, n);
        return results;
    }

    static void Backtrack(int row, char[,] board, List<List<string>> results, int n) {
        if (row == n) {
            var copy = new List<string>();
            for (int i = 0; i < n; i++) {
                var rowStr = new char[n];
                for (int j = 0; j < n; j++) {
                    rowStr[j] = board[i, j];
                }
                copy.Add(new string(rowStr));
            }
            results.Add(copy);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (IsSafe(row, col, board, n)) {
                board[row, col] = 'Q';
                Backtrack(row + 1, board, results, n);
                board[row, col] = '.'; // backtrack
            }
        }
    }

    static bool IsSafe(int row, int col, char[,] board, int n) {
        // Check column
        for (int i = 0; i < row; i++) {
            if (board[i, col] == 'Q') return false;
        }
        // Check upper left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i, j] == 'Q') return false;
        }
        // Check upper right diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i, j] == 'Q') return false;
        }
        return true;
    }

    static void PrintBoard(List<string> board) {
        foreach (var row in board) {
            Console.WriteLine(row);
        }
    }
}

if (row == n) { ... return; }

stop recursion when all rows have queens placed

for (int col = 0; col < n; col++) { if (IsSafe(row, col, board, n)) { board[row, col] = 'Q'; Backtrack(row + 1, board, results, n); board[row, col] = '.'; } }

try placing queen in each column of current row, recurse if safe, then backtrack

IsSafe checks column and diagonals above current row

ensure no queen attacks current position

Output

.Q..

...Q

Q...

..Q.



..Q.

Q...

...Q

.Q..

Complexity Analysis

Time: O(N!) because we try to place queens row by row and prune invalid positions early

Space: O(N^2) for the board and recursion stack up to N levels

vs Alternative: Brute force tries all board configurations (O(2^(N^2))) which is much slower

Edge Cases

N=1 (smallest board)

One queen placed trivially, solution is the single cell

DSA C#

if (row == n) { ... return; }

N=2 or N=3 (no solutions)

Backtracking finds no valid placements, returns empty list

DSA C#

if (IsSafe(row, col, board, n)) { ... }

Larger N (e.g. N=8)

Algorithm finds all valid solutions using backtracking efficiently

DSA C#

Backtrack recursion with pruning in IsSafe

When to Use This Pattern

When asked to place items on a grid without conflicts in rows, columns, and diagonals, use backtracking with safety checks to explore valid configurations.

Common Mistakes

Mistake: Not checking diagonals when verifying safe placement
Fix: Add checks for both upper left and upper right diagonals in IsSafe

Mistake: Not backtracking properly by resetting board cell after recursion
Fix: Reset board[row, col] to '.' after recursive call returns

Summary

Find all ways to place N queens on an NxN board so none attack each other.

Use backtracking when you need to explore all valid configurations with constraints.

The key is to place queens row by row and check columns and diagonals for safety before placing.

Practice

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

easy

A. Place N queens on an NxN board so that no two queens attack each other

B. Place N queens on an NxN board so that all queens attack each other

C. Place N queens on an NxN board in a single row

D. Place N queens on an NxN board in a single column

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 board so that no two queens attack each other -> Option A

4. Quick Check:

   Goal = No two queens attack each other [OK]

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

Common Mistakes:

• Thinking queens can share rows or columns
• Ignoring diagonal attacks
• Confusing with placing queens in one line

2. Which of the following C# code snippets correctly declares a 2D array to represent an 8x8 chessboard for the N Queens Problem?

easy

A. int[,] board = new int[8,8];

B. int[][] board = new int[8];

C. int board[8][8];

D. int board = new int[8,8];

Solution

1. Step 1: Identify correct 2D array declaration in C#

   In C#, a 2D array is declared as int[,] board = new int[8,8];.

2. Step 2: Check other options for syntax errors

   int[][] board = new int[8]; declares a jagged array but misses initialization of inner arrays. int board[8][8]; is invalid syntax in C#. int board = new int[8,8]; tries to assign an array to an int variable.

3. Final Answer:

   int[,] board = new int[8,8]; -> Option A

4. Quick Check:

   Correct 2D array syntax = int[,] board = new int[8,8]; [OK]

Hint: Use int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged arrays without initializing inner arrays
• Using C++ style array declarations
• Assigning arrays to single int variables

3. Consider the following C# code snippet for checking if a queen can be placed at row 1, column 2 on a 4x4 board:

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

int[,] board = new int[4,4];
board[0, 1] = 1;
bool result = IsSafe(board, 1, 2);
Console.WriteLine(result);

What will be the output?

medium

A. true

B. Compile-time error

C. false

D. Runtime exception

Solution

1. Step 1: Analyze the board state and IsSafe checks

   The board has a queen at (0,1). We check if placing at (1,2) is safe. The function checks left row, upper-left diagonal, and lower-left diagonal.

2. Step 2: Check conflicts for position (1,2)

   Left row check: no queen at (1,0) or (1,1). Upper-left diagonal: (0,1) has a queen, so returns false.

3. Final Answer:

   false -> Option C

4. Quick Check:

   Queen at (0,1) blocks (1,2) = false [OK]

Hint: Check diagonals carefully for conflicts [OK]

Common Mistakes:

• Ignoring diagonal checks
• Assuming no conflict if row is clear
• Misreading array indices

4. The following C# code attempts to solve the N Queens Problem but has a bug. What is the bug?

bool SolveNQueens(int[,] board, int col) {
    if (col >= board.GetLength(0)) return true;
    for (int i = 0; i < board.GetLength(0); i++) {
        if (IsSafe(board, i, col)) {
            board[i, col] = 1;
            if (SolveNQueens(board, col + 1)) return true;
            board[i, col] = 0;
        }
    }
    return false;
}

// IsSafe method is correct

medium

A. The function does not backtrack properly

B. No bug; code works correctly

C. The board array is not initialized

D. The base case should check row instead of column

Solution

1. Step 1: Review the recursive backtracking logic

   The function tries to place a queen in each row of the current column, checks safety, places queen, and recurses to next column.

2. Step 2: Verify base case and backtracking

   Base case returns true when all columns are processed. Backtracking resets board[i, col] to 0 if recursion fails. This is correct.

3. Final Answer:

   No bug; code works correctly -> Option B

4. Quick Check:

   Backtracking logic and base case are correct [OK]

Hint: Check base case and backtracking steps carefully [OK]

Common Mistakes:

• Confusing row and column in base case
• Forgetting to reset board on backtrack
• Assuming uninitialized board causes error

5. You want to modify the N Queens solver to count all possible solutions for N=4 instead of stopping at the first. Which change should you make to the recursive method?

hard

A. Add a global boolean flag to stop after first solution

B. Remove the IsSafe check to speed up counting

C. Change the board size to 5x5

D. Replace the return type with int and sum all recursive calls instead of returning on first true

Solution

1. Step 1: Understand current behavior

   The current solver returns true on finding the first solution, stopping further search.

2. Step 2: Modify to count all solutions

   Change return type to int, accumulate counts from recursive calls, and do not return early. This counts all valid placements.

3. Final Answer:

   Replace the return type with int and sum all recursive calls instead of returning on first true -> Option D

4. Quick Check:

   Counting solutions = sum recursive counts [OK]

Hint: Sum all recursive results to count solutions [OK]

Common Mistakes:

• Stopping at first solution
• Changing board size unnecessarily
• Removing safety checks causing wrong counts