回溯法(排列樹(shù))解決八(N)皇后問(wèn)題

問(wèn)題描述:



八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題:如何能夠在8×8的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后,使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后渗磅?為了達(dá)到此目的焕梅,任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上攻泼。八皇后問(wèn)題可以推廣為更一般的n皇后擺放問(wèn)題:這時(shí)棋盤(pán)的大小變?yōu)閚×n,而皇后個(gè)數(shù)也變成n。當(dāng)且僅當(dāng)n = 1或n ≥ 4時(shí)問(wèn)題有解凤藏。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ---------來(lái)自<維基百科>

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?



? ? ? 個(gè)人思路:

max表示n個(gè)皇后 用array[n]表示皇后在第n+1行,array[n]列,比如array[0] = 8 意思為:該皇后位于第1行第8列的坐標(biāo);


排列樹(shù)與子集樹(shù)的區(qū)別在于子集樹(shù)不需要初始化而排列樹(shù)需要,此初始化內(nèi)容為眾多可能解集合(注:是可能解,不一定為正確解)中的一個(gè)


初始化為a[]數(shù)組(1-n隨意排列);


將a數(shù)組的值向array中輸出,初始傳入n為0;表示該皇后在第一行,但具體哪列不確定,此時(shí)初始化的a數(shù)組就起到了作用,a[n]表示在n+1行的第a[n]列, 將其賦值給array,即: array[n] = a[i];


(因?yàn)閍[]中只是可能性,所以要將所有可能性用for循環(huán)表示.即:for(int i = n;i < max ; i++);


然后更新a數(shù)組 swap(a,n,i) (意為 既然已經(jīng)使用過(guò)a[i]那就用原本的a[n]替換a[i] 保證列值不重復(fù))


更新后判斷該位置是否與已經(jīng)存在的皇后的位置沖突(同斜線) 已經(jīng)通過(guò)a數(shù)組和n已經(jīng)去除掉同行同列的可能;n保證不同行,a[i]保證不同列;


如果合法,則進(jìn)入n+1;重復(fù)討論n+2個(gè)皇后的位置 /如果不合法,交換回之前位置(只有合法之后才能占該列值) i++;


當(dāng)i++到for循環(huán)結(jié)束,也就是說(shuō)該皇后在這一行所有列中都沒(méi)有找到合適自己的位置,回退,即該方法執(zhí)行結(jié)束,重新討論之前上個(gè)皇后的位置;


代碼如下:

? ? ?

public class NQueen {


int max = 8;

int array[] = new int[max];

int[] a = { 8, 2, 3, 4, 5, 6, 7, 1 };


public void backtrack(int n) {

if (n == max) {

? print();

? return;

} else {

? for (int i = n; i < max; i++) {

? array[n] = a[i];

? swap(a, n, i);

? if (nice(n)) {

? ? backtrack(n + 1);

? }

? swap(a, n, i);

? }

}


}


public boolean nice(int n) {

for (int i = 0; i < n; i++) {

? if (Math.abs(n - i) == Math.abs(array[n] - array[i])) {

? return false;

? }

}

return true;

}


public void swap(int[] a, int i, int j) {

int tem = a[i];

a[i] = a[j];

a[j] = tem;

}


int k = 0;


public void print() {

++k;

System.out.print("第" + k + "種解法:");

for (int i = 0; i < array.length; i++) {

? System.out.print(array[i] + " ");

}

System.out.println();

}


public static void main(String[] args) {


new NQueen().backtrack(0);

}

}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市堕伪,隨后出現(xiàn)的幾起案子揖庄,更是在濱河造成了極大的恐慌,老刑警劉巖欠雌,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件蹄梢,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡富俄,警方通過(guò)查閱死者的電腦和手機(jī)禁炒,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)而咆,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人幕袱,你說(shuō)我怎么就攤上這事暴备。” “怎么了们豌?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵涯捻,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我玛痊,道長(zhǎng)汰瘫,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任擂煞,我火速辦了婚禮混弥,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘对省。我一直安慰自己蝗拿,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布蒿涎。 她就那樣靜靜地躺著哀托,像睡著了一般。 火紅的嫁衣襯著肌膚如雪劳秋。 梳的紋絲不亂的頭發(fā)上仓手,一...
    開(kāi)封第一講書(shū)人閱讀 52,807評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音玻淑,去河邊找鬼嗽冒。 笑死,一個(gè)胖子當(dāng)著我的面吹牛补履,可吹牛的內(nèi)容都是我干的添坊。 我是一名探鬼主播,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼箫锤,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼贬蛙!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起谚攒,我...
    開(kāi)封第一講書(shū)人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤阳准,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后五鲫,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體溺职,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了浪耘。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片乱灵。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖七冲,靈堂內(nèi)的尸體忽然破棺而出痛倚,到底是詐尸還是另有隱情,我是刑警寧澤澜躺,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布蝉稳,位于F島的核電站,受9級(jí)特大地震影響掘鄙,放射性物質(zhì)發(fā)生泄漏耘戚。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一操漠、第九天 我趴在偏房一處隱蔽的房頂上張望收津。 院中可真熱鬧,春花似錦浊伙、人聲如沸撞秋。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)吻贿。三九已至,卻和暖如春哑子,著一層夾襖步出監(jiān)牢的瞬間舅列,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工卧蜓, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留剧蹂,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓烦却,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親先巴。 傳聞我的和親對(duì)象是個(gè)殘疾皇子其爵,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361

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

  • 在C語(yǔ)言中,五種基本數(shù)據(jù)類(lèi)型存儲(chǔ)空間長(zhǎng)度的排列順序是: A)char B)char=int<=float C)ch...
    夏天再來(lái)閱讀 3,352評(píng)論 0 2
  • 回溯算法 回溯法:也稱(chēng)為試探法,它并不考慮問(wèn)題規(guī)模的大小伸蚯,而是從問(wèn)題的最明顯的最小規(guī)模開(kāi)始逐步求解出可能的答案摩渺,并...
    fredal閱讀 13,675評(píng)論 0 89
  • 01 閱讀的藝術(shù)與活力 在這個(gè)信息大爆炸的時(shí)代,獲取信息方式各種各樣電臺(tái)剂邮、電視摇幻、網(wǎng)絡(luò),這些只要在網(wǎng)上搜索都能信手拈...
    橙橙讀書(shū)閱讀 188評(píng)論 0 1