最近接觸了數據結構與算法，這本該是計算機專業的同學大一就掌握的課程，可我現在才算正式接觸，感到慚愧萬分。但聞道有先后，術業有專攻。本篇博客開始記錄本人學習數據結構與算法這門課的點滴，希望自己能堅持下去，不要像記英語單詞書一樣，每次記到abandon就放棄了。

八皇后問題描述：在8*8的國際象棋棋盤中擺放8個皇后，使其不能相互攻擊，即：任意兩個皇后都不能處于同一行、同一列、同一斜線上，問有多少種解法？

思路分析：

1.第一個皇后先放在第一行的第一列；

2.第二個皇后放在第二行的第一列，然后判斷是否OK，如果不OK，則繼續放在第二列、第三列，依次把所有的列都放完，找到一個合適的列；

3.繼續第三個皇后，依然是第一列、第二列.....直到第8個皇后也能放在一個不沖突的位置，這算是找到了一個正確解；

4.當得到一個正確解時，在棧回退到上一個棧時，就會開始回溯（解釋參見文末配圖），即將第一個皇后放到第一行第一列的所有正確解全部得到為止；

5.然后回頭繼續第一個皇后放在第一行的第二列，后面繼續循環執行 1,2,3,4步驟

?

本文用一個一維數組進行求解（數組索引的妙用）

說明：用一個一維數組即可表示棋盤，例如?一種解法為：arr?=?{0,4,7,5,2,6,1,3}，對應的arr下標表示第?(下標+1)行，也表示第?(下標+1)個皇后；

如?arr[i]?=?val????表示?第(i+1)個皇后?放在第?(i+1)?行,?第?(val+1)?列；

在虛擬機中，引用類型的變量是存放在堆中的，因此在遞歸時，每個方法共享引用類型的變量，即?array

代碼如下：

//八皇后問題的解法 //說明：用一個一維數組即可表示棋盤，例如 一種解法為：arr = {0,4,7,5,2,6,1,3}，對應的arr下標表示第 (下標+1)行，也表示第 (下標+1)個皇后 //如 arr[i] = val 表示 第(i+1)個皇后 放在第 (i+1) 行, 第 (val+1) 列 //在虛擬機中，引用類型的變量是存放在堆中的，因此在遞歸時，每個方法共享引用類型的變量，即 array public class Queen8 {//定義一個max 表示一共有幾個皇后int max = 8;//定義一個數組array, 保持皇后放置位置的結果, 比如arr = {0,4,7,5,2,6,1,3}int[] array = new int[max];static int cnt = 0;public static void main(String[] args){Queen8 queen = new Queen8();queen.check(0); //表示從 第1個皇后開始放System.out.println("一共有解法： " + cnt);}//編寫一個方法，放置第n個皇后//注意：check是 每一次遞歸時，進入到check中都有一套循環 for(int i=0; i<max; i++)，因此會有回溯private void check(int n){//先寫遞歸退出條件if(n == max){ // n = 8 時，是第九個皇后，8個皇后已然放好print();return;}//再寫靠近遞歸退出的情況//依次放入皇后 ，并判斷是否沖突for(int i=0; i<max; i++){//先把當前皇后n ，放到該行的第1列（此時 i=0）array[n] = i;//判斷當放置第n個皇后到 i 列時，是否沖突if(judge(n)){ //說明返回true，與前面的位置不沖突//接著放第n+1個皇后，即開始遞歸check(n+1); //}//如果沖突（返回false，與前面的位置沖突），就繼續該循環，繼續執行array[n] = i ; 此時 i++了, 即將第n個皇后，放置在本行的后移的一個位置}}//查看當我們放置第 n 個皇后時，就去檢測該皇后是否和前面已經擺放的皇后沖突/*** * @param n 表示第n個皇后，也表示放在 第n+1行上* @return*/private boolean judge(int n){for(int i=0; i<n; i++){//說明：1.array[i] == array[n] 表示判斷 第 n 個皇后是否和前面 n-1 個皇后在同一列//2.Math.abs(n-i) == Math.abs(array[n]-array[i] 表示判斷 第 n 個皇后是否和第 i 個皇后在同一斜線，斜率//3.此算法，沒有必要判斷是否在同一列，因為數組索引表示行，肯定不在同一行，n每次都會遞增if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n]-array[i])){return false;}}return true;}//打印皇后位置private void print(){cnt++;for(int i=0; i<array.length; i++){System.out.print(array[i] + " ");}System.out.println();}}

最后一共有92種解法。

回溯解釋參考如下圖：

總結

以上是生活随笔為你收集整理的Java实现八皇后问题的解法（一维数组版本）的全部內容，希望文章能夠幫你解決所遇到的問題。

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