目錄

什么是八皇后

八皇后問題怎么解決？

什么是回溯法

回溯法的模板

八皇后問題的核心代碼

判斷皇后位置是否可行

總體實現(xiàn)代碼

每日一句：

種一棵樹的最好時間是十年前，其次是現(xiàn)在。

什么是八皇后

八皇后問題（英文：Eight queens），是由國際西洋棋棋手馬克斯·貝瑟爾于1848年提出的問題，是回溯算法的典型案例。

問題表述為：在8×8格的國際象棋上擺放8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。如果經(jīng)過±90度、±180度旋轉(zhuǎn)，和對角線對稱變換的擺法看成一類，共有42類。

八皇后問題怎么解決？

八皇后的解決辦法有很多種，我們這里采取回溯法解決。

什么是回溯法

回溯法的處理思想類似于枚舉搜索，我們枚舉出每一種情況，然后在根據(jù)條件進行篩選，找到滿足期望的值。我們把求解過程分為多個階段，每個階段我們都會面臨一個十字路口，我們隨便找一條路，走不通后，就回到上一個十字路口，選擇另一個十字路口進行下一步，知道遍歷完整個枚舉情況。

回溯法的模板

在面臨較簡單的回溯問題是可以使用以下模板

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }

    for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大?。? {
        處理節(jié)點;
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結(jié)果
    }
}

八皇后問題的核心代碼

int []Queen=new int[8];//存取皇后所在列的位置
    public void eightQueen(int row){

        if (row==8){//當(dāng)row等于8時說明八個皇后都放置好了
            printQueens(Queen);//打印八皇后
            return;
        }
        for (int column = 0; column < 8; column++) {
           if (isOk(row,column)){//這里判斷是否可以放在這個位置
               Queen[row]=column;//放置皇后
               eightQueen(row+1);
           }
        }
    }

?那么有小伙伴就迷惑了，八皇后不應(yīng)該是八行八列嗎，為什么數(shù)組只是一個一維數(shù)組。這里就用到了回溯法的思想，把八行八列分成了八行，每一行都獨立，而一維數(shù)組則只用來存取皇后的列坐標(biāo)，行坐標(biāo)由數(shù)組的下標(biāo)代替。

判斷皇后位置是否可行

public boolean isOk(int row,int column){
        int leftup=column-1,rightup=column+1;
        for (int i = row-1; i >=0 ; --i) {
            if (Queen[i]==column) return false;//看垂直方向是否有皇后
            if (leftup>=0){
                if (Queen[i]==leftup) return false;//看左上角斜線是否有皇后
            }
            if (rightup<8){
                if (Queen[i]==rightup) return false;//看右上角斜線是否有皇后
            }
            --leftup;
            ++rightup;
        }
        return true;
    }

判斷位置可行的條件是，是否存在有皇后處在同一列，同一行（同一行的情況不存在，因為row一直加1），同一斜線。?

那么判斷同一列我們只要看一維數(shù)組中是否有值與將要放置的皇后的列一致，如果一致我們?yōu)榕袛鄁alse;

那么如何判斷是否在同一條斜線，

假設(shè)一個點A AA的坐標(biāo)是[ a , b ] [a,b][a,b]，那么和該點在同一斜線上的點A 有四種,分別是
[ a + x , b + x ] 、 [ a ? x , b ? x ] 、 [ a + x , b ? x ] 、 [ a ? x , b + x ]?

而我們只考慮左右上角的位置是否存在同一條斜線,那么為什么不考慮下角是否存在呢，因為我們的皇后還沒排到左右下角，所以只考慮 [ a ? x , b + x ] 和[ a ? x , b ? x ]這兩種情況。

我們通過讓x等于1時來達到，當(dāng)處于同一斜線時，斜線分為四十五度，則行和列相等時，在同一斜線上，判斷為false.文章來源地址http://www.zghlxwxcb.cn/news/detail-405751.html

八皇后總體實現(xiàn)代碼

public static void main(String[] args) {
        Solution1 solution=new Solution1();
        solution.eightQueen(0);
    }
    int []Queen=new int[8];
    int count=0;
    public void eightQueen(int row){

        if (row==8){
            count++;
            printQueens(Queen);
            return;
        }
        for (int column = 0; column < 8; column++) {
           if (isOk(row,column)){

               Queen[row]=column;
               eightQueen(row+1);
           }
        }
    }
    public boolean isOk(int row,int column){
        int leftup=column-1,rightup=column+1;
        for (int i = row-1; i >=0 ; --i) {
            if (Queen[i]==column) return false;//看垂直方向是否有皇后
            if (leftup>=0){
                if (Queen[i]==leftup) return false;//看左上角斜線是否有皇后
            }
            if (rightup<8){
                if (Queen[i]==rightup) return false;//看右上角斜線是否有皇后
            }
            --leftup;
            ++rightup;
        }
        return true;
    }
    private void printQueens(int []Queen){
        for (int row = 0; row < 8; row++) {
            for (int column = 0; column < 8; column++) {
                if (Queen[row]==column) System.out.print("   Q   ");
                else System.out.print("   *   ");
            }
            System.out.println();
        }
        System.out.print(count);
        System.out.println();
    }
}

每日一句：

種一棵樹的最好時間是十年前，其次是現(xiàn)在。 ?

到了這里，關(guān)于八皇后問題（回溯法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！