N-Queens – 51. LeetCode

The N-Queens problems asks us to place N queens on an N * N chessboard such that no two queens threaten each other. The means no two queens can bin the the same row, column, or diagonal. The challenge is to find all possible configurations of the board that satisfy these conditions.

Imagine you’re solving a puzzle where each queen wants her own “safe spot”, and no queen wants to attack or be attack. The task is to figure out all the ways you can arrange them peacefully.

Brute Force Approach

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

public class NQueensBruteForce {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        
        // Initialize the board with '.'
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        
        solve(0, board, result);
        return result;
    }

    private void solve(int row, char[][] board, List<List<String>> result) {
        int n = board.length;
        if (row == n) {
            result.add(construct(board));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                solve(row + 1, board, result);
                board[row][col] = '.';
            }
        }
    }

    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }

    private List<String> construct(char[][] board) {
        List<String> result = new ArrayList<>();
        for (char[] row : board) {
            result.add(new String(row));
        }
        return result;
    }
}

This brute force approach tries every possible placement of queens row by row. it backtracks if placing a queen violates any rules. If a valid board configuration is reached, it saves the result. It checks if a queen’s placement is valid by verifying no conflicts in the column or diagonals.

Optimal Approach

Chosen Algorithm: Backtracking with pruning.

The backtracking approach systematically explores possibilities while pruning invalid paths early, avoiding unnecessary computations. The key insight is to:

• Use arrays to track conflicting columns and diagonals efficiently.

• Skip invalid positions immediately instead of exploring them fully.

This algorithm is suited because:

1. The problem has a clear recursive structure: place a queen row by row and backtrack if constraints are violated.

2. It minimizes unnecessary explorations using pruning.

Data Structures Used:

• Arrays for tracking conflicts in columns and diagonals.

• List for storing results.

Steps of the Algorithm

1. Initialize arrays to track conflicts in columns and diagonals.
2. Use a helper function for recursive backtracking.
3. At each step:
   • Check if placing a queen is valid.
   • Place the queen and mark the column and diagonal as occupied.
   • Recur for the next row
   • Backtrack by removing the queen and resetting conflicts.
4. Add valid board configurations to the result.

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

public class NQueens {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] cols = new int[n]; // Tracks columns
        int[] d1 = new int[2 * n]; // Tracks main diagonals
        int[] d2 = new int[2 * n]; // Tracks anti-diagonals
        char[][] board = new char[n][n];
        
        // Initialize the board
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        
        backtrack(0, n, board, result, cols, d1, d2);
        return result;
    }

    private void backtrack(int row, int n, char[][] board, List<List<String>> result,
                           int[] cols, int[] d1, int[] d2) {
        if (row == n) {
            result.add(construct(board));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            int id1 = row - col + n; // Main diagonal index
            int id2 = row + col;     // Anti-diagonal index
            if (cols[col] == 1 || d1[id1] == 1 || d2[id2] == 1) continue;

            board[row][col] = 'Q';
            cols[col] = 1; d1[id1] = 1; d2[id2] = 1;
            backtrack(row + 1, n, board, result, cols, d1, d2);
            board[row][col] = '.';
            cols[col] = 0; d1[id1] = 0; d2[id2] = 0;
        }
    }

    private List<String> construct(char[][] board) {
        List<String> result = new ArrayList<>();
        for (char[] row : board) {
            result.add(new String(row));
        }
        return result;
    }
}

1. Initialize Data Structures For Checking Queen Validity

    List<List<String>> result = new ArrayList<>();
    int[] cols = new int[n]; // Tracks columns
    int[] d1 = new int[2 * n]; // Tracks main diagonal
    int[] d2 = new int[2 * n]; // Tracks anti-diagonals
    char[][] board = new char[n][n];

• The cols array tracks whether a column is occupied by a queen.
• The d1 and d2 arrays track conflicts on main and anti-diagonals, respectively.

2. Preprocess the board

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = '.';
        }
    }

• The board is set up as an empty grid where ‘.’ represents an empty cell.
• This creates the chessboard representation that id modified and validated during the backtracking process.

3. Backtrack

backtrack(0, n, board, result, cols, d1, d2);
return result;

• The backtrack function is the core of the algorithm, systematically exploring all possible placements.

4. Base Case

    if (row == n) {
        result.add(construct(board));
        return;
    }

• It identifies and stores valid solutions once the board satisfies all constraints.

5. Iterating Over Columns

    for (int col = 0; col < n; col++) {
        int id1 = row - col + n; // Main diagonal index
        int id2 = row + col;     // Anti-diagonal index
        if (cols[col] == 1 || d1[id1] == 1 || d2[id2] == 1) continue;

• Iterates over each column in the current row.
• Calculates diagonal indices and checks if the column or diagonals are occupied.

• This ensures the queens are only placed in safe positions

6. Placing a Queen and Recursive Call

        board[row][col] = 'Q';
        cols[col] = 1; d1[id1] = 1; d2[id2] = 1;
        backtrack(row + 1, n, board, result, cols, d1, d2);
        board[row][col] = '.';
        cols[col] = 0; d1[id1] = 0; d2[id2] = 0;
    }

• A queen is place on the board (board[row][col] = ‘Q’), and the column and diagonals are marked as occupied.
• The algorithm then proceeds to the new row (backtrack(row + 1, …)).
• After recursion, the queen is removed (backtracking) to try other possibilities.

7. Constructing the Solution

private List<String> construct(char[][] board) {
    List<String> result = new ArrayList<>();
    for (char[] row : board) {
        result.add(new String(row));
    }
    return result;
}

• The construct method converts the board into a list of strings, representing the solution.
• This formats the board for output, making the result user-friendly and consistent.

Why Backtracking Works

• It eliminates invalid configurations early (pruning) by skipping unsafe placements.

• It explores solutions systematically, ensuring all possibilities are covered.

• The use of tracking arrays avoids recomputation, improving both time and space efficiency.