八皇后問題，是一個古老而著名的問題，是回溯演算法的典型案例，該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在 8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即：任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法(92)，
思路
-
將第一個皇后放在第一行第一列
-
將第二個皇后放在第二行第一列，判斷是否會和其他皇后相互攻擊，若會相互攻擊，則將其放到第三列、第四列…知道不會相互攻擊為止
-
將第三個皇后放在第三行第一列，判斷是否會和其他皇后相互攻擊，若會相互攻擊，則將其放到第三列、第四列…知道不會相互攻擊為止，并以此類推，在擺放的程序中，有可能會改動前面所放的皇后的位置
-
當得到一個正確的解時，就會回溯到上一行，由此來找出第一個皇后在第一行第一列的所有解
-
再將第一個皇后放到第一行第二列，并重復以上四個步驟
-
注意：
- 棋盤本身應該是用二維陣串列示，但是因為皇后所在的行數是固定的，所以可以簡化為用一個一維陣列來表示，其中的值代表皇后所在的列
- 陣列下標代表皇后所在行數，所以判斷是否在同一行列斜線上時，只需要判斷是否在同一列和同一斜線上即可
- 是否同列判斷：值是否相同
- 是否同一斜線：行號-行號是否等于列號-列號，且列號相減要取絕對值
代碼
public class Queen8 {
int max = 8;
int[] arr = new int[max];
static int count = 0;
public static void main(String[] args) {
Queen8 queen8 = new Queen8();
queen8.check(0);
System.out.printf("一共有%d種解法",count);
}
/**
* 檢查該皇后應放的位置
* @param n 要檢查的皇后
*/
private void check(int n){
if (n == max){//所有的皇后都放好了，列印并回傳
print();
return;
}
//把皇后放在每一列上，看哪些不會和之前的沖突
for (int i = 0; i < max; i++){
//把第queen+1個皇后放在第i列
arr[n] = i;
if (judge(n)){
//不沖突，就去放下一個皇后
check(n + 1);
}
}
}
/**
* 判斷該位置的皇后與前面幾個是否沖突
* @param n 需要判斷的皇后的位置
* @return true代表不沖突，false代表沖突
*/
private boolean judge(int n){
for (int i = 0; i < n; i++){
//如果兩個皇后在同一列或者同一斜線，就沖突
//因為陣列下標代表行數，所以不會存在皇后在同一行
//所在行數-所在行數 如果等于 所在列數-所在列數，則兩個皇后在同一斜線上
if (arr[n] == arr[i] || (n - i) == Math.abs(arr[n] - arr[i])){
return false;
}
}
return true;
}
/**
* 列印陣列元素
*/
private void print(){
count++;//count每加一次說明多了一種解法
for (int i = 0; i < arr.length; i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
這里僅測驗了最后一種解法，發現沒有問題
本文來自博客園，作者：腹白，轉載請注明原文鏈接：https://www.cnblogs.com/wyh518/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511042.html
標籤：其他
下一篇：常見的排序演算法與時間復雜度