N Queens Problem in DSA Java

Mental Model

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

Analogy: Imagine placing N friends on N tables arranged in a square room so that no friend can see another directly in the same row, column, or diagonal.

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

. = empty cell, Q = queen placed

Dry Run Walkthrough

Input: board size N=4

Goal: Place 4 queens on a 4x4 board so none attack each other

Step 1: Place queen at row 0, column 1

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

Why: Start placing queen in first row at column 1 to try a safe spot

Step 2: Place queen at row 1, column 3

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

Why: Next row, place queen where it is not attacked by previous queen

Step 3: Try placing queen at row 2, column 0 - safe, place it

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

Why: Find safe column in row 2 where no queen attacks

Step 4: Try placing queen at row 3, column 2 - safe, place it

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

Why: Last row, place queen safely to complete solution

Result:

. Q . .
. . . Q
Q . . .
. . Q .
Solution found with all queens safe

Annotated Code

DSA Java

public class NQueens {
    private int size;
    private char[][] board;

    public NQueens(int n) {
        size = n;
        board = new char[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                board[i][j] = '.';
            }
        }
    }

    private boolean isSafe(int row, int col) {
        // Check column above
        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 < size; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }

    private boolean solve(int row) {
        if (row == size) return true; // All queens placed

        for (int col = 0; col < size; col++) {
            if (isSafe(row, col)) {
                board[row][col] = 'Q'; // Place queen
                if (solve(row + 1)) return true; // Recurse to next row
                board[row][col] = '.'; // Backtrack
            }
        }
        return false; // No safe position found
    }

    public void solveAndPrint() {
        if (solve(0)) {
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("No solution found");
        }
    }

    public static void main(String[] args) {
        NQueens nq = new NQueens(4);
        nq.solveAndPrint();
    }
}

for (int col = 0; col < size; col++) {

try each column in current row to place queen

if (isSafe(row, col)) {

check if placing queen here is safe

board[row][col] = 'Q';

place queen at safe position

if (solve(row + 1)) return true;

recurse to next row to place next queen

board[row][col] = '.';

backtrack by removing queen if dead end

if (row == size) return true;

all queens placed successfully

Output

. Q . . 

. . . Q 

Q . . . 

. . Q . 

Complexity Analysis

Time: O(N!) because each row tries all columns and backtracks on conflicts

Space: O(N^2) for the board storage and O(N) recursion stack for rows

vs Alternative: Brute force tries all placements (N^N), backtracking prunes invalid paths early reducing search

Edge Cases

N=1 board

Places single queen immediately, solution is trivial

DSA Java

if (row == size) return true;

No solution board like N=2 or N=3

Backtracking tries all positions and returns no solution

DSA Java

return false; // No safe position found

Empty board initialization

Board filled with '.' to mark empty cells

DSA Java

board[i][j] = '.';

When to Use This Pattern

When asked to place items on a grid with constraints that no two items attack each other, use backtracking to try positions row by row and backtrack on conflicts.

Common Mistakes

Mistake: Not checking all three directions (column, left diagonal, right diagonal) for queen attacks
Fix: Add checks for column and both diagonals above current row before placing queen

Mistake: Not backtracking properly by removing queen after failed recursive call
Fix: Reset board cell to '.' after recursive call returns false

Summary

Finds a way to place N queens on an NxN board so none attack each other.

Use when you need to arrange items with mutual exclusion constraints on rows, columns, and diagonals.

Try placing queens row by row, backtrack immediately when a conflict is found to avoid useless work.

Practice

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

easy

A. Place queens only on the diagonal cells of the board

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

C. Count the total number of queens on the board

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

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 B

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember: no two queens can share row, column, or diagonal [OK]

Common Mistakes:

• Thinking queens can share the same row or column
• Confusing the problem with counting queens
• Assuming queens only attack diagonally

2. Which of the following Java method signatures is correct for a recursive function solving the N Queens Problem?

easy

A. static int solveNQueens(int[][] board, int n, int row)

B. public void solveNQueens(int n, int row, int[][] board)

C. public static boolean solveNQueens(int row, int n, int[][] board)

D. boolean solveNQueens(int n, int[][] board, int row)

Solution

1. Step 1: Check method signature correctness

   The recursive method should return a boolean indicating success/failure, take current row, board size, and board state.

2. Step 2: Validate parameter order and modifiers

   public static boolean solveNQueens(int row, int n, int[][] board) matches this: public static boolean solveNQueens(int row, int n, int[][] board)

3. Final Answer:

   public static boolean solveNQueens(int row, int n, int[][] board) -> Option C

4. Quick Check:

   Correct signature = public static boolean solveNQueens(int row, int n, int[][] board) [OK]

Hint: Recursive method returns boolean and takes current row first [OK]

Common Mistakes:

• Wrong return type (e.g., void instead of boolean)
• Incorrect parameter order
• Missing static keyword if required

3. What will be the output of the following Java code snippet for N=4?

public class NQueensTest {
    static int count = 0;
    public static void main(String[] args) {
        int n = 4;
        int[][] board = new int[n][n];
        solveNQueens(0, n, board);
        System.out.println(count);
    }
    static boolean solveNQueens(int row, int n, int[][] board) {
        if (row == n) {
            count++;
            return true;
        }
        boolean res = false;
        for (int col = 0; col < n; col++) {
            if (isSafe(row, col, board, n)) {
                board[row][col] = 1;
                res = solveNQueens(row + 1, n, board) || res;
                board[row][col] = 0;
            }
        }
        return res;
    }
    static boolean isSafe(int row, int col, int[][] board, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 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 >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) return false;
        }
        return true;
    }
}

