一、八皇后問題簡介

? 八皇后問題，一個(gè)古老而著名的問題，是回溯算法的典型案例。該問題由國際西洋棋棋手馬克斯·貝瑟爾于 1848 年提出：在 8×8 格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為有 76 種方案。1854 年在柏林的象棋雜志上不同的作者發(fā)表了 40 種不同的解，后來有人用圖論的方法解出 92 種結(jié)果。

如下圖是它的一種解法

二、解決思路

采用遞歸回溯的方法解決。

先做如下約定

• 我們用ways[8]，這個(gè)數(shù)組存儲擺放皇后的方式，其中，下標(biāo)表示第幾行，對應(yīng)的值表示皇后所在的列
• judge(int n) 表示判斷正在放置的第n個(gè)皇后，是否會與之前擺放好的皇后存在列沖突與對角線沖突（默認(rèn)皇后不擺放在一行）
• putQueen(int n) 該方法為遞歸的調(diào)用放置皇后的方法，若出現(xiàn)沖突則回溯。

具體步驟：

1. 先在第一行第一列放置第一個(gè)皇后，然后，再第二行放置第二個(gè)皇后，若與現(xiàn)有皇后站位不沖突，則繼續(xù)在第三行放置第三個(gè)皇后......
2. 如果發(fā)現(xiàn)沖突，則調(diào)整列，直到所有列均試完，若發(fā)現(xiàn)可以放置，則繼續(xù)放置下一行，直至八個(gè)皇后均擺放完畢，如果，所有的列均與現(xiàn)有皇后的站位沖突則，回溯至上一行，繼續(xù)遍歷上一行的各列，以此類推，直到將第一行的各列均遍歷完畢，就得到所有的結(jié)果。

三、代碼實(shí)現(xiàn)

/**
 * @author ymy
 * @date 2020/5/12
 *
 * 八皇后問題：
 *      在8*8的棋盤上，放置八個(gè)皇后，
 *      要求這八個(gè)皇后的任意兩個(gè)不在同一行，同一列，同一斜線
 */
public class EightQueens {

    private int queenNum = 8;//皇后數(shù)量
    private static int WAYS_NUM;
    private int [] ways=new int [8];//放置方法
    private static int judgeNums;

    /**
     * @param n 表示正在放置的第n個(gè)皇后
     * @return
     * 因?yàn)閣ays存儲的含義就不包括同一行，所以只需要判斷是否在同一列或者同一斜線即可。
     */
    public boolean jugde(int n){
        judgeNums++;
        for (int i = 0; i <n ; i++) {
            //  同一行               同一列（參考正方形對角線）
            if (ways[i]==ways[n] || Math.abs(ways[i]-ways[n])==Math.abs(i-n)){
                return false;
            }
        }
        return true;
    }

    public void print(){
        WAYS_NUM++;
        System.out.printf("這是第%d種方法：",WAYS_NUM);
        for (int a:ways){
            System.out.print(a+" ");
        }
        System.out.println();
    }

    /**
     * @param n 放置的第n個(gè)皇后
     */
    public void putQueen(int n){
        if (n==queenNum){
            print();
            return;
        }
        for (int i=0;i<queenNum;i++){
            ways[n]=i;
            if (jugde(n)){
                putQueen(n+1);
            }
        }
    }

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.putQueen(0);
        System.out.println("判斷次數(shù)："+judgeNums);
    }

}

四、測試結(jié)果