N皇後問題是計算機科學中最為經典的問題之一，該問題可追溯到1848年，由國 際西洋棋棋手馬克斯·貝瑟爾于提出了8皇後問題。
将N個皇後放擺放在N*N的棋盤中，互相不可攻擊，有多少種擺放方式，每種擺 放方式具體是怎樣的?
8皇後即 8*8的棋盤中，将8個皇後放置在棋盤上，且皇後之間無法倆倆攻擊到對方。
關于國際象棋中皇後的實力：國際象棋棋局中實力最強的一種棋子，也是最容易被吃掉的棋子。後可橫直斜走，且格數不限
類似4*4的棋盤上，有如下兩種皇後的放置方法:
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q.. 分析：
N*N的棋盤放置N個皇後，即至少每一行需要一個皇後；
- 将一個皇後放置到棋盤上之後，棋盤如何演變（一個皇後放到棋盤，她的影響區域為上，下，左，右，左上，左下，右上，右下）
- 針對每一個皇後，如何能夠确認下一個皇後，以及下下一個皇後。。。直到能夠放置N個皇後的棋盤分布？
針對問題一，我們可以實作如下算法：
針對棋盤打标:
void mark_queen(int x, int y, std::vector<std::vector<int> > &mark) {
/*
維護兩個方向數組
可以取到皇後的八個方向即可
這裡定義了const型是為了節省記憶體，即整個程序代碼運作期間，此時的const兩個數組是存放在常量記憶體區，
且定義為了static，則整個代碼僅僅會有一份拷貝*/
static const int dx[] = {0,0,-1,1,-1,1,-1,1};
static const int dy[] = {-1,1,0,0,-1,-1,1,1};
if (x < 0 || x > mark.size() || y < 0 || y > mark.size()) {
return ;
}
mark[x][y] = 1;
for (int i = 0;i < mark.size(); ++i) {
for (int j = 0;j < 8; ++j) {
int new_x = x + i * dx[j];
int new_y = y + i * dy[j];
if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) {
mark[new_x][new_y] = 1;
}
}
}
} 回到問題2上，我們想要擷取棋盤上能夠放置皇後的方法的個數以及具體的放置位置；
可以先嘗試一個一個放，當然這放置可以按照行放，也可以按照列放（八皇後問題最終的表現形式就是每行隻能有一個，每一列隻能有一個）。
我們這裡的放置皇後的方式都按照行放，第一行第一個：
| Q | 1 | 1 | 1 |
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 |
接下來皇後的放置的規則肯定就是在不能被第一個Q影響的情況下放置了，我們這裡仍然按照行進行放置，放第二個,如下紅色1則為重新放置後打入的标記
| Q | 1 | 1 | 1 |
| 1 | 1 | Q | 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 |
再次進行放置，發現第三行已經沒有位置可以放了，此時可以定論，最開始的第一次放置位置不合理，需要進行回溯，回溯到第一次放置Q之前棋盤的位置，即
綜上過程我們可以知道我們算法實作有以下幾個點
- 按行（或者列）進行棋盤周遊，每一次放置一個皇後，并對皇後區域進行打标
- 以上過程需要遞歸完成，遞歸過程中發現無法達到N*N放置N個皇後時即終止遞歸，并復原棋盤狀态為第一次放置皇後之前的棋盤狀态。
實作算法如下(文末有完整測試代碼):
/*标記棋盤放置皇後的數組*/
void mark_queen(int x, int y, std::vector<std::vector<int> > &mark) {
static const int dx[] = {0,0,-1,1,-1,1,-1,1};
static const int dy[] = {-1,1,0,0,-1,-1,1,1};
if (x < 0 || x > mark.size() || y < 0 || y > mark.size()) {
return ;
}
mark[x][y] = 1;
for (int i = 0;i < mark.size(); ++i) {
for (int j = 0;j < 8; ++j) {
int new_x = x + i * dx[j];
int new_y = y + i * dy[j];
if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) {
mark[new_x][new_y] = 1;
}
}
}
}
/*遞歸+回溯棋盤狀态*/
void generate(int k, int n, std::vector<string> &location, //用字元表示放置政策
std::vector<std::vector<string>> &result, //最終的放置政策的彙總
std::vector<std::vector<int> > &mark) { //儲存每一次放置皇後的棋盤狀态
if (k == n) { //結束條件就是發現目前放置政策支援N個皇後
result.push_back(location);
return;
}
/*按行周遊*/
for (int i = 0;i < n; ++i) {
/*備份初始棋盤狀态*/
std::vector<std::vector<int>> tmp_mark = mark;
/*放置位置就是沒有被打标的位置，即不會被其他皇後影響的位置*/
if (mark[k][i] == 0) {
/*放置一個皇後，針對其進行打标*/
mark_queen(k, i, mark);
location[k][i] = 'Q';
generate(k+1, n, location, result, mark);
/*遞歸之後復原到最初備份的狀态*/
mark = tmp_mark;
location[k][i] = '.';
}
}
}
/*初始化棋盤*/
std::vector<std::vector<string> > solve_N_queen(int n) {
std::vector<std::vector<int> > mark;
std::vector<std::vector<string> > result;
std::vector<string> location;
for (int i = 0;i < n; ++i) {
mark.push_back(std::vector<int> ());
for (int j = 0;j < n; ++j) {
mark[i].push_back(0);
}
location.push_back("");
location[i].append(n,'.');
}
generate(0,n,location,result,mark);
return result;
} 測試代碼如下:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
/*
N皇後問題是計算機科學中最為經典的問題之一，該問題可追溯到1848年
由國際西洋棋棋手馬克斯·貝瑟爾于提出了8皇後問題。
将N個皇後放擺放在N*N的棋盤中，互相不可攻擊，有多少種擺放方式，每種擺 放方式具體是怎樣的?
類似 N = 4
那麼如下輸出
solution1:
.Q..
...Q
Q...
..Q.
solution2:
..Q.
Q...
...Q
.Q..
*/
using namespace std;
/*标記棋盤放置皇後的數組*/
void mark_queen(int x, int y, std::vector<std::vector<int> > &mark) {
static const int dx[] = {0,0,-1,1,-1,1,-1,1};
static const int dy[] = {-1,1,0,0,-1,-1,1,1};
if (x < 0 || x > mark.size() || y < 0 || y > mark.size()) {
return ;
}
mark[x][y] = 1;
for (int i = 0;i < mark.size(); ++i) {
for (int j = 0;j < 8; ++j) {
int new_x = x + i * dx[j];
int new_y = y + i * dy[j];
if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) {
mark[new_x][new_y] = 1;
}
}
}
}
void generate(int k, int n, std::vector<string> &location,
std::vector<std::vector<string>> &result,
std::vector<std::vector<int> > &mark) {
if (k == n) {
result.push_back(location);
return;
}
for (int i = 0;i < n; ++i) {
std::vector<std::vector<int>> tmp_mark = mark;
if (mark[k][i] == 0) {
mark_queen(k, i, mark);
location[k][i] = 'Q';
generate(k+1, n, location, result, mark);
mark = tmp_mark;
location[k][i] = '.';
}
}
}
std::vector<std::vector<string> > solve_N_queen(int n) {
std::vector<std::vector<int> > mark;
std::vector<std::vector<string> > result;
std::vector<string> location;
for (int i = 0;i < n; ++i) {
mark.push_back(std::vector<int> ());
for (int j = 0;j < n; ++j) {
mark[i].push_back(0);
}
location.push_back("");
location[i].append(n,'.');
}
generate(0,n,location,result,mark);
return result;
}
int main(int argc, char const *argv[])
{
int n;
cin >> n;
std::vector<std::vector<string>> result;
result = solve_N_queen(n);
cout << "num of method is " << result.size() << endl;
cout << "method is " << endl;
for (int i = 0; i < result.size(); ++i) {
for (int j = 0;j < result[i].size(); ++j) {
cout << result[i][j];
cout << endl;
}
cout << endl;
}
return 0;
} #輸入
8
#輸出
num of method is 92
method is
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....
#以下輸出較多，可自行編譯檢視
...
#輸入
4
#輸出
num of method is 2
method is
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..