算法（Java實作）-求解八皇後問題（回溯算法）

1、八皇後問題介紹

八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即：任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

2、 八皇後問題算法思路分析

1. 第一個皇後先放第一行第一列
2. 第二個皇後放在第二行第一列、然後判斷是否OK，如果不OK，繼續放在第二列、第三列、依次把所有列都放完，找到一個合适
3. 繼續第三個皇後，還是第一列、第二列……直到第8個皇後也能放在一個不沖突的位置，算是找到了一個正确解
4. 當得到一個正确解時，在棧回退到上一個棧時，就會開始回溯(即将第一個皇後放到第一列的所有正确解全部得到).
5. 然後回頭繼續第一個皇後放第二列，後面繼續循環執行 1,2,3,4的步驟

說明： 理論上應該建立一個二維數組來表示棋盤，但是實際上可以通過算法，用一個一維數組即可解決問題. 比如其中一個解法：arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}

arr[i] = val , val 表示第i+1個皇後，放在第i+1行的第val+1列

即：

a[0] = 0 ：表示第1個皇後放在第1行的第1列

a[1] = 4 ：表示第2個皇後放在第2行的第5列

a[2] = 7 ：表示第3個皇後放在第3行的第8列

（後面依次類推）

…

3、代碼實作

package com.zhukun.qunun8
public class Queue8 {
	//定義一個max表示共有多少個皇後
	int max = 8;
	//定義數組array, 儲存皇後放置位置的結果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} 
	int[] array = new int[max];
	static int count = 0;
	static int judgeCount = 0;
	public static void main(String[] args) {
		//測試一把 ， 8皇後是否正确
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.printf("一共有%d解法", count);
		System.out.printf("一共判斷沖突的次數%d次", judgeCount); // 1.5w	
	}
	//編寫一個方法，放置第n個皇後
	//特别注意： check 是 每一次遞歸時，進入到check中都有  for(int i = 0; i < max; i++)，是以會有回溯
	private void check(int n) {
		if(n == max) {  //n = 8 , 其實8個皇後就既然放好
			print();
			return;
		}	
		//依次放入皇後，并判斷是否沖突
		for(int i = 0; i < max; i++) {
			//先把目前這個皇後 n , 放到該行的第1列
			array[n] = i;
			//判斷當放置第n個皇後到i列時，是否沖突
			if(judge(n)) { // 不沖突
				//接着放n+1個皇後,即開始遞歸
				check(n+1); //  
			}
			//如果沖突，就繼續執行 array[n] = i; 即将第n個皇後，放置在本行得 後移的一個位置
		}
	}	
	//檢視當我們放置第n個皇後, 就去檢測該皇後是否和前面已經擺放的皇後沖突
	/**
	 * 
	 * @param n 表示第n個皇後
	 * @return
	 */
	private boolean judge(int n) {
		judgeCount++;
		for(int i = 0; i < n; i++) {
			// 說明
			//1. array[i] == array[n]  表示判斷 第n個皇後是否和前面的n-1個皇後在同一列
			//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判斷第n個皇後是否和第i皇後是否在同一斜線
			//（相當于把棋盤看做一個直角坐标系的話|y2-y1|=|x2-x1| 可判斷夾角為45度)
			// n = 1  放置第 2列 1 n = 1 array[1] = 1
			// Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
			//3. 判斷是否在同一行, 沒有必要，n 每次都在遞增
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
				return false;
			}
		}
		return true;
	}	
	//寫一個方法，可以将皇後擺放的位置輸出
	private void print() {
		count++;
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}

}
           

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解法一共判斷沖突的次數15720次
           

歡迎持續關注！

個人部落格站：jQueryZK Blog