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

上圖為 8 皇后問題的一種解法。

給定一個(gè)整數(shù)?n，返回?n?皇后不同的解決方案的數(shù)量。

示例:

輸入: 4 輸出: 2 解釋: 4 皇后問題存在如下兩個(gè)不同的解法。 [[".Q..", ?// 解法 1"...Q","Q...","..Q."],["..Q.", ?// 解法 2"Q...","...Q",".Q.."] ]

class Solution {/*** 記錄某列是否已有皇后擺放*/private boolean col[];/*** 記錄某條正對(duì)角線（左上右下）是否已有皇后擺放（某條對(duì)角線對(duì)應(yīng)的擺放位置為 x - y + n - 1）*/private boolean dia1[];/*** 記錄某條斜對(duì)角線（左下右上）是否已有皇后擺放（某條對(duì)角線對(duì)應(yīng)的擺放位置為 x + y）*/private boolean dia2[];public int totalNQueens(int n) {// 依然可以使用 51 號(hào)問題的解決思路，但問題是有沒有更好的方法col = new boolean[n];dia1 = new boolean[2 * n - 1];dia2 = new boolean[2 * n - 1];return putQueen(n, 0);}/*** 遞歸回溯方式擺放皇后** @param n 待擺放皇后個(gè)數(shù)* @param index 已擺放皇后個(gè)數(shù)*/private int putQueen(int n, int index) {int res = 0;if (index == n) {return 1;}// 表示在 index 行的第 i 列嘗試擺放皇后for (int i = 0; i < n; i++) {if (!col[i] && !dia1[i - index + n - 1] && !dia2[i + index]) {// 遞歸col[i] = true;dia1[i - index + n - 1] = true;dia2[i + index] = true;res += putQueen(n, index + 1);// 回溯col[i] = false;dia1[i - index + n - 1] = false;dia2[i + index] = false;}}return res;}public static void main(String[] args) {int n = new Solution().totalNQueens(8);System.out.println(n);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/JAYPARK/p/10603112.html

總結(jié)

以上是生活随笔為你收集整理的力扣——N皇后II的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。