Description

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

Given an integer n, return all distinct solutions to the n-queens puzzle.

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:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solutions

1. Backtracking

  res 记录每个 queen 在每一行的位置。有如下几个特点:

  1. 正斜线(左下向右上)数组,该斜线特点为:斜线上每一格的行加列的和一定
  2. 反斜线(左上向右下)数组,该斜线特点为:斜线上每一格的行减列的差一定

  N 皇后问题的难点是要记录这正斜线和反斜线的结果,用于回溯剪枝。

# Time: O(n^2)
# Space: O(n)
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if n <= 0:
            return []
        res = []
        self.dfs(n, [], [], [], res)
        return [['.' * i + 'Q' + (n - i - 1) * '.' for i in sol] for sol in res]
    
    def dfs(self, n, xydiff_diag, xysum_diag, queens, res):
        # q is the current row index, queen store every column position of a queen
        r = len(queens)
        if r == n:
            res.append(queens)
            return
        
        # check every column position, c is the test column index
        for c in range(n):
            if c in queens or r - c in xydiff_diag or r + c in xysum_diag:
                continue
            self.dfs(n, xydiff_diag + [r - c], xysum_diag + [r + c], queens + [c], res)
# 9/9 cases passed (52 ms)
# Your runtime beats 97 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13 MB)

References

  1. 51. N-Queens
  2. LeetCode 51. N-Queens - 花花酱
  3. 6.1 N Queens Problem using Backtracking