參考博客:?https://blog.csdn.net/weixin_39651041/article/details/79972829

?

題目描述

NN皇后問題是指在N*NN?N的棋盤上要擺NN個皇后，
要求：任何兩個皇后不同行，不同列也不再同一條斜線上，
求給一個整數NN，返回NN皇后的擺法數。

?

示例1

輸入

1

返回值

1

示例2

輸入

8

返回值

92

?

思路如下:

?

? 由于N皇后問題不允許兩個皇后在同一行，所以，可用一維數組X表示N皇后問題的解，X[i]表示第i行的皇后所在的列號。例如一個滿足要求的四皇后棋盤布局如下圖所示，其結果X數組的值為：[2， 4， 1， 3]。

由上述X數組求解N皇后問題，保障了任意兩個皇后不在同一行上，而判定皇后彼此不受攻擊的其他條件，可以描述如下：

（1）X[i] = X[s]，則第i行與第s行皇后在同一列上。

（2）如果第i行的皇后在第j列，第s行皇后在第t列，即X[i] = j和X[s] = t，則只要i-j = s-t或者i+j = s+t，說明兩個皇后在同一對角線上。

對兩個等式進行變換后，得到結論：只要|i-s| = |j-t|（即i-s = X[i]-X[s]），則皇后在同一對角線上。

?

public class NqueenMe {int resultCount = 0;public static void main(String[] args) {//int[] queen = new int[8];NqueenMe nqueenMe = new NqueenMe();nqueenMe.Nqueen(9);System.out.println(nqueenMe.resultCount);}public int Nqueen (int n) {int[] queen = new int[n];tria(queen,0,n);return resultCount;}private void tria(int[]arr, int i, int n){if(i >= n){++resultCount;for (int j = 0; j < n; j++) {System.out.print(arr[j]+" ");}System.out.println();}else{for (int j = 0; j < n; j++) {arr[i] = j; // 第i行第j列if(place(arr, i)){// 結點滿足約束條件，則遞歸進入下一層繼續遍歷，否則跳過tria(arr, i+1, n);}}}}private boolean place(int[] arr, int s){// 判定s行X[s]位置上的皇后，與1至s-1行上各皇后的位置是否滿足約束條件for (int i = 0; i < s; i++) {// 同一列 或者 處于對角線if(arr[i] == arr[s] || (Math.abs(i-s) == Math.abs(arr[i] - arr[s]))){return false;}}return true;}}

?

?

?

總結

以上是生活随笔為你收集整理的常考数据结构与算法:N皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。