原文鏈接:傳送門

八皇后問題

八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即：任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

八皇后問題算法思路分析

1. 第一個皇后先放第一行第一列
2. 第二個皇后放在第二行第一列、然后判斷是否OK， 如果不OK，繼續放在第二列、第三列、依次把所有列都放完，找到一個合適
3. 繼續第三個皇后，還是第一列、第二列……直到第8個皇后也能放在一個不沖突的位置，算是找到了一個正確解
4. 當得到一個正確解時，在棧回退到上一個棧時，就會開始回溯，即將第一個皇后，放到第一列的所有正確解，全部得到.
5. 然后回頭繼續第一個皇后放第二列，后面繼續循環執行 1,2,3,4的步驟 【示意圖】

說明

理論上應該創建一個二維數組來表示棋盤，但是實際上可以通過算法，用一個一維數組即可解決問題. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //對應arr 下標 表示第幾行，即第幾個皇后，arr[i] = val , val 表示第i+1個皇后，放在第i+1行的第val+1列

使用到回溯算法

高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，后來有人用圖論的方法解出92種結果。計算機發明后，有多種計算機語言可以解決此問題

package com.atguigu.recursion;public class Queen8 {// 一共有多少個皇后（此時設置為8皇后在8X8棋盤）int max = 8;// 該數組保存結果，第一個皇后擺在array[0]列，第二個擺在array[1]列int[] array = new int[max];static int count = 0;public static void main(String[] args) {Queen8 queen8 = new Queen8();queen8.check(0);System.out.println("一共有" + count + "種解法");}/*** n代表當前是第幾個皇后 [n 是從 0 開始算的，即0 表示第一個皇后, 同時n也表示第幾行]* 即 第1行是第一個皇后(n=0)，第2行是第二個皇后(n=1), 第8行是第8個皇后(n=7)，如果遍歷到第9行(n=8)，說明* 皇后全部放置好了, 就相應的得到了一種解法...* 然后回溯 ，又將第一個皇后，放置第1行的第2列...** @param n 皇后n在array[n]列*/private void check(int n) {//終止條件是最后一行已經擺完，//由于每擺一步都會校驗是否有沖突，//所以只要最后一行擺完，說明已經得到了一個正確解if (n == max) {print();return;}//將第n個皇后從.第一列開始放值，然后判斷是否和本行本列本斜線有沖突，如果OK，就進入下一行的邏輯for (int i = 0; i < max; i++) {array[n] = i; //先將第一個皇后放置第一行的第一列 array[0] = 0if (judge(n)) {  // 如果 該皇后沒有和其它皇后沖突check(n + 1); // 放第二個皇后，因為是遞歸，因此大家可以思考，第二個皇后是從 第二行的第1列開始放}}}/*** 查看n皇后是否滿足約束條件(即：檢查皇后n是否會發生沖突)* 如果沖突，返回 false , 如果不沖突返回true* 0 4 7 5 2 6 1 3** @param n* @return*/private boolean judge(int n) {for (int i = 0; i < n; i++) {//說明: //1. array[i] == array[n] 判斷 是不是在同一列//2. Math.abs(n - i) == Math.abs(array[n] - array[i]) 判斷是不是在同一條斜線//3. 不用判斷是不是在同一行，因為我們每放一個皇后，行是遞增的.if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {return false;}}return true;}/*** 打印這個滿足條件的八皇后的放置位置*/private void print() {count++;for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}System.out.println();}
}

判斷斜線的時候,直接用 橫坐標減去縱坐標,若,兩個位置的差值相等,

就是同一個斜線上的

然而,這個上面例子中,存放的方式是:

一維數組: 數組的下標代表棋盤的行號,數組的值代表棋盤的列號

數組中員孫的個數即為 皇后的 棋子

在記性斜線判斷的時候,計算的是,兩點的橫向差值和縱向差值是否相等,若相等,則,斜率為1,即tan45° 嗯, 就判斷出了是在一個斜線上,皇后能夠互相攻擊,嗯,哦可,秒啊

原文鏈接:傳送門