Leetcode打卡：N皇后

执行结果：通过

题目：51 N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

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

提示：

• 1 <= n <= 9

代码以及解题思路

代码：

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:ans = []def dfs(i, a):if i == n: ans.append(['.' * j + 'Q' + '.' * (n - j - 1) for j in a])returnfor j in range(n):if all(j1 != j and j1 - i1 != j - i and j1 + i1 != j + i for i1, j1 in enumerate(a)):dfs(i + 1, a + [j])for i in range(n): dfs(1, [i])return ans

解题思路：

1. 初始化结果列表：
   • ans = []：用来存储所有满足条件的N皇后摆放方式。
2. 定义深度优先搜索函数 dfs(i, a)：
   • i：当前正在尝试放置皇后的行数（从1开始）。
   • a：一个列表，存储了到目前为止每一行皇后放置的列索引（从0开始）。
3. 递归终止条件：
   • if i == n:：当i等于n时，说明已经成功地在每一行都放置了一个皇后，此时将当前摆放方式添加到结果列表中。
   • ans.append(['.' * j + 'Q' + '.' * (n - j - 1) for j in a])：将当前摆放方式转换为字符串列表，每个字符串代表棋盘的一行，'Q'表示皇后，'.'表示空位。
4. 递归过程：
   • 遍历当前行的每一列j（从0到n-1）。
   • 检查当前列j是否安全，即是否不与之前放置的皇后冲突。
     • all(j1 != j and j1 - i1 != j - i and j1 + i1 != j + i for i1, j1 in enumerate(a))：检查当前列j和之前每一行放置的皇后j1是否在同一列、同一主对角线或同一副对角线上。
   • 如果安全，则递归调用dfs(i + 1, a + [j])，将当前列j添加到已放置皇后的列索引列表中，并尝试在下一行放置皇后。
5. 启动搜索：
   • 遍历第一行的每一列i（从0到n-1），作为搜索的起点，调用dfs(1, [i])开始搜索。
6. 返回结果：
   • 返回所有满足条件的N皇后摆放方式ans。

总结：

• 这段代码通过深度优先搜索（DFS）和回溯算法，尝试在N×N的棋盘上放置N个皇后，并记录所有满足条件的摆放方式。
• 通过递归和条件判断，确保每一行放置的皇后不与之前放置的皇后在同一列、同一主对角线或同一副对角线上。