medium

A. 2

B. 4

C. 1

D. 0

Solution

1. Step 1: Understand the code logic

   The code counts all valid solutions for 4 queens on a 4x4 board using backtracking.

2. Step 2: Recall known result for 4 queens

   It is a well-known fact that there are 2 valid solutions for the 4 queens problem.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Number of solutions for N=4 = 2 [OK]

Hint: Remember: 4 queens have exactly 2 solutions [OK]

Common Mistakes:

• Assuming only 1 solution exists
• Confusing number of solutions with board size
• Ignoring backtracking resets

4. Identify the bug in this snippet of the N Queens solver:

static boolean isSafe(int row, int col, int[][] board, int n) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 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 >= 0 && j <= n; i--, j++) {
        if (board[i][j] == 1) return false;
    }
    return true;
}

medium

A. It incorrectly checks columns beyond the board size

B. It does not check the left diagonal upwards

C. It does not check the current row for other queens

D. It misses checking the lower diagonals for threats

Solution

1. Step 1: Analyze the safety checks

   The column check and upper-left diagonal are correct.

2. Step 2: Identify the bug in upper-right diagonal

   The loop condition 'i >= 0 && j <= n' allows j to reach n (e.g., when col = n-1, after first iteration j = n), causing ArrayIndexOutOfBoundsException on board[i][n].

3. Final Answer:

   It incorrectly checks columns beyond the board size -> Option A

4. Quick Check:

   Upper-right diagonal: j <= n causes out-of-bounds [OK]

Hint: Always verify loop bounds in diagonal checks to avoid index errors [OK]

Common Mistakes:

• Forgetting off-by-one errors in diagonal loop conditions
• Overlooking array bounds in upper-right diagonal traversal
• Confusing upper vs lower diagonal checks

5. You want to modify the N Queens solver to print all distinct solutions for N=4. Which approach is best to achieve this?

hard

A. Stop recursion as soon as the first solution is found to save time

B. Place all queens in the first row and check if they attack each other

C. Use a greedy algorithm to place queens in the first available safe spot in each row

D. Modify the recursive function to store each valid board configuration in a list instead of returning after first success

Solution

1. Step 1: Understand the requirement

   We want to find and print all distinct solutions, not just one.

2. Step 2: Choose the correct approach

   Modifying the recursive function to continue searching after finding a solution and storing each valid board is the correct approach.

3. Step 3: Eliminate wrong options

   Stopping after first solution won't find all solutions. Greedy algorithm to place queens in the first available safe spot in each row and placing all queens in the first row and check if they attack each other are incorrect strategies.

4. Final Answer:

   Modify the recursive function to store each valid board configuration in a list instead of returning after first success -> Option D

5. Quick Check:

   Store all solutions by continuing recursion [OK]

Hint: Keep searching after each solution to collect all boards [OK]

Common Mistakes:

• Stopping recursion after first solution
• Using greedy instead of backtracking
• Placing multiple queens in one row