八皇后問(wèn)題

思路：

八個(gè)皇后互不沖突，即同一行同一列只能出現(xiàn)一位皇后。以行為標(biāo)準(zhǔn)，每一行只能放入一位皇后。可以使用一個(gè)一維數(shù)組來(lái)表示皇后的位置，一維數(shù)組的下表表示行數(shù)，一維數(shù)組中的元素表示列數(shù)。

int[] posQueen = new int[maxQueen];// posQueen = {0, 4, 7, 5, 2, 6, 1, 3} 表示在第一位皇后在第1行， 第1列；第二位皇后在第2行，第5列,以此類推...

當(dāng)放入第n位皇后時(shí)，前面（n-1）行已經(jīng)有皇后了，所以需要判斷第 n 位皇后是否與前（n-1）位沖突。所以需要有一個(gè)檢測(cè)沖突的函數(shù)：

//檢測(cè)第n個(gè)皇后是否和前面沖突private boolean check(int n) {for (int i=0; i<n; i++) {if (posQueen[n] == posQueen[i] //在同一列||Math.abs(n-i) == Math.abs(posQueen[n]-posQueen[i])) //在正、反對(duì)角線上{ return false;}}return true;}

寫(xiě)好了檢測(cè)沖突方法，就可以考慮開(kāi)始放入皇后了，在這里用遞歸可以找出所有的可行解：

//放置第n個(gè)皇后private void place(int n) {//檢測(cè)是否所有皇后已放好if (n==8) {count++;display();return;}//依次放入皇后，并判斷是否沖突for(int i=0; i<maxQueen; i++) {//先把當(dāng)前皇后放在第1列posQueen[n] = i;//判斷是否沖突if (check(n)) {//不沖突，進(jìn)入下一層place(n+1);} //沖突，檢查本行的下一個(gè)位置是否可行，即進(jìn)入for循環(huán)的下一位}}

以5皇后舉例說(shuō)明：

這個(gè)方法需要輸入當(dāng)前第幾個(gè)皇后正在被放置，在開(kāi)始時(shí)我們會(huì)輸入0（也就是放置第1位皇后）。

首先會(huì)檢測(cè)5位皇后是否已經(jīng)被放好，否，進(jìn)行下一步，將第1位皇后放在第1行的第1列上，用{0,0,0,0,0}表示此時(shí)的狀態(tài)；
然后判斷是否沖突，否，進(jìn)入下一層循環(huán)，放置第2位皇后；

先檢測(cè)5位皇后是否都被放好，否，將第2位皇后放在第2行第1列上，沖突；
將第2位皇后右移一位，放在第2行第2列上，沖突；
將第2位皇后右移一位，放在第2行第3列上，不沖突，此時(shí)狀態(tài)為{0,2,0,0,0}
進(jìn)入下一層循環(huán)，放置第3位皇后；

先檢測(cè)5位皇后是否都被放好，否，將第3位皇后放在第3行第1列上，沖突；
將第3位皇后右移一位，放在第3行第2列上，沖突；
…
將第3位皇后右移一位，放在第3行第5列上，不沖突，此時(shí)狀態(tài)為{0,2,4,0,0}
進(jìn)入下一層循環(huán)，放置第四位皇后；

同理，狀態(tài)為{0,2,4,1,0}，進(jìn)入下一層循環(huán)，放置第5位皇后；

同理，當(dāng)for循環(huán)到i=4時(shí)，狀態(tài)為{0,2,4,1,3}，第5位皇后不沖突，進(jìn)入下一層循環(huán)；

因?yàn)?位皇后都已經(jīng)被放置好，因此 if 檢測(cè)為 true，輸出第一組合理排列；
返回到上一層循環(huán)中，即回到第5步，并繼續(xù)第5步（因?yàn)樯弦淮蔚?步只檢查到第5行第4列）；

直接從for循環(huán)的i=5開(kāi)始，將第5位皇后放在第5行第5列上，沖突；
這一輪搜索結(jié)束，退回上一層，即第4步，從for循環(huán)的i=2開(kāi)始，重復(fù)上述過(guò)程；

直到返回第1步，從for循環(huán)的i=1開(kāi)始，重復(fù)第2-7步

最終會(huì)遍歷所有位置，找出所有的組合方式

圖解：

先從最后一行開(kāi)始遍歷；然后回到上一行，遍歷；直到回到第一行

完整代碼

public class Queen {//皇后的數(shù)量int maxQueen = 5;//皇后的位置數(shù)組，例：{0, 4, 7, 5, 2, 6, 1, 3}int[] posQueen = new int[maxQueen];//解法總數(shù)量int count = 0;//檢測(cè)第n個(gè)皇后是否和前面沖突private boolean check(int n) {for (int i=0; i<n; i++) {if (posQueen[n] == posQueen[i] || Math.abs(n-i) == Math.abs(posQueen[n]-posQueen[i])) {return false;}}return true;} //放置第n個(gè)皇后private void place(int n) {//檢測(cè)是否所有皇后已放好if (n==maxQueen) {count++;display();return;}//依次放入皇后，并判斷是否沖突, i表示當(dāng)前皇后放置在第n+1行第i+1列for(int i=0; i<maxQueen; i++) {//先把當(dāng)前皇后放在第1列posQueen[n] = i;//判斷是否沖突if (check(n)) {//不沖突，進(jìn)入下一層place(n+1);} //沖突，檢查本行的下一個(gè)位置是否可行，即進(jìn)入for循環(huán)的下一位}} //打印結(jié)果private void display() {System.out.println("第"+count+"種解法：");int[][] result = new int[posQueen.length][posQueen.length];for(int i=0; i<posQueen.length; i++) {result[i][posQueen[i]] = 1;for (int j=0; j<posQueen.length; j++) {System.out.print(result[i][j]+" ");}System.out.println(); }}public static void main(String[] args) {Queen queen = new Queen();queen.place(0);System.out.println(queen.maxQueen+"皇后問(wèn)題一共有"+queen.count+"種解法。");}}

相關(guān)章節(jié)
第一節(jié) 簡(jiǎn)述
第二節(jié) 稀疏數(shù)組 Sparse Array
第三節(jié) 隊(duì)列 Queue
第四節(jié) 單鏈表 Single Linked List
第五節(jié) 雙向鏈表 Double Linked List
第六節(jié) 單向環(huán)形鏈表 Circular Linked List
第七節(jié) 棧 Stack
第八節(jié) 遞歸 Recursion
第九節(jié) 時(shí)間復(fù)雜度 Time Complexity
第十節(jié) 排序算法 Sort Algorithm
第十一節(jié) 冒泡排序 Bubble Sort
第十二節(jié) 選擇排序 Select Sort
第十三節(jié) 插入排序 Insertion Sort
第十四節(jié) 冒泡排序，選擇排序和插入排序的總結(jié)
第十五節(jié) 希爾排序 Shell’s Sort
第十六節(jié) 快速排序 Quick Sort
第十七節(jié) 歸并排序 Merge Sort

總結(jié)

以上是生活随笔為你收集整理的算法与数据结构（Java解八皇后问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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