N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4 Output: [[”.Q..”,”…Q”,“Q…”,”..Q.”],[”..Q.”,“Q…”,”…Q”,”.Q..”]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1 Output: [[“Q”]]

Constraints:

• 1 <= n <= 9

Approach: Backtracking

Algorithm

1. Place queens row by row
2. For each row, try every column and check whether the placement conflicts with already placed queens
3. A conflict exists if a queen is already placed in the same column, the same main diagonal, or the same anti-diagonal
4. Use boolean arrays to track occupied columns and diagonals in O(1) checks
5. If a full board is completed, record the solution; otherwise backtrack by removing the queen

Time & Space Complexity

• Time Complexity: O(n!) - the number of valid placements grows factorially (with pruning)
• Space Complexity: O(n) - recursion depth and the tracking arrays

Java Implementation

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

public class NQueens {

    /**
     * Return all distinct solutions to the n-queens puzzle.
     * @param n Board size
     * @return List of solutions, each a list of strings
     */
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        boolean[] col = new boolean[n];
        boolean[] diag = new boolean[2 * n - 1]; // main diagonal: r + c
        boolean[] antiDiag = new boolean[2 * n - 1]; // anti-diagonal: r - c + n - 1
        char[][] board = new char[n][n];

        for (char[] row : board) {
            java.util.Arrays.fill(row, '.');
        }

        backtrack(0, n, col, diag, antiDiag, board, result);
        return result;
    }

    private static void backtrack(int row, int n, boolean[] col,
                                  boolean[] diag, boolean[] antiDiag,
                                  char[][] board, List<List<String>> result) {
        if (row == n) {
            result.add(construct(board));
            return;
        }

        for (int c = 0; c < n; c++) {
            int d = row + c;
            int ad = row - c + n - 1;

            if (col[c] || diag[d] || antiDiag[ad]) {
                continue;
            }

            board[row][c] = 'Q';
            col[c] = true;
            diag[d] = true;
            antiDiag[ad] = true;

            backtrack(row + 1, n, col, diag, antiDiag, board, result);

            board[row][c] = '.';
            col[c] = false;
            diag[d] = false;
            antiDiag[ad] = false;
        }
    }

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

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: n = 4");
        System.out.println("Output: " + solveNQueens(4));
        // Expected: [[.Q.., ...Q, Q..., ..Q.], [..Q., Q..., ...Q, .Q..]]

        System.out.println("Input: n = 1");
        System.out.println("Output: " + solveNQueens(1));
        // Expected: [[Q]]
    }
}

Key Points

1. One Queen per Row: Placing row by row guarantees no two queens share a row
2. Diagonal Tracking: Main diagonal (row + col) and anti-diagonal (row - col + n - 1) are constant per line
3. O(1) Conflict Check: Boolean arrays replace scanning the whole board
4. Backtracking: Undo the queen placement when a branch fails
5. Constraint: n <= 9, so the search space is manageable