N-Queens Problem in Java: Solving Constraints with Backtracking

Introduction to the N-Queens Problem

The N-Queens puzzle is the problem of placing N non-attacking queens on an N×N chessboard. A queen can attack horizontally, vertically, and diagonally. The goal is to find all distinct configurations where no two queens attack each other.

This problem is a classic example of how backtracking can be used to solve constraint satisfaction problems. It perfectly illustrates the power of systematically exploring possibilities while pruning invalid paths early.

When Should You Think About the N-Queens Problem?

While the N-Queens problem itself is a specific puzzle, the underlying principles are applicable when:

• You need to find all valid configurations that satisfy a set of constraints.
• The problem involves placing items on a grid or in a sequence.
• You can make incremental decisions and check for conflicts at each step.
• It's a combinatorial search problem where brute-force is too slow.

Core Concepts of Solving N-Queens with Backtracking

The backtracking approach for N-Queens involves placing queens one by one, column by column (or row by row). For each queen, we try to place it in a valid row. If a placement is valid, we proceed to place the next queen. If no valid row can be found for the current queen, we "backtrack" (undo the last placement) and try a different row for the previous queen.

Algorithm:

1. State Representation: We need a way to represent the board and track where queens are placed. A 2D character array (e.g., char[][] board) or a list of strings is common. We also need to efficiently check for conflicts.
2. Conflict Checking: To check if a position (row, col) is safe for a queen, we need to ensure no other queen attacks it. This means checking:
   • The current row (no other queen in this row).
   • The current col (no other queen in this column).
   • Both diagonals (no other queen on row - col = constant or row + col = constant).
3. Recursive Function: A function solveNQueens(col, board, results) that tries to place a queen in the current col.
   • Base Case: If col == N, all queens are placed. Add the current board configuration to results.
   • Recursive Step: For each row from 0 to N-1:
     • If (row, col) is a safe position:
       • Place a queen at (row, col).
       • Recursively call solveNQueens(col + 1, board, results).
       • Backtrack: Remove the queen from (row, col) to explore other possibilities.

Example: N-Queens Problem

Given an integer n, return all distinct solutions to the N-Queens puzzle.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, "."); // Initialize empty board with '.'
        }
        
        // Helper arrays to optimize conflict checking
        boolean[] cols = new boolean[n];
        boolean[] diag1 = new boolean[2 * n - 1]; // row + col
        boolean[] diag2 = new boolean[2 * n - 1]; // row - col + n - 1

        backtrackNQueens(0, n, board, results, cols, diag1, diag2);
        return results;
    }

    private void backtrackNQueens(
        int col,
        int n,
        char[][] board,
        List<List<String>> results,
        boolean[] cols,
        boolean[] diag1,
        boolean[] diag2
    ) {
        // Base Case: All queens are successfully placed
        if (col == n) {
            results.add(constructSolution(board));
            return;
        }

        // Explore Choices: Try placing a queen in each row of the current column
        for (int row = 0; row < n; row++) {
            // Check if the current position (row, col) is safe
            if (isSafe(row, col, n, cols, diag1, diag2)) {
                // Make a Choice: Place queen
                board[row][col] = 'Q';
                markOccupied(row, col, n, cols, diag1, diag2, true);

                // Recurse: Move to the next column
                backtrackNQueens(col + 1, n, board, results, cols, diag1, diag2);

                // Undo Choice (Backtrack): Remove queen
                board[row][col] = '.';
                markOccupied(row, col, n, cols, diag1, diag2, false);
            }
        }
    }

    // Optimized safety check using boolean arrays
    private boolean isSafe(int row, int col, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        return !cols[col] && !diag1[row + col] && !diag2[row - col + n - 1];
    }

    // Mark/unmark positions in helper arrays
    private void markOccupied(int row, int col, int n, boolean[] cols, boolean[] diag1, boolean[] diag2, boolean occupy) {
        cols[col] = occupy;
        diag1[row + col] = occupy;
        diag2[row - col + n - 1] = occupy;
    }

    // Converts char[][] board to List<String> format
    private List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (char[] row : board) {
            solution.add(new String(row));
        }
        return solution;
    }
}

Complexity:

• Time Complexity: The exact time complexity is hard to determine precisely due to pruning, but it's roughly O(N!) for checking all permutations, or more accurately, O(N^N) in the worst case without pruning. With pruning, it's significantly better, but still exponential. For N=8, it's around O(8!) or O(8^8).
• Space Complexity: O(N^2) for the board representation and O(N) for the recursion stack and helper arrays.

