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

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

6.7.1八皇后問題介紹

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

1.????? 第一個皇后先放第一行第一列

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

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

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

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

6.????? 示意圖

說明：

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

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