N Queens Problem in DSA Java - Execution Trace

Concept Flow - N Queens Problem

Start with empty board

↓

Place queen in row 0, col 0

↓

Check if safe

↓

Place queen

↓

Move to next row

↓

Repeat until all queens placed

↓

If no safe col, backtrack to previous row

↓

Try next col in previous row

↓

Repeat until solution found or all options exhausted

Try placing queens row by row, checking safety. If stuck, backtrack to try other columns.

Execution Sample

DSA Java

for (int row = 0; row < N; row++) {
  for (int col = 0; col < N; col++) {
    if (isSafe(board, row, col)) {
      board[row][col] = 'Q';
      if (solveNQueens(board, row + 1)) return true;
      board[row][col] = '.'; // backtrack
    }
  }
  return false;
}

Try placing a queen in each column of the current row, recurse to next row if safe, backtrack if needed.

Execution Table

Step	Operation	Row	Column	Action	Board State	Backtrack?
1	Place queen	0	0	Check safe → Yes, place Q	[Q . . . . . . . . . . . . . . .]	No
2	Place queen	1	0	Check safe → No, try next col	[Q . . . . . . . . . . . . . . .]	No
3	Place queen	1	1	Check safe → No, try next col	[Q . . . . . . . . . . . . . . .]	No
4	Place queen	1	2	Check safe → Yes, place Q	[Q . . . . . Q . . . . . . . . .]	No
5	Place queen	2	0	Check safe → No, try next col	[Q . . . . . Q . . . . . . . . .]	No
6	Place queen	2	1	Check safe → No, try next col	[Q . . . . . Q . . . . . . . . .]	No
7	Place queen	2	3	Check safe → Yes, place Q	[Q . . . . . Q . . . . Q . . . .]	No
8	Place queen	3	0	Check safe → No, try next col	[Q . . . . . Q . . . . Q . . . .]	No
9	Place queen	3	1	Check safe → Yes, place Q	[Q . . . . . Q . . . . Q . Q . .]	No
10	All queens placed	-	-	Solution found	[Q . . . . . Q . . . . Q . Q . .]	No
11	Backtrack	3	1	Remove queen, try next col	[Q . . . . . Q . . . . Q . . . .]	Yes
12	Place queen	3	2	Check safe → No, try next col	[Q . . . . . Q . . . . Q . . . .]	No
13	Place queen	3	3	Check safe → No, backtrack	[Q . . . . . Q . . . . Q . . . .]	Yes
14	Backtrack	2	3	Remove queen, try next col	[Q . . . . . Q . . . . . . . . .]	Yes
15	Place queen	2	1	Check safe → No, try next col	[Q . . . . . Q . . . . . . . . .]	No
16	Place queen	2	2	Check safe → No, backtrack	[Q . . . . . Q . . . . . . . . .]	Yes
17	Backtrack	1	2	Remove queen, try next col	[Q . . . . . . . . . . . . . . .]	Yes
18	Place queen	1	3	Check safe → Yes, place Q	[Q . . . . . . Q . . . . . . . .]	No
19	Place queen	2	0	Check safe → Yes, place Q	[Q . . . . . . Q Q . . . . . . .]	No
20	Place queen	3	1	Check safe → Yes, place Q	[Q . . . . . . Q Q . . . . Q . .]	No
21	All queens placed	-	-	Solution found	[Q . . . . . . Q Q . . . . Q . .]	No

💡 All queens placed successfully or all options exhausted

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 9	After Step 10	After Step 17	After Step 21
board	[empty]	[Q . . . . . Q . . . . . . . . .]	[Q . . . . . Q . . . . Q . . . .]	[Q . . . . . Q . . . . Q . Q . .]	[Q . . . . . Q . . . . Q . Q . .]	[Q . . . . . . . . . . . . . . .]	[Q . . . . . . Q Q . . . . Q . .]
row	0	2	2	3	3	1	3
col	0	2	3	1	1	2	1
backtrack	No	No	No	No	No	Yes	No

Key Moments - 3 Insights

Why do we backtrack after placing queens in some rows?

Backtracking happens when no safe column is found in the current row (see steps 11, 13, 14). We remove the last placed queen and try the next column in the previous row to find a valid arrangement.

How do we know if placing a queen is safe?

We check if no other queen is in the same column, or diagonals above the current row (see 'Check safe' actions in execution_table). If safe, we place the queen; otherwise, try next column.

When does the algorithm stop?

It stops when all queens are placed safely (step 10 or 21) or when all columns in the first row are tried without success (not shown here).

Visual Quiz - 3 Questions

Look at the execution table, at which step is the first queen placed in row 2?

A Step 7

B Step 9

C Step 5

D Step 19

💡 Hint

Check the 'Operation' and 'Row' columns for 'Place queen' at row 2.

At which step does the algorithm first backtrack?

A Step 10

B Step 13

C Step 11

D Step 17

💡 Hint

Look for the first 'Backtrack' action in the 'Operation' column.

If the queen at row 1, column 2 was safe, how would the board state at step 4 change?

A Queen placed at (1,3) instead

B Queen placed at (1,2) as shown

C No queen placed in row 1

D Backtrack would happen earlier

💡 Hint

Step 4 shows queen placed at (1,2) because it was safe; changing safety would change placement.

Concept Snapshot

N Queens Problem:
- Place N queens on an N×N board
- No two queens share the same row, column, or diagonal
- Use backtracking: place queen row by row
- Check safety before placing
- Backtrack if stuck
- Stop when all queens placed

Full Transcript

The N Queens Problem places N queens on an N by N chessboard so that no two queens attack each other. The algorithm tries to place queens row by row. For each row, it tries each column and checks if placing a queen there is safe. Safety means no other queen is in the same column or diagonals above. If safe, it places the queen and moves to the next row. If no column is safe, it backtracks by removing the last placed queen and tries the next column in the previous row. This continues until all queens are placed or all options are exhausted. The execution table shows each step, the board state, and when backtracking happens. Key moments include understanding why backtracking is needed, how safety is checked, and when the algorithm stops.

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