- 首页 > it技术 > >
/*
八皇后问题：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，
即任意两个皇后都不能处于同一行、同一列或同一斜线（45度）上，
问有多少种摆法。
*//*
分析：
由已知条件可知，每行有且只有一个皇后。用一个数组存放每行上皇后的位置。
此数组中，下标表示行数，元素表示列数（也即本行上皇后的位置）。从第一行开始遍历每行不产生冲突的皇后位置。
当第i行没有正确位置可以放的话，那么将第i-1行的皇后位置往后移一个位置并判断是否是正确位置。
如果i-1行还没有的话再往上找。（回溯思想）
如果遍历到最后一行的皇后也有正确位置可以摆放的话，将其打印下来，摆法加1。
然后继续遍历最后一行是否有其他位置也是正确的，如果有，打印下来，摆法加1；
如果没有再去找倒数第二行上面是否有其他正确位置可以放，有的话，就再遍历最后一行，查找是否有正确位置。（回溯的思想）。
*//*
在网上找了一些实现方法，特别是c++的，都有点不好理解，可能是 俺是菜鸟的缘故吧。
这是一个C版的实现，将来会写一个C++的版本。
另外，读者看了之后有疑惑的地方，请一定告知！俺会积极配合、探讨、修正、解答！谢谢！
*/
#include "stdafx.h"
#include
#include
#include using namespace std;
#define MAX 8int queen[MAX];
// 此数组中，下标表示行数，元素表示列数（也即本行上皇后的位置）。
int sum = 0;
int IsCorPos(int CurRowNum)//判断是否是正确位置
{
if(0 == CurRowNum)
return 1;
for(int RowNum = 0;
RowNum < CurRowNum;
RowNum++)
{
if(abs(CurRowNum - RowNum) == abs(queen[CurRowNum] - queen[RowNum]) || queen[CurRowNum] == queen[RowNum])
return 0;
}
return 1;
}
void Print()// 打印摆放结果
{
for(int i = 0;
i < MAX;
i++)
cout << i << ' ' << queen[i] << ',';
cout << endl;
sum++;
}void Put(int RowNum)// 这是重点，采用了回溯法。 用递归方法辅助实现。
{
for(int Col = 0;
Col < MAX;
Col++)
{queen[RowNum] = Col;
if(IsCorPos(RowNum))
{
if(RowNum == MAX - 1)
Print();
else
{
Put(1+RowNum);
}
}
}
}
// 测试用例
int main()
{
Put(0);
cout << endl << sum << endl;
return 0;
}
推荐阅读
