近来无聊，想着几年前用c#实现的八皇后，是参考网上的答案，如今过了几年，想试试有没进步，用c++简单地实现。
八皇后问题，是回溯算法的经典例子，它的规则要求是同一行同一列同一条斜线不能有两个皇后，不然会相互攻击。这条件听上去不难吧，可运算量却是惊人的多啊。
首先，程序是算法加数据结构，我这程序的数据结构是一个8*8的整型矩阵chessboard，全部初始化为0，这作为棋盘，每一格若为0则代表可以放棋子，另外还有一个长度为8的整型数组path，记录一次成功的排列，path[i]代表第i行棋子的位置。
然后，本程序有两个关键函数，
void setTrap(int*chessboard,int row,int column,int boardLength,char value)
该函数的含义是在row行column列放置棋子，并在同一行同一列同一斜线的格子加上value。
bool retreat(int*chessboard,int* path,int row,int boardLength)
该函数的含义是回退，在row行回退，返回是否成功，步骤是首先把当前行走的那一步撤销，然后再往前探测是否有可走的格子（value为0），若达到该行的尽头还没找到，返回false。
最后，就剩下启动函数了
for (int i=0; i<board_length; i++) {
for (int j=0; j<board_length; j++) {
if(chessboard[i*board_length+j]==0){
chessboard[i*board_length+j]=i+board_length;
setTrap(chessboard, i, j, board_length,i+board_length);
path[i]=j;
break;
}
else if (j==board_length-1) {
for (int k=i; k>0; k--) {
if (retreat(chessboard, path, k-1, board_length)) {
j=-1;
i=k;
break;
}
}
}
}
if (i==board_length-1&&path[board_length-1]!=-1) {
//succeed to get one solution
for (int i=0; i<board_length; i++) {
cout<<path[i]<<" ";
}
solutionCount++;
cout<<endl;
for (int k=i; k>=0; k--) {
if (retreat(chessboard, path, k, board_length)) {
i=k;
break;
}
}
}
}
本算法并未考虑棋盘旋转的情况，所以有不少重复的布局，故8*8的棋盘会有190中排列方式。
至此，本算法大体结束了，完整代码地址：http://download.csdn.net/detail/xanxus46/7078239
一段时间以后重新做回以前不会的算法，收获还是不少的。