八皇后問題詳解
今天的八皇后也是遞回訓練的一個小環節，廢話不多說，
首先我們獲取題目的資訊：
在國際象棋中，皇后是最厲害的棋子，可以橫走、直走，還可以斜走，棋手馬克斯·貝瑟爾 1848 年提出著名的八皇后問題：即在 8 × 8 的棋盤上擺放八個皇后，使其不能互相攻擊 —— 即任意兩個皇后都不能處于同一行、同一列或同一條斜線上，例如：
現在我們把棋盤擴展到 n×n 的棋盤上擺放 n 個皇后，請問該怎么擺？
請撰寫程式，輸入正整數 n，輸出全部擺法（棋盤格子空白處顯示句點“.”，皇后處顯示字母“Q”，每兩個字符之間空一格），
輸入格式：
正整數 n(n>0)
輸出格式：
若問題有解，則輸出全部擺法（每兩種擺法之間空一行），
若問題無解，則輸出 None，
輸入樣例1：
3
輸出樣例1：
None
輸入樣例2：
6
輸出樣例2：
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .
. . Q . . .
. . . . . Q
. Q . . . .
. . . . Q .
Q . . . . .
. . . Q . .
. . . Q . .
Q . . . . .
. . . . Q .
. Q . . . .
. . . . . Q
. . Q . . .
. . . . Q .
. . Q . . .
Q . . . . .
. . . . . Q
. . . Q . .
. Q . . . .
下面就直接上代碼了，我會在代碼后面反復注釋，盡量讓讀者理解進去
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
char ch[N][N];//用一個二維陣列來存盤皇后放置的位置
bool col[N], l[N << 1], r[N << 1];//為了陣列不會越界，就把N乘2了,涉及位運算了
bool mark;//設定一個變數，判斷是否有解（有解輸出排法，無解輸出None）
int n;
//這個dfs是按行逐漸進行下去的，初始值為0行
void dfs(int x)
{
//如果x能夠來到從初始值0來到n的位置就說明有一個解已經產生
if (x == n) {
/*
加這個判斷實屬必要，當第一個解產生的時候，此時mark還是初始值false(0),
所以把mark進入判斷的第二個作用域，賦值為true(1),如果還有第二個解，
此時的mark已經為true，所以輸出換行，看到這里是不是有些明白了，對，沒錯！
這個判斷就是為了“解”與“解”之間能有個換行符而存在的！
*/
if (mark)
{
cout << endl;
}
else
{
mark = 1;
}
//下面就是遍歷這個“解”了
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << ch[i][j];
if(j!=n-1)
{
cout<<' ';//處理字符與字符之間的空格
}
}
putchar(10);//輸出一行后需要換行，換行的ASCII數為10
}
return;//當這個“解”遍歷完的時候，可以安排它消亡了
}
//下面代碼是這個題的核心，請務必！務必！務必！要不擇一切手段也要弄懂
/*
要明白下面的for回圈的意思，記住是x代表行數，下面的 i 代表的是x行 i 列,
如果不明白，請反復看，已經是 保姆式 教學了，
*/
for (int i = 0; i < n; i++)
{
//下面的判斷是核心中核心:
//第一個判斷col[i]是判斷i列能不能放，col[i]=1,說明不能放（因為下面的判斷是！col[i]）
//第二個判斷l[x + i]是判斷主對角線能不能放，
//第三個判斷r[n - x + i]是判斷副對角線能不能放，
//第二第三個如果不能理解，建議直接強記模板！
if (!col[i] && !l[x + i] && !r[n - x + i])
{
col[i] = l[x + i] = r[n - x + i] = 1;//如果能放，對狀態進行標記
ch[x][i] = 'Q';
dfs(x + 1);//第一行結束，對下一行進行判斷,都 x+1了，你說是不是下一行
//對該坐標進行歸“零”處理
ch[x][i] = '.';
col[i] = l[x + i] = r[n - x + i] = 0;
}
}
}
int main() {
//這個就是對陣列進行初始化處理，如果不知道的建議搜 memset()詳解
memset(ch, '.', sizeof(ch));//初始化地圖陣列,這個函式在cstring這個頭檔案下面
cin >> n;
dfs(0);//這個就沒得說了，從第一行開始遍歷，0就是第一行，
//無解就輸出 None 咯！
if (!mark)
{
cout << "None";
}
return 0;
}
八皇后題解如上，如看不懂，那就反復的看吧，這涉及到了遞回的知識，借用一句話：“ 要理解遞回，你要先理解遞回，直到你理解遞回”，
今天八皇后有點難，反復的敲一下，總有好處，讀書也是這樣：“書讀百遍，其義自見！”（保姆式教學）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274133.html
標籤：其他