當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

DFS与N皇后问题

發布時間：2025/3/21 编程问答 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 DFS与N皇后问题小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

DFS與N皇后問題

DFS

什么是DFS

DFS是指深度優先遍歷也叫深度優先搜索。

它是一種用來遍歷或搜索樹和圖數據結構的算法

注：關于樹的一些知識可以去看《樹的概念及基本術語》這篇文章

它會不斷地沿著節點的深度方向（該深度方向為其鄰接點的方向）進行遍歷

DFS如何實現

DFS主要步驟有以下幾步

訪問并從某節點
向鄰接點出發，訪問路徑向深處走
若走到最深處還有節點沒訪問，則再回到該層訪問該節點（回溯）
依次重復上述步驟，直至所有路徑都被訪問（遞歸）

DFS時空復雜度

空間復雜度

DFS算法實際上是一個遞歸算法，需要借助一個遞歸工作棧

故

空間復雜度：O(n)

時間復雜度

時間復雜度：不確定

為什么不確定？

因為遍歷圖的過程實質上是對每個頂點找查其所有鄰接點的過程，其耗費時間取決于所采用結構

下面給出常用的幾種數據結構DFS時的時間復雜度

（注：n是圖中結點的個數，e是圖中邊的個數。）

鄰接表 O(e+n)
鄰接矩陣 O(n^2)

N皇后問題

N皇后問題（HDU2553）

HDU 2553 N皇后問題在N*N的方格棋盤放置了N個皇后，使得它們不相互攻擊（即任意2個皇后不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上。你的任務是，對于給定的N，求出有多少種合法的放置方法。輸入：共有若干行，每行一個正整數N≤10，表示棋盤和皇后的數量；如果N=0，表示結束。輸出：共有若干行，每行一個正整數，表示對應輸入行的皇后的不同放置數量。輸入樣例： 1 8 5 0輸出樣例： 1 92 10

經典DFS帶來的問題

而經典的DFS，基本是將所有子節點全部擴展開，再選取最新的節點進行擴展。

但是對于N皇后來說，我們如果一一枚舉，則有N的N次方種情況.

即使N=10，則有10^10種情況，我們還要在這些情況中進行篩選，這無疑需要巨大的計算

故：我們需要對DFS進行優化

回溯與減枝

我們可以讓程序在某節點由某些條件就可以判斷再進行繼續展開并不符合要求，然后立即返回，達到回溯和減少樹的枝干的生成（減枝）的目的，從而進行優化。

下面給出N=4時減枝的樹狀圖解

問題分析

關鍵問題

關鍵問題：在擴展節點時如何去掉不符合條件的節點？

設左上角是(0,0)，已經放好皇后是(i,j)，不同行、列、斜線的新皇后是(r,c)，則：

橫向不同行 i != r
縱向不同列 j != c
斜對角：從(i,j)向斜對角走a步，新坐標(r,c)有4種情況 (i-a,j-a) (i+a,j-a) (i-a,j+a) (i+a,j+a)，即|i-r| = |j-c|。也就是說不再斜線上滿足 |i-r| != |j-c|

其他問題

由于給出N<=10，所以可以用打表的方式，將每種n取值對應的結果放到數組ans[n]中
對于數組ans[]由于大小最方便設為11，n在0–10中取值一共11種情況。盡管我們可以忽略0定義成大小為10的數組（將n=1結果存放在ans[0]以此類推），但我們在取出數據時還要進行減法運算并不方便。
對于在對特定的n取值分析時可用個tot變量來記錄到達最深處情況的個數，由于循環是從0開始，我們只需要讓r=n時tot自增1來記錄并回溯
數組col[r] = c，表示皇后放在第r行c列，我們可以用col[i] 來依次獲得前幾行皇后位置信息，故對于本題col[]數組定義最大為10就行

題解代碼

#include <iostream>using namespace std;//tot記錄每次n取特定值能放置n皇后情況的個數，每當n改變時tot重置為0 int n, tot = 0;//表示皇后存放位置 col[r] = c 表示第r行的皇后在第c列 int col[10];//r為行,c為列 //check()用于檢查新放置的皇后（r,c）是否和已經存放好的皇后沖突 //沖突返回false，不沖突返回true bool check(int r, int c) {for (int i = 0; i < r; i++)if (col[i] == c || (abs(col[i] - c) == abs(i - r))) //絕對值判斷是否在同一斜線上return false; //沖突返回falsereturn true; //不沖突返回true }//r為檢索的行 //對每行檢索并放置皇后 void DFS(int r) {//若達到最底行（層）則新增1種情況，并返回（回溯）if (r == n) {tot++;return;}//對第r行（層）的每一列進行檢索，若能放置則進入下一行（層）再從r+1行第0列向后檢索放置依次類推//若不能放置則本層次結束，遞歸然后回溯出去再改變上一層的列數，從該列再進行展開for(int c=0;c<n;c++)if (check(r, c)) //檢查若放在該層該列是否與之前皇后沖突{col[r] = c; //記錄再第r行c列放皇后，用于下一層向上檢驗沖突DFS(r + 1); //繼續放下一層皇后}}int main() {//用于打表記錄結果的數組int ans[11];memset(ans, 0, sizeof(0));//算出n取所有值的答案for (n = 0; n <= 10; n++){memset(col, 0, sizeof(col)); //清空上一回的數組，計算下一個n皇后問題tot = 0;DFS(0);ans[n] = tot; //打表，保存}while (cin >> n){if (n == 0)return 0;cout << ans[n] << endl;}return 0; }