八皇后问题
皇后：国际象棋中威力最强的一颗棋子，走法是横、直、斜走均可，格数不限，不可越子
国际象棋：在8*8的方格上进行的一种快乐游戏
棋盘
八皇后问题：如何在8*8的棋盘上摆放八个皇后使其不能互相攻击
思考
看到这个问题，首先想到的就是不断进行尝试，暴力求出所有可能性。但是这样会有种情况，耗时太多。
自然的，就会想到可不可以提前判断，如果棋子已经放在了不恰当的位置，就直接舍弃之后的所有可能性
第二行的棋子落下
第二行的棋子落下时，Queen们就会互相攻击，所以就不必继续放置接下来的
种情况
来自维基的动图
代码
声明部分
#include <iostream>
using namespace std;
const int N = 8; //N值代表几皇后问题
int chessboard[N][N] = { 0 }; //定义棋盘大小
int solve_num = 0; //解的数目
我们采用二维数组，可以更加直观的表达棋盘的情况
N值可根据情况任意改变，如N=4即为四皇后问题
判断部分
bool check(int row, int col)
{
if (row == 0) return true;
for (int i = 0; i != row; ++i){
if (chessboard[i][col] == 1)
return false; //每列(col)只能有一个棋子
}
for (int j = 0; j != col; ++j){
if (chessboard[row][j] == 1)
return false; //每行(row)只能有一个棋子
}
/*把i和j的值分别置为比当前棋子位置的值少一，即为左上角一格，
i >= 0 && j >= 0;控制i和j在棋盘范围内，
--i, --j；向左上角移动
*/
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j){
if (chessboard[i][j] == 1)
return false; //判断左上角是否有棋子
}
/*i的值为当前棋子的行值减一，j的值为当前棋子的列值加一，即为右上角一格，
i != N && j != N; 控制i和j在棋盘范围内，
--i, ++j；向右上角移动
*/
for (int i = row - 1, j = col + 1; i >= 0 && j != N; --i, ++j){
if (chessboard[i][j] == 1)
return false; //判断右上角是否有棋子
}
//如果行、列和对角线都没有其他棋子，则返回true
return true;
}
输出部分
void print()
{
int row, col; //行，列
++solve_num; //每次执行该输出函数，全局变量solve_num就会加一，代表解的数目加一
cout << "Solution " << solve_num << ":" << endl;
for (row = 0; row != N; ++row) {
for (col = 0; col != N; ++col) {
cout << chessboard[row][col] << ends;
}
cout << endl;
}
}
递归函数实现回溯法
void solve(int row)
{
int col; //列
for (col = 0; col != N; ++col){
chessboard[row][col] = 1; //在第row行的其中一列放置皇后
if (check(row, col) == true){ //检查放置皇后位置是否合法
if (row == N - 1){ //检查合法后，如该行已经是棋盘最后一行
print(); //打印出该解法
}
else{ //如果不是最后一行
solve(row + 1);//就继续判断下一行的皇后要放在哪个位置
}
}
chessboard[row][col] = 0;//如检查不合法，就把放置的皇后撤走(即1变0)
}
}
递归时不要过于纠结每步是如何实现的，那是程序要完成的工作，
我们只要坚信，递归结果是正确的
主函数
int main()
{
solve(0); //传入第 0行
return 0;
}
运行结果
四皇后：
四皇后
十四皇后：
十四皇后
个人主页
http://spaceman.site/
欢迎访问
