N-Queens

Description

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

---

Brute Force Approach: Standard Backtracking with $O(N)$ Validation

Intuition

Place queens column by column (col from 0 to n - 1). For each column, iterate through every row (0 to n - 1) and attempt to place a queen.

Before placing a queen at (row, col), run an $O(N)$ helper function isSafe() to check if any previously placed queen attacks this position from:

1. The same horizontal row to the left.
2. The upper-left diagonal.
3. The lower-left diagonal.

import java.util.*;
 
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        backtrack(0, board, result, n);
        return result;
    }
 
    private void backtrack(int col, char[][] board, List<List<String>> result, int n) {
        if (col == n) {
            result.add(constructBoard(board));
            return;
        }
 
        for (int row = 0; row < n; row++) {
            if (isSafe(row, col, board, n)) {
                // 1. CHOOSE
                board[row][col] = 'Q';
 
                // 2. EXPLORE
                backtrack(col + 1, board, result, n);
 
                // 3. UN-CHOOSE (Backtrack)
                board[row][col] = '.';
            }
        }
    }
 
    private boolean isSafe(int row, int col, char[][] board, int n) {
        // Check left side of current row
        for (int c = 0; c < col; c++) {
            if (board[row][c] == 'Q') return false;
        }
 
        // Check upper-left diagonal
        for (int r = row, c = col; r >= 0 && c >= 0; r--, c--) {
            if (board[r][c] == 'Q') return false;
        }
 
        // Check lower-left diagonal
        for (int r = row, c = col; r < n && c >= 0; r++, c--) {
            if (board[r][c] == 'Q') return false;
        }
 
        return true;
    }
 
    private List<String> constructBoard(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) {
            res.add(new String(row));
        }
        return res;
    }
}
 

Complexity

• Time Complexity: $O(N!\cdot N)$ — Placing queens column by column has $N!$ possibilities, and validating each placement with isSafe() takes $O(N)$ time.
• Space Complexity: $O(N^2)$ — Board storage of size $N\times N$ plus $O(N)$ recursion depth stack.

---

Most Optimized Solution: Backtracking with $O(1)$ Hash Array Lookups

Intuition

Instead of scanning the board in $O(N)$ time to check if a position is safe, use boolean arrays (hashing)** to check safety in $O(1)$ time:

1. leftRow[row]: Tracks if row already has a queen.
2. lowerDiagonal[row + col]: For any position (row, col), elements on the same lower-left diagonal share the identical sum row + col.
3. upperDiagonal[n - 1 + col - row]: For any position (row, col), elements on the same upper-left diagonal share the identical index (n - 1) + col - row.

Board coordinate indexing for 4x4:
Lower Diagonals (row + col):         Upper Diagonals (n - 1 + col - row):
 0  1  2  3                           3  4  5  6
 1  2  3  4                           2  3  4  5
 2  3  4  5                           1  2  3  4
 3  4  5  6                           0  1  2  3
 

import java.util.*;
 
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
 
        boolean[] leftRow = new boolean[n];
        boolean[] lowerDiagonal = new boolean[2 * n - 1];
        boolean[] upperDiagonal = new boolean[2 * n - 1];
 
        backtrack(0, board, result, leftRow, lowerDiagonal, upperDiagonal, n);
        return result;
    }
 
    private void backtrack(int col, char[][] board, List<List<String>> result, 
                           boolean[] leftRow, boolean[] lowerDiagonal, boolean[] upperDiagonal, int n) {
        if (col == n) {
            result.add(constructBoard(board));
            return;
        }
 
        for (int row = 0; row < n; row++) {
            if (!leftRow[row] && !lowerDiagonal[row + col] && !upperDiagonal[n - 1 + col - row]) {
                // 1. CHOOSE
                board[row][col] = 'Q';
                leftRow[row] = true;
                lowerDiagonal[row + col] = true;
                upperDiagonal[n - 1 + col - row] = true;
 
                // 2. EXPLORE
                backtrack(col + 1, board, result, leftRow, lowerDiagonal, upperDiagonal, n);
 
                // 3. UN-CHOOSE (Backtrack)
                board[row][col] = '.';
                leftRow[row] = false;
                lowerDiagonal[row + col] = false;
                upperDiagonal[n - 1 + col - row] = false;
            }
        }
    }
 
    private List<String> constructBoard(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) {
            res.add(new String(row));
        }
        return res;
    }
}
 

