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.

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.

1
2
3
4
5
Example 1:
![N-Queens](https://raw.githubusercontent.com/wenyupeng/pic-lib/main/blog/20260405191101352.png)
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
1
2
3
4
Example 2:

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

1 <= n <= 9

Approach

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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(row, columns, diagonals, anti_diagonals, board):
            if row == n:
                solution = [''.join(row) for row in board]
                solutions.append(solution)
                return

            for col in range(n):
                if col in columns or (row - col) in diagonals or (row + col) in anti_diagonals:
                    continue

                board[row][col] = 'Q'
                columns.add(col)
                diagonals.add(row - col)
                anti_diagonals.add(row + col)

                backtrack(row + 1, columns, diagonals, anti_diagonals, board)

                board[row][col] = '.'
                columns.remove(col)
                diagonals.remove(row - col)
                anti_diagonals.remove(row + col)

        solutions = []
        empty_board = [['.' for _ in range(n)] for _ in range(n)]
        backtrack(0, set(), set(), set(), empty_board)
        return solutions

# example usage:
n = 4
solution = Solution()
print(solution.solveNQueens(n))        
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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        m = 2*n-1
        onPath = [False]*n # columns
        diag1 = [False]*m # r+c
        diag2 = [False]*m # r-c
        res = []
        path = [0]*n
        def helper(r: int):
            if r == n:
                res.append(["."*c+"Q"+"."*(n-1-c) for c in path])
                return
            for c in range(n):
                if not onPath[c] and not diag1[r+c] and not diag2[r-c]:
                    path[r] = c
                    onPath[c] = diag1[r+c] = diag2[r-c] = True
                    helper(r+1)
                    path[r] = 0
                    onPath[c] = diag1[r+c] = diag2[r-c] = False
        helper(0)
        return res
# example usage:
n = 4
solution = Solution()
print(solution.solveNQueens(n))