数据结构与算法中的“递归”——用回溯法求解8皇后问题
八皇后问题是一个古老而著名的问题，它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的：在8行8列的国际象棋棋盘上摆放着八个皇后。若两个皇后位于同一行、同一列或同一对角线上，则称为它们为互相攻击。在国际象棋中皇后是最强大的棋子，因为它的攻击范围最大，图6-15显示了一个皇后的攻击范围。
图6-15 皇后的攻击范围
现在要求使这八个皇后不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。现代教学中，把八皇后问题当成一个经典递归算法例题。图6-16显示了两种八个皇后不相互攻击的情况。
图6-16八个皇后不相互攻击的情况
现在来看如何使用回溯法解决八皇后问题。这个算法将在棋盘上一列一列地摆放皇后直到八个皇后在不相互攻击的情况下都被摆放在棋盘上，算法便终止。当一个新加入的皇后因为与已经存在的皇后之间相互攻击而不能被摆在棋盘上时，算法便发生回溯。一旦发生这种情况，就试图把最后放在棋盘上的皇后移动到其他地方。这样做是为了让新加入的皇后能够在不与其它皇后相互攻击的情况下被摆放在棋盘的适当位置上。例如图6-17所示的情况，尽管第7个皇后不会与已经放在棋盘上的任何一皇后放生攻击，但仍然需要将它移除并发生回溯，因为无法为第8个皇后在棋盘上找到合适的位置。
图6-17 需要发生回溯的情况
算法的回溯部分将尝试移动第7个皇后到第7列的另外一点来为第8个皇后在第8列寻找一个合适的位置。如果第7个皇后由于在第7列找不到合适的位置而无法被移动，那么算法就必须去掉它然后回溯到第6列的皇后。最终算法不断重复着摆放皇后和回溯的过程直到找到问题的解为止。
以上问题描述摘自左飞的《C++数据结构原理与经典问题求解》。
下面是我写的代码：(请不要被我的代码所影响，这里只是起到对比的作用，我的代码并不好，是按照我的第一习惯写的，而且只能找出一组，所以可跳过)
// 八皇后问题
#include<iostream>
using namespace std;
#include <vector>
struct node
{
int x;
int y;
};
// 要有个容器保存暂时的几个落脚点。
vector<node> vec;
bool isSafe(const node& tmp)
{
for (int i=0;i<vec.size();i++)
{
/**** if ( (tmp.y-vec[i].y) % (tmp.x-vec[i].x) != 0 ) 这种判断不对，如[7][7] 和[6][4] 也是余数0，但是不符合
{
return false;
} ****/
if (tmp.y==vec[i].y||tmp.x==vec[i].x)
{
return false;
}
if ( tmp.y-vec[i].y == tmp.x-vec[i].x ) // 别用横纵坐标差相除=1判断，而是用横纵坐标差相等来判定
{
return false;
}
}
vec.push_back(tmp);
return true;
}
void OutPut(const vector<node>& vec)
{
for (int i=0;i<vec.size();i++)
{
cout<<vec[i].x<<","<<vec[i].y<<endl;
}
}
bool find(int column) // 递归函数 参数column是当前在这个列上找可放的落脚点
{
for (int raw=0;raw<8;raw++)
{
if (vec.size()==8)
{
// 打印结果，终止整个运行
OutPut(vec);
return true;
}
node tmp;
tmp.x=column;
tmp.y=raw;
if (isSafe(tmp))
{
find(column+1) ; // 内部调用递归
}
}
vec.pop_back(); // 我所没考虑的是假如发现一直找不到了，那么popup是必须的操作啊，那么放在这是对的吗？？
return false;
}
int main()
{
// 先构造棋盘
node board[8][8];
for (int i=0;i<8;i++)
{
for (int j=0;j<8;j++)
{
board[i][j].x=i;
board[i][j].y=j;
}
}
// 外部调用递归
find(0);
return 0;
}
下面是左飞的代码：（很强大，果然在数据结构方面应该多多看别人的优秀的代码）
#include <CONIO.H>
#include <IOSTREAM>
using namespace std;
#define MAX 8
int sum=0;
class QueenPuzzle
{
int queens[MAX]; // 保存每行皇后的列标 用一维的数组就能表示2种变量之间的联系
public:
void printOut(); // 打印结果
int IsValid(int n); // 判断第n个皇后放上去后是否合法
void placeQueen(int i); // 递归算法放置皇后
};
void QueenPuzzle::printOut()
{
for (int i=0;i<MAX;i++)
{
for (int j=0;j<MAX;j++)
{
if (j==queens[i])
{
cout<<"Q";
}
else
{
cout<<"0";
}
}
cout<<endl;
}
cout<<endl<<"按q键退出，按其他键继续"<<endl<<endl;
if (getch()=='q')
{
exit(0);
}
}
int QueenPuzzle::IsValid(int n)
{
for (int i=0;i<n;i++)
{
if (queens[i]==queens[n])
{
return 0;
}
if (abs(queens[i]-queens[n]) == abs(i-n)) // 列数之差等于行数之差
{
return 0;
}
}
// 没有冲突返回1
return 1;
}
void QueenPuzzle::placeQueen(int i) // 在第i行放置皇后
{
for (int j=0;j<MAX;j++)
{
if (i==MAX)
{
sum++;
cout<<"第"<<sum<<"组解:"<<endl;
printOut();
return ; // 本次函数调用结束，那么也是回到上次的placeQueen(i+1);语句啊，然后也是接着下个循环j++嘛。。。
}
queens[i]=j;
if (IsValid(i))
{
placeQueen(i+1);
}
}
// 假如循环结束出到这了，那么本次函数调用结束，那么也是回到上次的placeQueen(i+1);语句啊，然后也是接着下个循环j++嘛。。。
}
int main()
{
QueenPuzzle queen;
queen.placeQueen(0);
cout<<"共"<<sum<<"组解"<<endl;
return 0;
}
这里有个疑惑是为什么左飞的代码可以弄出很多组解呢？？
其原因在于placeQueen里的j通过自增是迟早会从0遍历到MAX的。它也会让你原来的符合要求的queensland[i]重新赋值为新的j继续做判断。
要理解的一点就是比如当前第5行的女皇位置为某个值时，剩下的2个女皇可以出现对应的一组布局，当第5行的女皇帝在另外一个值时候，剩下的2个女皇又可以出现在不同的一组布局上。