Complexity

• Time Complexity: $O(N!)$ — Safety checks are reduced from $O(N)$ to $O(1)$ time per placement choice.
• Space Complexity: $O(N)$ — Extra lookup arrays take $O(N)$ space ($3\cdot N$ space total), excluding output board construction.

---

Easy Memory Rule

“Place column by column (col + 1). Validate in $O(1)$ using 3 arrays: leftRow[row], lowerDiagonal[row + col], and upperDiagonal[n - 1 + col - row].”

In the optimized N-Queens solution, we place queens column by column (from col = 0 to col = n - 1).

Because we only place one queen per column and move left-to-right, we never need to check for attacks in the same column or anywhere to the right. We only need to check three directions:

1. Same Horizontal Row (to the left)
2. Lower-Left Diagonal ($\swarrow$)
3. Upper-Left Diagonal ($\nwarrow$)

Instead of running loops ($O(N)$) to check these three paths, we use 3 boolean arrays as lookup tables to check safety in $O(1)$ constant time.

---

1. leftRow Array

• Size: n
• Lookup Index: row
• Logic: Every square in the same horizontal row shares the exact same row index.
• If leftRow[2] == true, it means a queen is already sitting anywhere in Row 2.

---

2. lowerDiagonal Array ($\swarrow$)

• Size: 2 * n - 1
• Lookup Index Formula: row + col
• Logic: On any lower-left diagonal, as row goes down (increases by 1), col goes left (decreases by 1). Therefore, the sum row + col is constant for every square on that diagonal.

For a $4\times 4$ chessboard, notice how row + col identifies each lower diagonal:

$\begin{array}{cccc}(0,0)[0]& (0,1)[1]& (0,2)[2]& (0,3)[3]\\ (1,0)[1]& (1,1)[2]& (1,2)[3]& (1,3)[4]\\ (2,0)[2]& (2,1)[3]& (2,2)[4]& (2,3)[5]\\ (3,0)[3]& (3,1)[4]& (3,2)[5]& (3,3)[6]\end{array}$

• Squares (3,0), (2,1), (1,2), and (0,3) all share the sum row + col = 3.
• If a queen is placed at (2,1), setting lowerDiagonal[3] = true blocks the entire diagonal instantly.

---

3. upperDiagonal Array ($\nwarrow$)

• Size: 2 * n - 1
• Lookup Index Formula: (n - 1) + col - row
• Logic: On any upper-left diagonal, row and col increase or decrease together. Therefore, the difference col - row is constant for every square on that diagonal.

Because col - row can result in negative numbers (e.g., at row 3, col 0: $0-3=-3$), we add an offset of (n - 1) so every index becomes non-negative starting from 0.

For a $4\times 4$ board (n - 1 = 3), the index 3 + col - row maps as:

$\begin{array}{cccc}(0,0)[3]& (0,1)[4]& (0,2)[5]& (0,3)[6]\\ (1,0)[2]& (1,1)[3]& (1,2)[4]& (1,3)[5]\\ (2,0)[1]& (2,1)[2]& (2,2)[3]& (2,3)[4]\\ (3,0)[0]& (3,1)[1]& (3,2)[2]& (3,3)[3]\end{array}$

• Squares (0,0), (1,1), (2,2), and (3,3) all map to index 3.
• If a queen is placed at (1,1), setting upperDiagonal[3] = true blocks that entire diagonal.

---

How the Backtracking Logic Uses Them

At position (row, col):

1. Check Safety in $O(1)$:

if (!leftRow[row] && !lowerDiagonal[row + col] && !upperDiagonal[n - 1 + col - row])
 

2. Choose (Mark as Occupied):

leftRow[row] = true;
lowerDiagonal[row + col] = true;
upperDiagonal[n - 1 + col - row] = true;
 

3. Explore:

backtrack(col + 1, ...); // Move to fill next column
 

4. Un-Choose (Backtrack / Reset):

leftRow[row] = false;
lowerDiagonal[row + col] = false;
upperDiagonal[n - 1 + col - row] = false;