LeetCode N皇后题解

LeetCode N皇后题解

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

示例：

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

解题思路

方法：回溯

思路：

• 使用回溯算法来解决这个问题。
• 维护一个数组cols来记录每一列是否已经有皇后。
• 维护一个数组diag1来记录主对角线是否已经有皇后。
• 维护一个数组diag2来记录副对角线是否已经有皇后。
• 从第一行开始，尝试所有可能的列：
  • 如果当前列、主对角线、副对角线都没有皇后，则放置皇后。
  • 递归处理下一行。
  • 回溯：撤销选择，继续尝试其他列。
• 当行号等于 n 时，将解决方案加入结果列表。

复杂度分析：

• 时间复杂度：O(n!)，这是 n 皇后问题的复杂度。
• 空间复杂度：O(n)，递归调用栈的深度为 n。

代码实现

方法：回溯

# N皇后（回溯） def solve_n_queens(n): result = [] cols = [False] * n diag1 = [False] * (2 * n) diag2 = [False] * (2 * n) board = [['.' for _ in range(n)] for _ in range(n)] def backtrack(row): if row == n: result.append([''.join(row) for row in board]) return for col in range(n): d1 = row - col + n d2 = row + col if cols[col] or diag1[d1] or diag2[d2]: continue cols[col] = diag1[d1] = diag2[d2] = True board[row][col] = 'Q' backtrack(row + 1) board[row][col] = '.' cols[col] = diag1[d1] = diag2[d2] = False backtrack(0) return result # 测试 def test_solve_n_queens(): n = 4 print(solve_n_queens(n)) # 输出：[['..Q.', 'Q...', '...Q', '.Q..'], ['.Q..', '...Q', 'Q...', '..Q.']] if __name__ == "__main__": test_solve_n_queens()

测试用例

测试用例 1：n=4

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

测试用例 2：n=1

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

总结

N皇后是一个经典的回溯算法问题，它可以通过回溯算法来高效地解决。

回溯算法的核心思想是：从第一行开始，尝试所有可能的列，确保不会与其他皇后冲突，递归处理下一行，然后回溯。

掌握回溯算法的使用方法，对于解决类似的问题非常重要。