八皇后問題(N皇后問題)

八皇后問題是一個經(jīng)典的遞歸回溯問題蜗字。

描述

八皇后問題是在一個 8*8 的棋盤上放置皇后,要求其放置后滿足同一行铅辞,同一列埋酬,同一對角線上沒有重復(fù)的皇后出現(xiàn)哨啃。試問有多少種擺盤方式?

思路

我們的主要思路是通過一行一行的放置皇后写妥,來使得每一行都有一個皇后拳球。當然,這些皇后在放置時都必須要滿足規(guī)定的要求才行珍特。

因此就會出先如下情況:

  • 放置時不符合規(guī)則祝峻,繼續(xù)檢索同一行的下一列位置是否合理
  • 如果符合規(guī)則就將其放置,然后進行下一行的嘗試(遞歸)
  • 如果有某一行沒有可行的解扎筒,則退回上一行莱找,消除上一行擺放的皇后,檢索剩余的列嗜桌,看是否有合理的位置奥溺,然后繼續(xù)進行。(回溯)
  • 直到所有的行都被放置為止骨宠。

需要注意的是浮定,我們在放置皇后時需要檢測其防止和理性的判斷條件為:

  1. 同一列的上方所有行中是否有皇后
  2. 左上方對角線上是否有皇后
  3. 右上方對角線上是否有皇后

算法實現(xiàn)

public class EightQueen {

    private static final int num = 8; // 可以拓展為N皇后問題
    private static int[][] item = new int[num][num];
    private static int methods = 0; // 總方法數(shù)

    public static void main(String[] args) {
        buildQueen(0);
        System.out.println(methods);
    }

    /**
     * 構(gòu)建棋盤的第row行
     *
     * @param row
     */
    private static void buildQueen(int row) {
        if (row == num) {
            methods++;
//            System.out.println("第" + methods + "種解法:");
//            for (int i = 0; i < num; i++) {
//                for (int j = 0; j < num; j++) {
//                    System.out.print(item[i][j] + " ");
//                }
//                System.out.print("\n");
//            }
            return;
        } else {
            for (int col = 0; col < num; col++) { // 每一列進行檢查相满,試探性放置
                if (isSatisfy(row, col)) {
                    item[row][col] = 1;
                    buildQueen(row + 1);
                    item[row][col] = 0;
                }
            }
        }
    }

    /**
     * 檢查row行col列元素是否滿足要求
     * 因為是一行行的放置皇后,所以不需要檢測同一行是否存在重復(fù)皇后
     * 在判斷重復(fù)元素時桦卒,只需要判斷上半部分的區(qū)域即可
     *
     * @param row
     * @param col
     * @return
     */
    private static boolean isSatisfy(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (item[i][col] == 1) { // 同一列的上方元素
                return false;
            }
        }
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) { // 左上方斜對角線
            if (item[i][j] == 1) {
                return false;
            }
        }
        for (int i = row, j = col; i >= 0 && j < num; i--, j++) { // 右上方斜對角線
            if (item[i][j] == 1) {
                return false;
            }
        }
        return true;
    }
}

優(yōu)雅的位運算解法

我們直接從一個例子來講解思路吧立美。先看看下圖的情況:


img1.jpeg

我們可以看到,前三行已經(jīng)放置了皇后方灾,我們需要在第四行選擇放置皇后的點建蹄。陰影部分表示會出現(xiàn)沖突的格子,而沖突我們主要分為三種:同列沖突迎吵、右下方?jīng)_突和左下方?jīng)_突躲撰。

而就這對這種情況而言(此例為八皇后問題,可拓展到N皇后)击费,一行剛好8個格子,對應(yīng)8位二進制數(shù)字桦他。因此我們可以首先定義沖突:

同列沖突: A = 1000 1001蔫巩;

右下沖突: B = 0001 0010;

左下沖突: C = 0010 0010快压;

其中1表示沖突的格子圆仔,0表示可以放置皇后的格子。因此我們可以輕松得出綜合的沖突情況:

D = (A | B | C) = 1011 1011蔫劣;

對于我們將要放置的第四行而言坪郭,現(xiàn)在有兩個0,意味著有兩個可以放置皇后的位置脉幢,我們需要將所有的情況都考慮到歪沃,這里有一個神奇的式子:bit = (D + 1) & ~D; 它計算得出的結(jié)果是: 0000 0100;

其實它能夠得到最右邊一個可以放置皇后的位置,并用1來表示嫌松,其余位是0沪曙。 這樣做是有好處的...

