n-皇后問(wèn)題
n?皇后問(wèn)題是指將 n 個(gè)皇后放在 n×n的國(guó)際象棋棋盤(pán)上，使得皇后不能相互攻擊到，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。
現(xiàn)在給定整數(shù) n，請(qǐng)你輸出所有的滿足條件的棋子擺法。
輸入格式
共一行，包含整數(shù) n。
輸出格式
每個(gè)解決方案占 n行，每行輸出一個(gè)長(zhǎng)度為 n的字符串，用來(lái)表示完整的棋盤(pán)狀態(tài)。
其中 . 表示某一個(gè)位置的方格狀態(tài)為空，Q 表示某一個(gè)位置的方格上擺著皇后。
每個(gè)方案輸出完成后，輸出一個(gè)空行。
注意：行末不能有多余空格。
輸出方案的順序任意，只要不重復(fù)且沒(méi)有遺漏即可。
數(shù)據(jù)范圍
1≤n≤9
輸入樣例：
4
輸出樣例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
思路一：
米字攻擊法+回溯 dfs+剪枝
u是列數(shù)，一列一列擺棋子。
#include
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u)
{
if (u == n)
{
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
return;
}
for (int i = 0; i < n; i ++ )
if (!col[i] && !dg[u + i] && !udg[n - u + i])
{
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
方法二：
一種更加樸素的搜索順序，直接挨個(gè)挨個(gè)兩種情況討論即可，仍舊是從上往下一直擺，出了錯(cuò)誤就回溯。
#include
using namespace std;
const int N = 10;
int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];
void dfs(int x, int y, int s)
{
if (s > n) return;
if (y == n) y = 0, x ++ ;
if (x == n)
{
if (s == n)
{
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
}
return;
}
g[x][y] = '.';
dfs(x, y + 1, s);
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
g[x][y] = 'Q';
dfs(x, y + 1, s + 1);
g[x][y] = '.';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
}
}
int main()
{
cin >> n;
dfs(0, 0, 0);
return 0;
}
版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。
版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。
相關(guān)文章
