一.問題描述
題目如上圖所示，在一個(gè)n*n的國際象棋棋盤上怎么擺放能使得皇后互相攻擊不到（也就是在任意一列、一行、一條對角線上都不存在兩個(gè)皇后）
二.思路分析
1.DFS
想要解決這個(gè)問題，我們可以使用dfs也就是深度優(yōu)先遍歷，深度優(yōu)先搜索的步驟為先遞歸到底再回溯上來，顧名思義，dfs是以深度為目標(biāo)，一條路走到底，直到達(dá)到無路可走時(shí)，退回到上一步的狀態(tài)，走其他路回溯上來。
這題我們就可以定義數(shù)組當(dāng)做棋盤，遍歷所有位置判斷是否可以放置皇后（需要滿足任意一列、一行、一條對角線上都不存在兩個(gè)皇后），在遍歷的過程中需要考慮剪枝的情況，減少解題時(shí)間復(fù)雜度。
三.代碼實(shí)現(xiàn)與解析
1.分析
首先我們創(chuàng)建完數(shù)組模擬棋盤后，先要依據(jù)題意，將數(shù)組初始化為.
#include <iostream>
const int N = 20;
using namespace std;
char ret[N][N];
bool col[N], dg[N], udg[N];//標(biāo)記列、對角線上是否已經(jīng)有皇后
int n = 0;
void dfs(int u);
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int m = 0; m < n; m++)
ret[i][m] = '.';
dfs(0);//dfs算法函數(shù)
return 0;
}
緊接著就是dfs函數(shù)代碼的實(shí)現(xiàn)邏輯：
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i++)
{
cout << ret[i] << endl;;
}
cout<< endl;
return;
}
for (int i = 0; i < n; i++)
{
if (!col[i] && !dg[u + i] && !udg[n + i - u])
{
ret[u][i] = 'Q';
col[i] = dg[u + i] = udg[n + i - u] = true;
dfs(u + 1);
ret[u][i] = '.';
col[i] = dg[u + i] = udg[n + i - u] = false;
}
}
}
需要重點(diǎn)理解的在for循環(huán)中i代表的是列數(shù)（遍歷的是列），u代表的是層數(shù)，if判斷當(dāng)行、對角線均暫無皇后時(shí)，則可以在此放置皇后，并標(biāo)識(shí)為已經(jīng)放置，此時(shí)這一層的放置就結(jié)束了，所以接著就要遞歸下一層，之后就會(huì)分為兩種情況：
1.遞歸到最后一層成功打印了這次的方案。接著就會(huì)向上回溯文章來源：http://www.zghlxwxcb.cn/news/detail-843481.html
ret[u][i] = '.';
col[i] = dg[u + i] = udg[n + i - u] = false;
執(zhí)行恢復(fù)邏輯。
2.在后續(xù)層數(shù)遍歷放置時(shí)，出現(xiàn)了不合法的情況（列數(shù)到達(dá)閾值依舊沒有放置），此時(shí)就會(huì)剪枝，也是會(huì)回溯到上圖代碼進(jìn)行恢復(fù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-843481.html
2.完整代碼
#include <iostream>
const int N = 20;
using namespace std;
char ret[N][N];
bool col[N], dg[N], udg[N];
int n = 0;
void dfs(int u);
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int m = 0; m < n; m++)
ret[i][m] = '.';
dfs(0);
return 0;
}
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i++)
{
cout << ret[i] << endl;;
}
cout<< endl;
return;
}
for (int i = 0; i < n; i++)
{
if (!col[i] && !dg[u + i] && !udg[n + i - u])
{
ret[u][i] = 'Q';
col[i] = dg[u + i] = udg[n + i - u] = true;
dfs(u + 1);
ret[u][i] = '.';
col[i] = dg[u + i] = udg[n + i - u] = false;
}
}
}
到了這里，關(guān)于N皇后問題詳解：回溯算法的應(yīng)用與實(shí)踐（dfs）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
