n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
image.png
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：

输入：4
输出：[
[“.Q..”, // 解法 1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”, // 解法 2
“Q…”,
“…Q”,
“.Q..”]
]
解释: 4 皇后问题存在两个不同的解法。

提示：
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

解法一：回溯

  1. class Solution:
  2.     def solveNQueens(self, n: int) -> List[List[str]]:
  3.         """N queens backtrace with DP"""
  4.         solves = []
  5.         # Marks unavailable cols, diags and anti_diags
  6.         cols = [False] * n
  7.         diags = [False] * (2 * n - 1)
  8.         anti_diags = [False] * (2 * n - 1)
  10.         def _cell_to_diag(row, col):
  11.             """The first diag is on top left"""
  12.             return row + col
  14.         def _cell_to_anti_diag(row, col):
  15.             """The first anti_diag is on bottem left"""
  16.             return n - row + col - 1
  18.         def _queen(row, solve):
  19.             """
  20.             Test every col of current row.
  21.             Add valid  to current solve then find cols in the next row.
  22.             """
  23.             if row > n - 1:
  24.                 solves.append(solve)
  25.                 return
  26.             for col in range(n):
  27.                 idx1 = _cell_to_diag(row, col)
  28.                 idx2 = _cell_to_anti_diag(row, col)
  29.                 if not cols[col] and not diags[idx1] and not anti_diags[idx2]:
  30.                     # Drop a queen on i-th row then mark col, diag and anti_diag
  31.                     cols[col] = diags[idx1] = anti_diags[idx2] = True
  32.                     _queen(row + 1, solve + [col])
  33.                     # Revert col, diag and anti_diag when tracing-back
  34.                     cols[col] = diags[idx1] = anti_diags[idx2] = False
  36.         def _print_solves(solves):
  37.             return [
  38.                 [
  39.                     ('.' * col + 'Q' + '.' * (n - col - 1))
  40.                     for col in solve
  41.                 ]
  42.                 for solve in solves
  43.             ]
  46.         _queen(0, [])
  47.         return _print_solves(solves)

相关题目

52. N皇后 II

只要给出解的数量即可

  1. class Solution:
  2.     def totalNQueens(self, n: int) -> int:
  3.         def backtrack(row: int) -> int:
  4.             if row == n:
  5.                 return 1
  6.             else:
  7.                 count = 0
  8.                 for i in range(n):
  9.                     if i in columns or row - i in diagonal1 or row + i in diagonal2:
  10.                         continue
  11.                     columns.add(i)
  12.                     diagonal1.add(row - i)
  13.                     diagonal2.add(row + i)
  14.                     count += backtrack(row + 1)
  15.                     columns.remove(i)
  16.                     diagonal1.remove(row - i)
  17.                     diagonal2.remove(row + i)
  18.                 return count
  20.         columns = set()
  21.         diagonal1 = set()
  22.         diagonal2 = set()
  23.         return backtrack(0)