NQueens

Problem Link

Problem: N-Queens

Problem Statement

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

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 placement of the n queens, where 'Q' and '.' indicate a queen and an empty space respectively.

Examples

Example 1
Input: n = 4
Output:

[
 [".Q..",
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

Example 2
Input: n = 1
Output: [["Q"]]

Constraints

1 <= n <= 9

Intuition

This is a classical backtracking problem:

At each row, try placing a queen in every column.
Use a helper function to check if placing a queen at a specific (row, col) is valid.
If valid, mark that position and move to the next row.
Once all rows are filled (row == n), convert the board into the required string format and add it to the result.
Backtrack after each recursive call.

Approach (Backtracking with Board Validation)

Use a 2D boolean array chess[n][n] to represent the board.
Use recursion to place a queen row by row.
At each row:
- Try placing the queen in all columns.
- If isValid() returns true, proceed.
Base case: If row == n, convert the board to a list of strings and add to result.
Backtrack after the recursive call by removing the queen.

Code (Java)

class Solution {
    public List<List<String>> solveNQueens(int n) {
        boolean[][] chess = new boolean[n][n];
        List<List<String>> ans = new ArrayList<>();
        helper(0, n, chess, ans);
        return ans;
    }

    public void helper(int row, int n, boolean[][] chess, List<List<String>> result) {
        if (row == n) {
            List<String> mat = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.setLength(0);
                for (int j = 0; j < n; j++) {
                    sb.append(chess[i][j] ? 'Q' : '.');
                }
                mat.add(sb.toString());
            }
            result.add(mat);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isValid(chess, row, col)) {
                chess[row][col] = true;
                helper(row + 1, n, chess, result);
                chess[row][col] = false; // backtrack
            }
        }
    }

    public boolean isValid(boolean[][] chess, int r, int c) {
        // Check vertically upwards
        for (int i = r - 1; i >= 0; i--) {
            if (chess[i][c]) return false;
        }

        // Check upper-left diagonal
        for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
            if (chess[i][j]) return false;
        }

        // Check upper-right diagonal
        for (int i = r - 1, j = c + 1; i >= 0 && j < chess.length; i--, j++) {
            if (chess[i][j]) return false;
        }

        return true;
    }
}

Time and Space Complexity

Time Complexity: O(N!)
- At each row, we try placing queens in N columns, with pruning via the isValid() function.
Space Complexity: O(N²)
- For the board and result list.

Dry Run

Input: `n = 4`

Initial state: chess = 4x4 board, all false.

Start placing queen row by row:

Try (0, 0), (0, 1), (0, 2), (0, 3)
For each, recurse to next row if valid
Continue building
If at any row, no valid column → backtrack
When row == n, convert board to list of strings and store

Eventually, two configurations are found.

Conclusion

This problem is an elegant application of recursive backtracking combined with board validation logic. It teaches how to prune invalid paths early and how to build up state (chess board) and backtrack it efficiently.