n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊改览。
N皇后 II上圖為 8 皇后問題的一種解法并淋。
給定一個整數(shù) n刁憋，返回 n 皇后不同的解決方案的數(shù)量。
示例:
輸入: 4
輸出: 2
解釋: 4 皇后問題存在如下兩個不同的解法墓毒。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/n-queens-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有吓揪。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處蚁鳖。
與N皇后的解題一致磺芭，省掉了創(chuàng)建字符串
class Solution {
private int targetN; // n
private int resultCnt; // 解決方案的數(shù)量
private boolean[] columnChoice; // 已經(jīng)被選擇的列
private boolean[] leftSlant; // x-y=b,存儲b
private boolean[] rightSlant; // x+y=b,存儲b
public int totalNQueens(int n) {
targetN = n;
resultCnt = 0;
columnChoice = new boolean[targetN];
leftSlant = new boolean[targetN * 2];
rightSlant = new boolean[targetN * 2];
searchQueen(0);
return resultCnt;
}
private void searchQueen(int curRow) {
if (curRow == targetN) {
resultCnt ++;
return;
}
for (int i = 0; i < targetN; i++) {
// 滿足當(dāng)前列 && 對角線上
if (!columnChoice[i] && !leftSlant[curRow - i + targetN] && !rightSlant[curRow + i]) {
columnChoice[i] = true;
leftSlant[curRow - i + targetN] = true;
rightSlant[curRow + i] = true;
searchQueen(curRow + 1);
// 回退
columnChoice[i] = false;
leftSlant[curRow - i + targetN] = false;
rightSlant[curRow + i] = false;
}
}
}
}
運行效率
