一、題目
八皇後問題,是一個古老而著名的問題,是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出:在8×8格的國際象棋上擺放八個皇後,使其不能互相攻擊,即:任意兩個皇後都不能處于同一行、同一列或同一斜線上,問有多少種擺法。
二、思路
使用遞歸和回溯解決該問題,并将結果儲存到長度為8的一維數組中。比如:[7, 3, 0, 2, 5, 1, 6, 4],意思是在8*8的棋盤上,第一行的棋子放在第7列,第二行的棋子放在第3列,第三行的棋子放在第2列以此類推。
三、源代碼
package recursion;
import java.util.Arrays;
public class Queen8 {
static int count = 0; //用于計算,統計有多少種可能的結果
static int max = 8; // 棋盤大小(全局變量)
static int[] chessBoard = new int[max]; // 棋盤(全局變量)
public static void main(String[] args) {
recurse(0);
}
/*
* 1. 列印八皇後每一種可能的結果
*/
public static void print() {
System.out.printf("第%d種可能的結果: " + Arrays.toString(chessBoard) + "\n", count);
}
/*
* 2. 檢查後面的象棋是否與前面的存在沖突,比如在同一列,或者某兩個在對角線上
*/
public static Boolean checkValidity(int index) {
for(int j=0;j<index;j++) {
// 如果在 同一列 或者在 對角線 上
if(chessBoard[j]==chessBoard[index]
|| Math.abs(chessBoard[index] - chessBoard[j]) == Math.abs(index-j)) {
return false;
}
}
return true;
}
/*
* 3. 運用遞歸和回溯實作列印所有可能的八皇後結果
*/
public static void recurse(int num) {
// 如果到了最後一步
if(num == max) {
count++;
print();
return;
}
for(int k=0;k<max;k++) {
chessBoard[num] = k;
// 如果符合條件,就遞歸下去
if(checkValidity(num)) {
recurse(num+1);
}
// 如果不符合條件,就繼續for循環
}
}
}