生活随笔
收集整理的這篇文章主要介紹了
N皇后问题12 · N-Queens
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
［抄題］：
n皇后問題是將n個皇后放置在n*n的棋盤上，皇后彼此之間不能相互攻擊。
給定一個整數n，返回所有不同的n皇后問題的解決方案。
每個解決方案包含一個明確的n皇后放置布局，其中“Q”和“.”分別表示一個女王和一個空位置。
對于4皇后問題存在兩種解決的方案：
[
? ? [".Q..", // Solution 1
? ? ?"...Q",
? ? ?"Q...",
? ? ?"..Q."],
? ? ["..Q.", // Solution 2
? ? ?"Q...",
? ? ?"...Q",
? ? ?".Q.."]
]
?［思維問題］：
看不懂特殊情況：主要是要區別x y
［一句話思路］：
DFS去掉特殊情況后畫圖
［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：
［畫圖］：
［一刷］：
search函數可以是空類型，不返回search函數，返回其中的results即可。cols鏈表是后續函數的參數，此處需要新建鏈表。如果輔助鏈表cols滿了，需要在結果數組中添加畫圖，之后直接返回results。cols是數組，畫成圖才是鏈表drawCheesboard方法中，需要新建一個chessboard數組，作為最后返回的結果。?sb.append(j == cols.get(i) ? 'Q' : '.');表示j如果到達x有值處就打印Q判斷函數要有默認的return true?此函數判斷的是cols,column是否有效，因此全部行通過后返回true ［二刷］：
［三刷］：
［四刷］：
［五刷］：
? [五分鐘肉眼debug的結果]：
［總結］：
search函數用的DFS回溯是關鍵
［復雜度］：Time complexity: O(分支的深度次方) Space complexity: O(分支*深度)
［英文數據結構或算法，為什么不用別的數據結構或算法］：
DFS：找出全部方法
［其他解法］：
［Follow Up］：
［LC給出的題目變變變］：
Nqueen第二版，改參數不行 暫時算了吧
?[代碼風格] ：
規律：返回值和函數類型是相同的 class Solution {/*** Get all distinct N-Queen solutions* @param n: The number of queens* @return: All distinct solutions* For example, A string '...Q' shows a queen on forth position*/List<List<String>> solveNQueens(
int n) {List<List<String>> results =
new ArrayList<>
();if (n <= 0
) {return results;}search(results, new ArrayList<Integer>
(), n);return results;}/** results store all of the chessboards* cols store the column indices for each row*/private void search(List<List<String>>
results,List<Integer>
cols,int n) {if (cols.size() ==
n) {results.add(drawChessboard(cols));return;}for (
int colIndex = 0; colIndex < n; colIndex++
) {if (!
isValid(cols, colIndex)) {continue;}cols.add(colIndex);search(results, cols, n);cols.remove(cols.size() - 1
);}}private List<String> drawChessboard(List<Integer>
cols) {List<String> chessboard =
new ArrayList<>
();for (
int i = 0; i < cols.size(); i++
) {StringBuilder sb =
new StringBuilder();for (
int j = 0; j < cols.size(); j++
) {sb.append(j == cols.get(i) ? 'Q' : '.'
);}chessboard.add(sb.toString());}return chessboard;}private boolean isValid(List<Integer> cols,
int column) {int row =
cols.size();for (
int rowIndex = 0; rowIndex < cols.size(); rowIndex++
) {if (cols.get(rowIndex) ==
column) {return false;}if (rowIndex + cols.get(rowIndex) == row +
column) {return false;}if (rowIndex - cols.get(rowIndex) == row -
column) {return false;}}return true;}
} View Code ?
轉載于:https://www.cnblogs.com/immiao0319/p/8410050.html
總結
以上是生活随笔為你收集整理的N皇后问题12 · N-Queens的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
