本文轉載自:https://xie.infoq.cn/article/3d5174941484a82784d85624a
之前網上看到很多關于N皇后問題的解法，大都比較難懂也不易記住，今天分享下比較易懂的一個解法:
我們定義要求如下，給定一個n*n方格的棋盤，每一行放一個皇后，要求滿足任一皇后所在的列及斜邊上都不能有其他皇后存在，然后將所有解法列印出來，要求列印出n*n的字符矩陣，皇后的位置用“Q”表示，空格用“.”表示，拿4皇后來說，其中一個解如下圖，需要滿足的要求是行、列、斜邊上都不能有其他皇后存在，
理解了題目要求后，現在分析題目的解法，要求給出所有可能的解，需要從第一行開始，逐行、逐列求解滿足要求的行與列的序號，記錄下符合的解，最后按格式輸出，而每一次的判斷都需要依賴之前合法的皇后放置結果，第i+1行所有列執行判斷后，需要回到第i行，繼續第i行下一列的判斷，一個完整的解為當已經判斷到最后一行，而此時最后一行的第j列符合要求，則此時的記錄中為一個合法的解，直到所有行所有列的情況都判斷完成，求解結束，所以這個問題適合用深度優先遍歷的方式來解，從首行首列開始，優先向深度方向即向下一行搜索，下一行則遍歷各列，找到第一個符合要求的列后即再向下一行也就是深度方向搜索……
用偽代碼表示程序大致如下：
dfs (row) {
if (row == n) {
printOneSolver()
return;
}
for (col in n) {
if (valid(row, col) {
addToValidConditions(row, col)
dfs(row + 1）
removeFromValidConditions(row, col)
}
}
}
//說明：這里的row和col表明是與行列有關，真正的引數由行列引申而來，
上述偽碼描述了大致的程序，便于整體上理解思路，接下來介紹如何判斷合法性，先說行的判斷，因為每行只能放置一個皇后，又是以行為深度向下遍歷，所以一個合法的解其實只需要有n個列值資訊就可以表示，比如其中一個合法解的列值為[1, 3, 0, 2]（0表示第一列），這個解表示皇后放在第1行第2列，第2行第4列，第3行第1列，第4行第3列，因此行資訊是不需要單獨列出的，這個時候得出一個關鍵資料，就是用一個有序的資料結構來表示列，序號即為所在行，而該序號下的值為所在列，這個結構我們稱為cols，
行不需要單獨判斷，而列有了如上資料結構表示，那就剩下斜邊的判斷了，畫個圖來說明一下斜邊的判斷如何做，
以左上角為坐標原點，向下表示行，向右表示列，從圖上可以看到兩個斜邊其實是斜率為1和-1的兩條直線，而在不同的皇后位置的斜邊表示都是x+y=a和x-y=b的形式，a和b其實也就是截距，x和y就是行、列值，因此我們可以借助兩個資料結構分別表示目前已經被占用的斜邊，x+y的形式我們稱為xySum，而x-y的形式，我們就稱為xyDiff，
到目前我們得出合法的判斷條件就是當前列不在cols中且行列之和不在xySum中且行列之差不在xyDiff中，這里需要注意一點，當合法時要將條件放入這幾個結構，進行dfs，而dfs結束后，要還原為之前的狀態，以便進行下一列的判斷，這在偽代碼中也有說明，
最后說下結果的列印，按要求的方式列印時我們仍以其中一個解為例來說明，[1, 3, 0, 2]，對于該解其列印結果應為：
.Q.. ...Q Q... ..Q.
這里給出列序號如何拼接該行的輸出，如當前列值為1，則表示皇后在第2列（列號從0開始），那么在皇后之前就有1個“.”，然后是“Q”，再然后是n-列序號-1個“.”，用公式表示如下，col代表列序號：
".".repeat(col) + "Q" + ".".repeat(n - col - 1)
為了輸出后對于我們觀察更直觀，我們在字符后多加個空格，會更方便觀察，所以改為如下公式：
". ".repeat(col) + "Q " + ". ".repeat(n - col - 1) //輸出相應如下 . Q . . . . . Q Q . . . . . Q .
最后給出完整實作：
public void solveNQueens(int n) {
dfs(n, new ArrayList<>(), new HashSet<>(), new HashSet<>());
}
/**
* @param n 棋盤大小，也是皇后的數量
* @param cols 存放當前合法的列序號，其size的大小表示當前已經遍歷的行數
* 而其值正好是要進行遍歷的下一行
* @param xySum 行列之和，用Set存放
* @param xyDiff 行列之差，用Set存放
*/
private void dfs(int n, List<Integer> cols, Set<Integer> xySum, Set<Integer> xyDiff) {
//當cols.size為n時，表明每一行都可以合法放置一個皇后，得到一個合法解
if (cols.size() >= n) {
printOneSolver(cols);
return;
}
int row = cols.size();
for (int col = 0; col < n; col++) {
if (!cols.contains(col)
&& !xySum.contains(row + col)
&& !xyDiff.contains(row - col)) {
cols.add(col);
xySum.add(row + col);
xyDiff.add(row - col);
dfs(n, cols, xySum, xyDiff);
cols.remove(Integer.valueOf(col));
xySum.remove(Integer.valueOf(row + col));
xyDiff.remove(Integer.valueOf(row - col));
}
}
}
private void printOneSolver(List<Integer> cols) {
for (int i = 0; i < cols.size(); i++) {
System.out.println(". ".repeat(cols.get(i))
+ "Q "
+ ". ".repeat(cols.size() - cols.get(i) - 1));
}
System.out.println();
}
以4皇后為例，輸出如下：
. Q . . . . . Q Q . . . . . Q . . . Q . Q . . . . . . Q . Q . .
思路是這樣，如果更換資料結構和判斷的具體寫法，效率上可能會高一點，之前也有看過說N皇后問題用位運算解決會更高效，位運算的解法完成之后將作為相關主題補充在文章末尾，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24756.html
標籤：其他
上一篇：關于qt中的uchar
下一篇：求教qt 平滑滾動顯示圖片的問題