Dry Run: N-Queens (N=4)

Input: n = 4

Initial board:

. . . .
. . . .
. . . .
. . . .

backtrackNQueens(0, 4, board, results, ...)

• col = 0: Try row = 0
  • Place Q at (0,0).
  • Call backtrackNQueens(1, 4, board, results, ...)
    • col = 1: Try row = 0 (unsafe), row = 1 (unsafe), row = 2 (safe)
      • Place Q at (2,1).
      • Call backtrackNQueens(2, 4, board, results, ...)
        • col = 2: Try row = 0 (unsafe), row = 1 (unsafe), row = 2 (unsafe), row = 3 (safe)
          • Place Q at (3,2).
          • Call backtrackNQueens(3, 4, board, results, ...)
            • col = 3: Try row = 0 (unsafe), row = 1 (safe)
              • Place Q at (1,3).
              • Call backtrackNQueens(4, 4, board, results, ...)
                • col = 4: Base case. Add solution:

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

                • Return.
              • Backtrack (1,3).
            • row = 2 (unsafe), row = 3 (unsafe).
          • Backtrack (3,2).
        • row = 0,1,2 (unsafe).
      • Backtrack (2,1).
    • row = 3 (unsafe).
  • Backtrack (0,0).

... and so on, exploring all valid paths. The algorithm will find two distinct solutions for N=4.

First Solution for N=4:

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

Second Solution for N=4:

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

