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..