執(zhí)行結(jié)果：通過

題目：51 N皇后

按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n?皇后問題?研究的是如何將?n?個(gè)皇后放置在?n×n?的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個(gè)整數(shù)?n?，返回所有不同的?n?皇后問題?的解決方案。

每一種解法包含一個(gè)不同的?n 皇后問題?的棋子放置方案，該方案中?'Q'?和?'.'?分別代表了皇后和空位。

示例 1：

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋：如上圖所示，4 皇后問題存在兩個(gè)不同的解法。

示例 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. 初始化結(jié)果列表：
   • ans = []：用來存儲(chǔ)所有滿足條件的N皇后擺放方式。
2. 定義深度優(yōu)先搜索函數(shù)?dfs(i, a)：
   • i：當(dāng)前正在嘗試放置皇后的行數(shù)（從1開始）。
   • a：一個(gè)列表，存儲(chǔ)了到目前為止每一行皇后放置的列索引（從0開始）。
3. 遞歸終止條件：
   • if i == n:：當(dāng)i等于n時(shí)，說明已經(jīng)成功地在每一行都放置了一個(gè)皇后，此時(shí)將當(dāng)前擺放方式添加到結(jié)果列表中。
   • ans.append(['.' * j + 'Q' + '.' * (n - j - 1) for j in a])：將當(dāng)前擺放方式轉(zhuǎn)換為字符串列表，每個(gè)字符串代表棋盤的一行，'Q'表示皇后，'.'表示空位。
4. 遞歸過程：
   • 遍歷當(dāng)前行的每一列j（從0到n-1）。
   • 檢查當(dāng)前列j是否安全，即是否不與之前放置的皇后沖突。
     • all(j1 != j and j1 - i1 != j - i and j1 + i1 != j + i for i1, j1 in enumerate(a))：檢查當(dāng)前列j和之前每一行放置的皇后j1是否在同一列、同一主對(duì)角線或同一副對(duì)角線上。
   • 如果安全，則遞歸調(diào)用dfs(i + 1, a + [j])，將當(dāng)前列j添加到已放置皇后的列索引列表中，并嘗試在下一行放置皇后。
5. 啟動(dòng)搜索：
   • 遍歷第一行的每一列i（從0到n-1），作為搜索的起點(diǎn)，調(diào)用dfs(1, [i])開始搜索。
6. 返回結(jié)果：
   • 返回所有滿足條件的N皇后擺放方式ans。

總結(jié)：

• 這段代碼通過深度優(yōu)先搜索（DFS）和回溯算法，嘗試在N×N的棋盤上放置N個(gè)皇后，并記錄所有滿足條件的擺放方式。
• 通過遞歸和條件判斷，確保每一行放置的皇后不與之前放置的皇后在同一列、同一主對(duì)角線或同一副對(duì)角線上。