Reusable Template for N-Queens

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class NQueensSolver {

    /**
     * Solves the N-Queens puzzle and returns all distinct solutions.
     * @param n The size of the chessboard (N x N).
     * @return A list of lists of strings, where each inner list represents a board configuration.
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, "."); // Initialize empty board with '.'
        }

        // Helper boolean arrays for O(1) conflict checking
        boolean[] cols = new boolean[n]; // Tracks occupied columns
        boolean[] diag1 = new boolean[2 * n - 1]; // Tracks occupied main diagonals (row + col)
        boolean[] diag2 = new boolean[2 * n - 1]; // Tracks occupied anti-diagonals (row - col + n - 1)

        backtrackNQueens(0, n, board, results, cols, diag1, diag2);
        return results;
    }

    private void backtrackNQueens(
        int col, // Current column to place a queen
        int n,
        char[][] board,
        List<List<String>> results,
        boolean[] cols,
        boolean[] diag1,
        boolean[] diag2
    ) {
        // Base Case: All queens are successfully placed (col has reached n)
        if (col == n) {
            results.add(constructSolution(board));
            return;
        }

        // Explore Choices: Try placing a queen in each row of the current column
        for (int row = 0; row < n; row++) {
            // Check if the current position (row, col) is safe
            if (isSafe(row, col, n, cols, diag1, diag2)) {
                // Make a Choice: Place queen at (row, col)
                board[row][col] = 'Q';
                markOccupied(row, col, n, cols, diag1, diag2, true); // Mark this position as occupied

                // Recurse: Move to the next column to place the next queen
                backtrackNQueens(col + 1, n, board, results, cols, diag1, diag2);

                // Undo Choice (Backtrack): Remove queen from (row, col)
                board[row][col] = '.';
                markOccupied(row, col, n, cols, diag1, diag2, false); // Unmark this position
            }
        }
    }

    // Checks if placing a queen at (row, col) is safe (O(1) using helper arrays)
    private boolean isSafe(int row, int col, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        return !cols[col] && !diag1[row + col] && !diag2[row - col + n - 1];
    }

    // Marks or unmarks the position in the helper arrays
    private void markOccupied(int row, int col, int n, boolean[] cols, boolean[] diag1, boolean[] diag2, boolean occupy) {
        cols[col] = occupy;
        diag1[row + col] = occupy;
        diag2[row - col + n - 1] = occupy;
    }

    // Converts the char[][] board representation to a List<String> format for results
    private List<String> constructSolution(char[][] board) {
        List<String> solution = new ArrayList<>();
        for (char[] row : board) {
            solution.add(new String(row));
        }
        return solution;
    }
}

How to Recognize N-Queens in Interviews

Look for these clues:

• Problem Type: Placing items on a grid, usually with constraints that limit valid placements.
• Goal: Find all valid configurations or count the number of valid configurations.
• Keywords: "Chessboard", "queens", "non-attacking", "place items", "grid puzzle", "satisfy constraints".
• Structure: Often involves a square grid and rules about how items interact.

Common Mistakes

Mistake 1: Incorrect Conflict Checking

Missing one of the three conflict conditions (row, column, or both diagonals) will lead to incorrect solutions. The optimized isSafe function using boolean arrays is crucial for efficiency.

Mistake 2: Forgetting to Backtrack

Not resetting the board state (removing the queen) and unmarking the helper arrays after a recursive call will lead to incorrect results, as subsequent calls will see an invalid board state.

Mistake 3: Inefficient Conflict Checking

Checking the entire board for conflicts in O(N) time for each isSafe call will lead to O(N^3) per recursive step, making the overall complexity too high. Using boolean arrays for O(1) checks is a key optimization.

Mistake 4: Handling N=1 or N=0 Edge Cases

For N=1, there is one solution. For N=0, there are no queens to place, so an empty list of solutions is expected. Ensure your base cases handle these correctly.

N-Queens vs. Other Backtracking Problems

• Permutations/Combinations: N-Queens involves placing items with specific spatial constraints, whereas permutations/combinations are about selecting/arranging items from a set.
• Sudoku Solver: Similar in that it's a grid-based constraint satisfaction problem, but Sudoku has different rules for valid placements (rows, columns, 3x3 boxes).
• Word Search: Involves pathfinding on a grid, but the goal is to find a word, not to place items under non-attacking constraints.

Practice Problems for This Pattern

1. N-Queens (LeetCode 51) - The classic problem itself.
2. N-Queens II (LeetCode 52) - Count the number of distinct solutions.
3. Sudoku Solver (LeetCode 37) - Another classic constraint satisfaction problem using backtracking.
4. Solve the Equation (LeetCode 640) - While not grid-based, it involves solving for variables, which can sometimes use backtracking for finding solutions.

Interview Script You Can Reuse

"The N-Queens problem is a classic backtracking puzzle. My approach will be to place queens column by column. For each column, I'll iterate through all possible rows. Before placing a queen at `(row, col)`, I'll check if it's a safe position (no other queen in the same row, column, or diagonals). To optimize this check, I'll use three boolean arrays: one for columns, one for main diagonals (`row + col`), and one for anti-diagonals (`row - col + n - 1`). If a position is safe, I'll place the queen, mark the corresponding positions in my helper arrays, and recursively call the function for the next column. After the recursive call returns, I'll backtrack by removing the queen and unmarking the helper arrays. The base case is when all `N` queens are successfully placed (i.e., `col == N`), at which point I'll add the current board configuration to my results. The time complexity will be exponential, roughly O(N!), and space complexity will be O(N^2) for the board and O(N) for the recursion stack and helper arrays."

Final Takeaways

• N-Queens is a prime example of backtracking for constraint satisfaction.
• It involves placing items incrementally and pruning invalid paths.
• Efficient conflict checking (using boolean arrays for rows, columns, and diagonals) is key.
• Always remember to backtrack (undo choices) to explore all possibilities.

Mastering the N-Queens problem provides a strong foundation for solving a wide range of combinatorial search and constraint satisfaction problems using backtracking.

Read Next

• DSA in Java Series
• Sudoku Solver in Java
• Word Search in Java
• Subset Sum and Partition Problems in Java
• Backtracking Pattern in Java: Permutations and Combinations
• Bellman-Ford Algorithm in Java
• Kruskal’s Algorithm in Java
• Prim’s Algorithm in Java
• Matrix Traversal in Java
• Lowest Common Ancestor (LCA) in Java
• Dijkstra’s Algorithm in Java
• Union Find (DSU) in Java
• Topological Sort in Java
• BFS (Breadth First Search) in Java
• DFS (Depth First Search) in Java
• Monotonic Queue Pattern in Java
• Monotonic Stack Pattern in Java
• Sorting Algorithms in Java
• Binary Search Pattern in Java
• In-place Reversal of a Linked List in Java
• Fast & Slow Pointers in Java
• Dutch National Flag Pattern in Java
• Kadane’s Algorithm in Java
• Prefix Sum Pattern in Java
• Sliding Window Pattern in Java
• Two Pointers Pattern in Java
• Big-O Notation in Java