问题描述
什么是皇后问题
八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
一起看看经典教材 计算机算法设计与分析 对该问题的描述：
- 在 n × n 棋盘上放彼此不受攻击的n个皇后。
- 按照国际象棋规则，皇后可以攻击 同行、同列、同一斜线 的棋子。
- 等价于在 n × n 格的棋盘上放置 n 个皇后，任何 2 个皇后不放在 同一行 或 同一列 或 同一斜线 上。
解题思路
由于皇后的位置受到上述三条规则约束，我们必须通过一些技术手段来判断当前皇后的位置是否合法。
1.皇后的编号从 0 ~ N - 1 （N表示皇后的数量），这样编号的想法很简单：数组下标从0开始（这样方便后续对其位置的说明）。
2.使用一维数组 putInf 对每一行皇后的存放位置进行保存，因此得到解向量 (putInf[0], putInf[1], putInf[3], … , putInf[N - 1])，putInf[i] 表示第 i 个皇后被放置到了第 putInf[i] + 1 列上（putInf数组中存储的是列号，范围为 0 ~ N - 1）;
3.第二个条件：各皇后不同列， N 皇后放在 N x N 的棋盘上，那么每一列最多且必须放置一个皇后，这里我用了一个 used数组 对每一列的摆放情况进行记录， used[i] = true 表示 第 i 列 已经放置了皇后，used[i] = false 表示第i列暂未放置皇后，这样我们可以保证不在一列上放置多个皇后，也就能满足 各皇后不同列 的规则。
4.各皇后不能处于同一对角线位置：假设两皇后位置坐标分别为(i, j) 、（l, k），那么根据直线斜率公式：
- (i - l) / (j - k) = 1 求解得 i - l == j - k ①
- (i - l) / (j - k) = -1 求解得 i - l == k - j ②
这两种情况出现时表明处于同一对角线，那么要满足摆放规则就必须满足
| i - l | != | j - k | （“| |” 表示绝对值）
解空间树
实现代码
#include <iostream>
#include <vector>
using namespace std;
#define N 4 //N皇后
vector<int> putInf;//每一行皇后的置放位置情况
//不同行 不同列 不同斜线 |ri - rj| != |ci - cj| 第1行与
vector<int> used(N, 0);//每一列只能有一个皇后，记录每一列的状态
vector<vector<int>> ans;//存储可行方案
int curRow = 0;//当前待放皇后的行数
/* 正置放皇后行↓ 置放列↓ */
bool judgeLegalPut(int& curRow, int col) {//判断在curRow行的col列放置皇后是否合法
for (int i = curRow - 1; i >= 0; i--) {
//我们的解空间树已经去除一行一列置放相同元素
//（每一个皇后被放在不同行以及不同列）的情况
//因此我们只需要判断皇后是否成斜线即可
if (curRow - i == abs(col - putInf[i])) {
//当前位置与之前的皇后处于同一斜线上
return false;
}
}
return true;
}
void queensAssign(int curRow) {
if (curRow >= N) {//递归到叶子节点，递归结束，收集结果
ans.push_back(putInf);
return;
}
//i : 当前行皇后准备放的列数
for (int i = 0; i < N; ++i) {//curRow行i列的位置
if (used[i]) continue;//位置被使用过，直接跳过
//这样满足了不处于同一列的显条件 类似于全排列
if (judgeLegalPut(curRow, i)) {
//当前位置置放与之前不冲突 将皇后加入
used[i] = true;
putInf.push_back(i);
queensAssign(curRow + 1);
used[i] = false;//撤销之前的状态
putInf.pop_back();
}
}
}
void printChessBoard(vector<int>& vec) {//输出模拟棋盘
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j != vec[i])
cout << " × ";
else
cout << " √ ";
}cout << endl;
}cout << endl;
}
/// <author>
/// nepu_bin
/// <博客域名>
/// bincode.blog.csdn.net
int main() {
queensAssign(0);
int n = 1;
cout << N << "皇后问题,方案如下:\n" << endl;
for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end(); it++) {
cout << "第" << n++ << "种放置方案, 皇后被放于 " << endl;
for (int i = 0; i < it->size(); i++) {
cout << (*it)[i] + 1 << " ";
}cout <<"列" << endl;
cout << endl << "棋盘布局如下↓" << endl;
printChessBoard(*it);
}
return 0;
}
运行效果
四皇后问题运行截图：
通过修改宏定义 N 可以得到不同数量皇后问题的解答~~~
八皇后求解：
子集树与排列树
附上子集树 and 排列树的定义
