Algorithm Day63 - N-Queens

Posted on Edited on In , Views:

🧩 Problem Description

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.
Return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the queen placements, represented as an array of strings, where 'Q' and '.' indicate a queen and an empty space, respectively.

💬 Example

Example 1

1
2
3
4
5
6
7
8
9
10
11
Input: n = 4
Output: [
 [".Q..",
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",
  "Q...",
  "...Q",
  ".Q.."]
]

Example 2

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

💡 Intuition

This is a classic backtracking problem.
We need to try placing queens row by row, ensuring each placement is valid:

  1. A queen cannot share the same column.
  2. A queen cannot share the same diagonal.

We backtrack:

  • Place a queen in a valid column for the current row.
  • Move to the next row.
  • If all rows are filled, store the board as one solution.

🔢 Java Code (Backtracking)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(res, board, 0);
        return res;
    }

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

    private boolean isValid(char[][] board, int row, int col) {
        // check column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // check upper-left diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // check upper-right diagonal
        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> res = new ArrayList<>();
        for (char[] row : board) res.add(new String(row));
        return res;
    }
}

⏱ Complexity Analysis

Let n be the board size:

  • Time: O(n!) — Each row has up to n choices, pruning reduces but worst case exponential.
  • Space: O(n^2) for board + O(n) recursion depth.

✍️ Summary

  • Use backtracking to try placing queens row by row.
  • Check columns and diagonals for validity.
  • Collect solutions when all rows are filled.

Related problems

  • lc-52 — N-Queens II (count solutions)