我們現(xiàn)在得出 bit = 0000 0100,便能夠輕松得到下一行的沖突 A' = (A | bit); B' = (B | bit) >> 1; C' = (C | bit) << 1; 便能夠很輕易地寫出遞歸式了萎羔。

而我們的第4行試探其實并沒有結(jié)束液走,只是從左向右的第一個可以放置的位置進行了試探,那想要取到第二個可以放置的位置怎么辦呢贾陷?很簡單缘眶,只需要做如下運算:

D = D + bit 將剛才試過的那一位設(shè)置為不能放置皇后狀態(tài),然后繼續(xù)做 bit = (D + 1) & ~D 即可髓废。

一直循環(huán)的試探巷懈,知道D 全部為1 為止。

下面是整個程序的代碼:

public class NQueen {

    private static final int N = 8; // 皇后數(shù)量瓦哎,可拓展為N皇后
    private static int count = 0; // 總方法數(shù)
    private static int limit;

    public static void main(String[] args) {
        limit = (1 << N) - 1;
        backtracking(0, 0, 0, 0);
        System.out.println(count);
    }

    private static void backtracking(int a, int b, int c, int depth) {
        if (depth == N) {
            count++;
            return;
        }
        int d = a | b | c;
        while (d < limit) {
            int bit = (d + 1) & ~d;
            backtracking(a | bit, limit & ((b | bit) >> 1), limit & ((c | bit) << 1), depth + 1);
            d |= bit;
        }
    }
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末砸喻,一起剝皮案震驚了整個濱河市柔逼,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌割岛,老刑警劉巖愉适,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異癣漆,居然都是意外死亡维咸,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進店門惠爽,熙熙樓的掌柜王于貴愁眉苦臉地迎上來癌蓖,“玉大人,你說我怎么就攤上這事婚肆∽飧保” “怎么了?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵较性,是天一觀的道長用僧。 經(jīng)常有香客問我,道長赞咙,這世上最難降的妖魔是什么责循? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮攀操,結(jié)果婚禮上院仿,老公的妹妹穿的比我還像新娘。我一直安慰自己速和,他們只是感情好歹垫,可當我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著健芭,像睡著了一般县钥。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上慈迈,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天若贮,我揣著相機與錄音,去河邊找鬼痒留。 笑死谴麦,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的伸头。 我是一名探鬼主播匾效,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼恤磷!你這毒婦竟也來了面哼?” 一聲冷哼從身側(cè)響起野宜,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎魔策,沒想到半個月后匈子,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡闯袒,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年虎敦,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片政敢。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡其徙,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出喷户,到底是詐尸還是另有隱情唾那,我是刑警寧澤,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布褪尝,位于F島的核電站通贞,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏恼五。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一哭懈、第九天 我趴在偏房一處隱蔽的房頂上張望灾馒。 院中可真熱鬧,春花似錦遣总、人聲如沸睬罗。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽容达。三九已至,卻和暖如春垂券,著一層夾襖步出監(jiān)牢的瞬間花盐,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工菇爪, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留算芯,地道東北人。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓凳宙,卻偏偏與公主長得像熙揍,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子氏涩,可洞房花燭夜當晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 我今天好不容易上了一次課届囚,然后數(shù)據(jù)結(jié)構(gòu)老師給我們留大作業(yè)有梆,喪心病狂,先解決一個叫八皇后的問題意系。 題目背景: 【問題...
    阿里高級軟件架構(gòu)師閱讀 2,990評論 1 5
  • 問題描述 n皇后問題是將n個皇后放置在n*n的棋盤上泥耀,皇后彼此之間不能相互攻擊(不同行,不同列昔字,不同對角線)爆袍。給定...
    Alfie20閱讀 618評論 0 0
  • 高中時我特別想離開家,在上課的時候就老走神作郭,腦子里全是“我要去流浪陨囊,我要去遠方”這種盲目的念頭。但...
    履善閱讀 354評論 0 2
  • 文/古 泉淵 字數(shù):2400左右夹攒,建議閱讀時間:4分鐘 01 冬與克爾凱郭爾 冬天忽然來了蜘醋,氣溫驟降,冷得直叫人哆...
    古泉淵閱讀 801評論 5 4
  • 文/創(chuàng)業(yè)人張涵 回顧自己這幾年的經(jīng)歷胎食,順風順水卻一無所得。有的時候真的非常沮喪允懂,有的時候卻又無比慶幸厕怜,這矛盾的兩極...
    dfbc10ae5419閱讀 316評論 0 3