15.八皇后問題

1.八皇后問題介紹

image.png

2.思路分析

1.將第一個(gè)皇后放在第一行第一列
2.將第二個(gè)皇后放在第二行第一列,判斷與第一個(gè)皇后是否沖突升略,如果沖突屡限,將它放在第二列品嚣、第三列......直到找到不沖突的位置
3.將第三個(gè)皇后放在第三行第一列钧大,判斷是否沖突啊央,如果沖突眶诈,將它放在第二列瓜饥、第三列......直到找到不沖突的位置
4.之后幾列和2逝撬,3步驟相同宪潮,尋找一個(gè)正確解,如果找不到就將前一個(gè)皇后向后移一位狡相,重復(fù)1,2檩淋,3步驟

  1. 找到一個(gè)正確解后,從棧頂元素開始蟀悦,在這一行找其它位置不沖突的正確解氧敢,到棧底時(shí)就會(huì)找到第一個(gè)皇后放在第一行第一列的所有正確解

6.將第一個(gè)皇后放在第一行第二列,重復(fù)2浙炼,3唯袄,4,5步

注:這里我們用一個(gè)一維數(shù)組來存儲(chǔ)恋拷,數(shù)組中第一個(gè)元素表示第一個(gè)皇后放在第一行的第arr[0]+1列,第二個(gè)皇后放在第二行的第arr[1]+1列.......,第i個(gè)皇后放在第i行的第arr[i]+1列.arr[i] = val表示第i+1個(gè)皇后放在第i+1行第val+1列宴偿。

3.代碼實(shí)現(xiàn)

package com.yc.day03.recursion;

public class Queue8 {
    //定義皇后個(gè)數(shù)及數(shù)組
    int max = 8;
    int arr[] = new int[8];
    static int count = 0;
    static int judgeCount = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("共有%d種擺法\n",count);
        System.out.printf("共判斷了%d次",judgeCount);
    }
    /**
     *擺放皇后
     * */
    public void check(int n){

        if(n==max){//當(dāng)n==max時(shí)诀豁,是第九個(gè)皇后了,表示前八個(gè)皇后已經(jīng)擺放完成
            print();
            count++;
            return;
        }
        for (int i = 0; i < max; i++) {
            //將第n+1個(gè)皇后擺放在第n+1行第i+1列
            arr[n] = i;
            if(judge(n)){//如果不沖突娩践,擺放下一個(gè)皇后
                check(n+1);
            }
            //如果沖突了烹骨,將第n+1個(gè)皇后往后移arr[n]=i+1,由于這里i++,所以不用做操作直接進(jìn)入下次循環(huán)
        }
    }
    /**
     * 擺放第n+1個(gè)元素時(shí)判斷是否與前面所有元素沖突
     * */
    public boolean judge(int n){
        judgeCount++;
        for (int i = 0; i < n; i++) {
            /**
             * 說明:
             * 1.arr[i]==arr[n]用于判斷第n+1個(gè)皇后是否與第i+1個(gè)皇后在同一列
             * 2.Math.abs(n-i)==Math.abs(arr[n]-arr[i])用于判斷第n+1個(gè)皇后是否與第i+1個(gè)皇后在斜線上
             * */
            if(arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                return false;
            }
        }
        return true;
    }
    /**
     * 打印數(shù)組
     * */
    public  void print(){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末脸爱,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌络它,老刑警劉巖歪赢,帶你破解...
    沈念sama閱讀 217,826評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異点楼,居然都是意外死亡白对,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,968評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門蟀瞧,熙熙樓的掌柜王于貴愁眉苦臉地迎上來条摸,“玉大人,你說我怎么就攤上這事钉蒲。” “怎么了帆赢?”我有些...
    開封第一講書人閱讀 164,234評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵线梗,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我瘾婿,道長(zhǎng)烤咧,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,562評(píng)論 1 293
  • 正文 為了忘掉前任笛谦,我火速辦了婚禮昌阿,結(jié)果婚禮上饥脑,老公的妹妹穿的比我還像新娘。我一直安慰自己谣沸,他們只是感情好笋颤,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,611評(píng)論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著赋除,像睡著了一般非凌。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上清焕,一...
    開封第一講書人閱讀 51,482評(píng)論 1 302
  • 那天秸妥,我揣著相機(jī)與錄音,去河邊找鬼粥惧。 笑死,一個(gè)胖子當(dāng)著我的面吹牛起惕,可吹牛的內(nèi)容都是我干的咏删。 我是一名探鬼主播,決...
    沈念sama閱讀 40,271評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼嘀粱,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼辰狡!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起宛篇,我...
    開封第一講書人閱讀 39,166評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎偷卧,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體涯冠,經(jīng)...
    沈念sama閱讀 45,608評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡蛇更,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,814評(píng)論 3 336
  • 正文 我和宋清朗相戀三年赛糟,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片掌逛。...
    茶點(diǎn)故事閱讀 39,926評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡司倚,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出皿伺,到底是詐尸還是另有隱情盒粮,我是刑警寧澤鸵鸥,帶...
    沈念sama閱讀 35,644評(píng)論 5 346
  • 正文 年R本政府宣布妒穴,位于F島的核電站摊崭,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏呢簸。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,249評(píng)論 3 329
  • 文/蒙蒙 一嘿架、第九天 我趴在偏房一處隱蔽的房頂上張望啸箫。 院中可真熱鬧,春花似錦忘苛、人聲如沸唱较。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,866評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽汉形。三九已至倍阐,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間岔冀,已是汗流浹背概耻。 一陣腳步聲響...
    開封第一講書人閱讀 32,991評(píng)論 1 269
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留鞠柄,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,063評(píng)論 3 370
  • 正文 我出身青樓矫膨,卻偏偏與公主長(zhǎng)得像期奔,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子馁痴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,871評(píng)論 2 354

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