什么是八皇后問題？

八皇后問題是一個古老而著名的問題，它是回溯算法的典型案例。其問題的內(nèi)容是：在8x8格的國際棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問共有多少種擺法。

八皇后問題算法思路分析：

1、先把第一個皇后放在第一行第一列；
2、第二個皇后放在第二行第一列，然后判斷是否可行，如果可以，繼續(xù)放在第二列、第三列，依次把所有列都放完，找到一個合適的；
3、繼續(xù)放第三個皇后，還是從第一列、第二列…直到第八個皇后也能放在一個不沖突的位置上，這樣就找到了一個正確的解；
4、當?shù)玫揭粋€正確解時，在棧上回退到上一個棧，就會開始回溯，即將第一個皇后放在第一列的所有正確的解，都全部得到了；
5、然后繼續(xù)第一個皇后放第二列，后面繼續(xù)循環(huán)執(zhí)行1、2、3、4的步驟

代碼體現(xiàn)

public class EightQueens {//定義一個queens表示皇后的數(shù)量int queens = 8;//定義數(shù)組array，用于保存皇后位置擺放的結(jié)果：其中數(shù)組的下標表示排，數(shù)組下標對應的值表示列int[] array = new int[queens];static int count = 0;//用于記錄最終存在多少種解法static int judgeCount = 0;//用于記錄判斷沖突的次數(shù)public static void main(String[] args) {new EightQueens().check(0);System.out.printf("一共有%d種解法\n", count);//一共有92種解法System.out.printf("判斷沖突的次數(shù)共%d次", judgeCount);//判斷沖突的次數(shù)共15720次}/*** 該方法用于放置第n個皇后** @param n 表示第n個皇后*/private void check(int n) {if (n == queens) { //此時n=8，也就代表8個皇后都已經(jīng)放好了count++;print();return;}//依次放入皇后，判斷是否發(fā)生沖突for (int i = 0; i < queens; i++) {//先把當前這個皇后放到該行的第一列array[n] = i;//判斷當放置第n個皇后到第i列時，是否發(fā)生沖突if (judge(n)) {//不沖突，接著放n+1個皇后（即開始遞歸）check(n + 1);}//如果發(fā)生沖突，就繼續(xù)執(zhí)行array[n]=i,即將第n個皇后放在本行后移的一個位置}}/*** 用于檢測放置第n個皇后時，是否和前面已經(jīng)擺放好的皇后發(fā)生沖突** @param n 表示第n個皇后* @return*/private boolean judge(int n) {judgeCount++;for (int i = 0; i < n; i++) {//array[i] == array[n]：判斷第n個皇后是否和前面的n-1個皇后在同一列//Math.abs(n - i) == Math.abs(array[n] - array[i])：判斷第n個皇后是否和前面的n-1個皇后在同一對角線if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {return false;}}return true;}/*** 用于輸出皇后擺放好之后的位置*/private void print() {for (int i = 0; i < array.length; i++) {System.out.print(array[i] + "\t");}System.out.println();}
}

注：

通過最終的結(jié)果看到了判斷沖突的次數(shù)一共達到了1.5萬余次，相對而言效率不夠高，所以上訴代碼后期還需要繼續(xù)進行優(yōu)化！