N 皇后

难度：⭐⭐⭐⭐ Hard

考点

• 回溯经典问题
• 对角线攻击判断
• 用集合/数组优化冲突检测
• 面试中考察回溯思维完整性

题目描述

在 n×n 的棋盘上放置 n 个皇后，使得它们互不攻击（任意两个皇后不在同一行、同一列、同一对角线上）。返回所有不同的解法。

每种解法用一个 []string 表示，其中 'Q' 表示皇后，'.' 表示空位。

函数签名

func solveNQueens(n int) [][]string

示例

输入：n = 4
输出：
[
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

输入：n = 1
输出：[["Q"]]

要求

1. 回溯法，逐行放置
2. O(1) 判断冲突（用列集合 + 两条对角线集合）

提示

• 逐行放置，每行只放一个 → 行不冲突
• 用 cols[] 记录哪些列被占用
• 主对角线：同一条上 row-col 相同（加偏移避免负数）
• 副对角线：同一条上 row+col 相同
• 三个 bool 数组实现 O(1) 冲突检测

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func solveNQueens(n int) [][]string {
	var result [][]string
	board := make([][]byte, n)
	for i := range board {
		board[i] = make([]byte, n)
		for j := range board[i] {
			board[i][j] = '.'
		}
	}

	cols := make([]bool, n)
	diag1 := make([]bool, 2*n) // 主对角线 row-col+n
	diag2 := make([]bool, 2*n) // 副对角线 row+col

	var backtrack func(row int)
	backtrack = func(row int) {
		if row == n {
			solution := make([]string, n)
			for i := range board {
				solution[i] = string(board[i])
			}
			result = append(result, solution)
			return
		}
		for col := 0; col < n; col++ {
			if cols[col] || diag1[row-col+n] || diag2[row+col] {
				continue
			}
			board[row][col] = 'Q'
			cols[col] = true
			diag1[row-col+n] = true
			diag2[row+col] = true

			backtrack(row + 1)

			board[row][col] = '.'
			cols[col] = false
			diag1[row-col+n] = false
			diag2[row+col] = false
		}
	}
	backtrack(0)
	return result
}