內(nèi)容來(lái)自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫(xiě)在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

6.7.1八皇后問(wèn)題介紹

八皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型案例。該問(wèn)題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出:在8*8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即:任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法(92)。

1.????? 第一個(gè)皇后先放第一行第一列

2.????? 第二個(gè)皇后放在第二行第一列、然后判斷是否OK，如果不OK，繼續(xù)放在第二列、第三列、依次把所有列都放完，找到一個(gè)合適

3.????? 繼續(xù)第三個(gè)皇后，還是第一列、第二列……直到第8個(gè)皇后也能放在一個(gè)不沖突的位置，算是找到了一個(gè)正確解

4.????? 當(dāng)?shù)玫揭粋€(gè)正確解時(shí)，在棧回退到上一個(gè)棧時(shí)，就會(huì)開(kāi)始回溯，即將第一個(gè)皇后，放到第一列的所有正確解，全部得到.

5.????? 然后回頭繼續(xù)第一個(gè)皇后放第二列，后面繼續(xù)循環(huán)執(zhí)行1,2,3,4的步驟

6.????? 示意圖

說(shuō)明：

理論上應(yīng)該創(chuàng)建一個(gè)二維數(shù)組來(lái)表示棋盤(pán)，但是實(shí)際上可以通過(guò)算法，用一個(gè)一維數(shù)組即可解決問(wèn)題. arr[8]={0,4,7,5,2,6,1,3}//對(duì)應(yīng)arr下標(biāo)表示第幾行，即第幾個(gè)皇后，ar[i]=val , val 表示第i+1個(gè)皇后，放在第+1行的第val+1列

6.7.3八皇后問(wèn)題算法代碼實(shí)現(xiàn)