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()测试用例测试用例 1n4输入n 4输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]测试用例 2n1输入n 1输出[[Q]]总结N皇后是一个经典的回溯算法问题它可以通过回溯算法来高效地解决。回溯算法的核心思想是从第一行开始尝试所有可能的列确保不会与其他皇后冲突递归处理下一行然后回溯。掌握回溯算法的使用方法对于解决类似的问题非常重要。