問題
image
八皇后問題物臂，是一個古老而著名的問題蛙讥，是回溯算法的典型案例候醒。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊哼绑，即：任意兩個皇后都不能處于同一行岩馍、同一列或同一斜線上，問有多少種擺法抖韩。
思路分析
- 第一個皇后先放第一行第一列
- 第二個皇后放在第二行第一列蛀恩、然后判斷是否OK[即判斷是沖突]， 如果不OK茂浮，繼續(xù)放在第二列双谆、第三列、依次把所有列都放完席揽，找到一個合適
- 繼續(xù)第三個皇后佃乘，還是第一列、第二列……直到第8個皇后也能放在一個不沖突的位置驹尼，算是找到了一個正確解
- 當?shù)玫揭粋€正確解時趣避，在棧回退到上一個棧時新翎，就會開始回溯程帕，即將第一個皇后，放到第一列的所有正確解地啰，全部得到.
- 然后回頭繼續(xù)第一個皇后放第二列愁拭，后面繼續(xù)循環(huán)執(zhí)行 1,2,3,4的步驟。
注意點:
說明：理論上應該創(chuàng)建一個二維數(shù)組來表示棋盤亏吝，但是實際上可以通過算法岭埠，用一個一維數(shù)組即可解決問題. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //對應arr 下標 表示第幾行，即第幾個皇后，arr[i] = val , val 表示第i+1個皇后惜论，放在第i+1行的第val+1列许赃。
代碼演示
/**
* @author 曾鑫曜(xinyao.zeng @ ucarinc.com)
* @version 1.0
* @description:
* @since 2019/9/18 13:31
*/
public class Queue8 {
//定義一個MAX常量表示一共有多少個皇后
private static final int MAX = 8;
//定義一個數(shù)組Array，保存皇后放置的結(jié)果馆类，比如: arr={ 0,4,7,5,2,6,1,3 } 該數(shù)組的下標表示第幾行混聊，具體的值表示第幾列。
int[] arr = new int[MAX];
//一共多少種解法
static int count = 0;
//一共判斷多少次乾巧，
static int judgeCount = 0;
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.println("八皇后問題解法總數(shù):"+count);
System.out.println("八皇后問題執(zhí)行次數(shù)："+judgeCount);
}
/**
* 這個方法用于表示放置第N個皇后句喜，依次是第一行表示第一個，第二個表示第二個這樣的思路.
*
* 過程:
* 1.如果放置的是最后一個沟于，則直接打印咳胃， 因為只有等于8的時候，表示是都放完了旷太。
* 否則
* 1.因為是從第N個開始放拙绊，我們的設計就是從第N行開始計算，遍歷8次泳秀，每次代表放在第N行的第幾列
* 2.判斷是否沖突标沪，
* 3.如果沒有沖突繼續(xù)放下一行，直到放到最后一行完成嗜傅。否則會進行回溯
*
* @param n
*/
private void check(int n) {
//如果為最后一個金句，則打印數(shù)組，同時吕嘀，返回null;
if(n == MAX){
print();
return;
}
//否則從第N行的第1個位置開始存放皇后违寞，遍歷存放皇后
for(int i=0;i<MAX;i++){
//遍歷存放
arr[n]=i;
//判斷與之前是否有沖突。
if(judge(n)) {
//如果不沖突偶房，接著N+1趁曼，開始遞歸
check(n+1);
}
//如果沖突，繼續(xù)執(zhí)行array[n]=i,即將第n個皇后放置到本行最后一個位置
}
}
/**
* 查看我們放置導的第N個皇后棕洋，就去檢測該皇后是否與前面的拜訪沖突
* @param n 表示第n個皇后
* @return
*/
private boolean judge(int n) {
judgeCount++;
//n表示與之前的n次對比挡闰，是否有沖突
for(int i=0; i < n; i++) {
/**
* arr[i] == arr[n] 判斷是否有皇后與之前的在同一列
*
* Math.abs(n-i) == Math.abs(arr[n] - arr[i]) 判斷是否有皇后與之前的皇后在同一斜線上。
* 判斷依據(jù)取決于我們的設計: 我們設計每一個皇后的位置在數(shù)組的索引表示行掰盘，數(shù)組的所在索引的值表示第幾列摄悯。該方式可以計算是否在同一斜線上。
*
* 因為每次檢查必定不會在同一行愧捕，因此不需要檢查同一行的情況奢驯，可以看上面的計算思路
*/
if(arr[i] == arr[n] || Math.abs(n-i) == Math.abs(arr[n] - arr[i])){
return false;
}
}
return true;
}
//寫一個方法，可以將皇后擺放的位置輸出
private void print(){
count++;
System.out.println(Arrays.toString(arr));
}
}
計算結(jié)果:
image
image
結(jié)果分析:
- 解法總量一共有92種
- 執(zhí)行次數(shù)達一萬5千多次效率很低(推薦使用貪心算法改進)
- 開上圖圈起部分次绘，看這兩個例子
image
可知瘪阁，如果執(zhí)行到上圖中第一行撒遣，這時候會回到第七行中第五列，繼續(xù)判斷是否有沖突管跺，如果有义黎，則繼續(xù)回到第六行，繼續(xù)遍歷又有沖突伙菜，直到回溯到第四行開始，這是放入第4列命迈，才發(fā)現(xiàn)沒有沖突后贩绕，會繼續(xù)遞歸執(zhí)行。
