遞歸和回溯解決八皇後問題

一、題目

八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于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循環
		}
		
	}
}

           

四、結果