什么是八皇后問(wèn)題
八皇后問(wèn)題廊营，是一個(gè)古老而著名的問(wèn)題哼凯，是回溯算法的典型案例锌妻。該問(wèn)題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后盈包，使其不能互相攻擊沸呐，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上呢燥，問(wèn)有多少種擺法崭添。
代碼實(shí)現(xiàn)
package com.swh.data.recursion;
import com.alibaba.fastjson.JSON;
public class Queue8 {
/**
* 表示存放的皇后 數(shù)組元素的下標(biāo)表示存放的第幾個(gè)皇后也是第幾行皇后
* 數(shù)組元素中的值表示 皇后存放的第幾列
*/
int max = 8;
private int[] arrays = new int[max];
static int count = 0;
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.printf("一共有%d種排列方法",count);
}
/**
* n 表示第幾個(gè)房后
*
* @param n
*/
private void check(int n) {
if (n == max) { //n == 8 表示已經(jīng)開(kāi)始放第九個(gè)皇后(n 從0開(kāi)始) 說(shuō)明前八個(gè)已經(jīng)放好 也就是說(shuō)當(dāng)前這種放置方式已經(jīng)完成
print();
return;
}
for (int i = 0; i < max; i++) {
arrays[n] = i; // 把當(dāng)前的列設(shè)置到數(shù)組中
// 檢查放入的皇后是否與其他皇后沖突
if(!judge(n)){
check(n+1);
}
}
}
/**
* n 表示第幾個(gè)皇后
* 該方法用于判斷當(dāng)前第n個(gè)皇后 是否與前面幾個(gè)皇后有沖突
*
* @param n
* @return
*/
private boolean judge(int n) {
for (int i=0;i<n;i++){
/**
* 判斷第n個(gè)皇后是否跟之前的有沖突
* arrays[i]==arrays[n] 表示是否在同一列
* Math.abs(n-i)==Math.abs(arrays[n]-arrays[i])
* 表示是否在同一斜線上 Math.abs(n-i) 這個(gè)表示行的差距
* Math.abs(arrays[n]-arrays[i]) 這個(gè)表示列的差距
* 當(dāng)行的差距跟列的差距一致時(shí)，說(shuō)明在同一個(gè)斜線上
* 至于行 因?yàn)?n表示也同時(shí)表示第幾行的皇后 她與前面幾行的皇后進(jìn)行比較 肯定不會(huì)重復(fù)
*
*/
if(arrays[i]==arrays[n]||Math.abs(n-i)==Math.abs(arrays[n]-arrays[i])){
return true;
}
}
return false;
}
private void print() {
count++;
System.out.println(JSON.toJSONString(arrays));
}
}
執(zhí)行結(jié)果
[0,4,7,5,2,6,1,3]
[0,5,7,2,6,3,1,4]
[0,6,3,5,7,1,4,2]
[0,6,4,7,1,3,5,2]
[1,3,5,7,2,0,6,4]
[1,4,6,0,2,7,5,3]
[1,4,6,3,0,7,5,2]
[1,5,0,6,3,7,2,4]
[1,5,7,2,0,3,6,4]
[1,6,2,5,7,4,0,3]
[1,6,4,7,0,3,5,2]
[1,7,5,0,2,4,6,3]
[2,0,6,4,7,1,3,5]
[2,4,1,7,0,6,3,5]
[2,4,1,7,5,3,6,0]
[2,4,6,0,3,1,7,5]
[2,4,7,3,0,6,1,5]
[2,5,1,4,7,0,6,3]
[2,5,1,6,0,3,7,4]
[2,5,1,6,4,0,7,3]
[2,5,3,0,7,4,6,1]
[2,5,3,1,7,4,6,0]
[2,5,7,0,3,6,4,1]
[2,5,7,0,4,6,1,3]
[2,5,7,1,3,0,6,4]
[2,6,1,7,4,0,3,5]
[2,6,1,7,5,3,0,4]
[2,7,3,6,0,5,1,4]
[3,0,4,7,1,6,2,5]
[3,0,4,7,5,2,6,1]
[3,1,4,7,5,0,2,6]
[3,1,6,2,5,7,0,4]
[3,1,6,2,5,7,4,0]
[3,1,6,4,0,7,5,2]
[3,1,7,4,6,0,2,5]
[3,1,7,5,0,2,4,6]
[3,5,0,4,1,7,2,6]
[3,5,7,1,6,0,2,4]
[3,5,7,2,0,6,4,1]
[3,6,0,7,4,1,5,2]
[3,6,2,7,1,4,0,5]
[3,6,4,1,5,0,2,7]
[3,6,4,2,0,5,7,1]
[3,7,0,2,5,1,6,4]
[3,7,0,4,6,1,5,2]
[3,7,4,2,0,6,1,5]
[4,0,3,5,7,1,6,2]
[4,0,7,3,1,6,2,5]
[4,0,7,5,2,6,1,3]
[4,1,3,5,7,2,0,6]
[4,1,3,6,2,7,5,0]
[4,1,5,0,6,3,7,2]
[4,1,7,0,3,6,2,5]
[4,2,0,5,7,1,3,6]
[4,2,0,6,1,7,5,3]
[4,2,7,3,6,0,5,1]
[4,6,0,2,7,5,3,1]
[4,6,0,3,1,7,5,2]
[4,6,1,3,7,0,2,5]
[4,6,1,5,2,0,3,7]
[4,6,1,5,2,0,7,3]
[4,6,3,0,2,7,5,1]
[4,7,3,0,2,5,1,6]
[4,7,3,0,6,1,5,2]
[5,0,4,1,7,2,6,3]
[5,1,6,0,2,4,7,3]
[5,1,6,0,3,7,4,2]
[5,2,0,6,4,7,1,3]
[5,2,0,7,3,1,6,4]
[5,2,0,7,4,1,3,6]
[5,2,4,6,0,3,1,7]
[5,2,4,7,0,3,1,6]
[5,2,6,1,3,7,0,4]
[5,2,6,1,7,4,0,3]
[5,2,6,3,0,7,1,4]
[5,3,0,4,7,1,6,2]
[5,3,1,7,4,6,0,2]
[5,3,6,0,2,4,1,7]
[5,3,6,0,7,1,4,2]
[5,7,1,3,0,6,4,2]
[6,0,2,7,5,3,1,4]
[6,1,3,0,7,4,2,5]
[6,1,5,2,0,3,7,4]
[6,2,0,5,7,4,1,3]
[6,2,7,1,4,0,5,3]
[6,3,1,4,7,0,2,5]
[6,3,1,7,5,0,2,4]
[6,4,2,0,5,7,1,3]
[7,1,3,0,6,4,2,5]
[7,1,4,2,0,6,3,5]
[7,2,0,5,1,4,6,3]
[7,3,0,2,5,1,6,4]
一共有92種排列方法
