八皇后問題，是在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法？

算法思路：

八皇后問題實質為一種深度優先(DFS)搜索問題。

可分為兩個子函數來解決該問題。第一個子函數用于在棋盤上放置皇后。第二個子函數用于檢查擺放過程中有沒有違反放置規則。

實際運行過程，為放置第一層上的皇后，進入下一層然后先對上一層檢查，合法則進行下一行的放置。反之則退出遞歸調用，將非法行上的皇后移位。

算法具體描述：

放置皇后函數void Queen_Move(int i)；

void Queen_Move(int i)

{

int m = 0;//每行放置的格子位置

if (i == 8)//彈出遞歸的條件(放完了第8行)和打印結果；

{

map++;//總的放置方法個數

cout << "Queens Location ：" << map << endl;

Print();//打印函數

return;}

for (m = 0; m < 8; m++)//一行有八個格子，循環八次

{

if (Check(i,m) == 1)//檢驗上一次擺放合法后進入

{

Board[i][m] = 1;//放置皇后

Queen_Move(i + 1);//進入下一層放置皇后

Board[i][m] = 0;//進入遞歸下一層后，清除上一層數據，發現錯誤后正確進入下一個格子

}

}

}

檢查擺放合法函數：int Check(int k, int j)

int Check(int k, int j)

{

//由于以行為單位進行遞歸放置，因此不會出現一行中放置多個Queen的情況

for (int i = 0; i < 8; i++) //檢查列

{

if (Board[i][j] == 1)

{

return 0;

}

}

for (int i = k - 1, m = j - 1; i >= 0 && m >= 0; i--, m--)

//檢查左對角線

{

if (Board[i][m] == 1)

{

return 0;

}

}

for (int i = k - 1, m = j + 1; i >= 0 && m <= 7; i--, m++)

//檢查右對角線

{

if (Board[i][m] == 1)

{

return 0;

}

}

return 1;

}

八皇后問題抽象出來的模型，實質為一種以深度為單位進行相關檢索的程序設計問題。棋盤的每一層即可被抽象為一層，共八層，從第一層開始尋找，合理進入下一層，并尋找前面擺放是否合法。

總結

以上是生活随笔為你收集整理的python深度优先算法 八皇后_八皇后问题——DFS(深度优先搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。