8皇后问题：如何在8 x 8的国际象棋棋盘上安排8个皇后，使得没有两个皇后能互相攻击？( 如果两个皇后处在同一行、同一列或同一条对角线上，则她们能互相攻击。）
解向量为长度为8的数组，记为solution。因为共有8个皇后，而棋盘刚好为8*8，所以每一行肯定会有一个皇后，那么我们约定solution[i]表示第i+1个皇后放在第i+1行的第几列。solution中的列从1开始记。
回溯算法的思路是对问题的状态空间树进行深度优先搜索，树的每一层节点代表了对解的每一个分量所做的选择。如果该节点表示的选择符合要求，那么继续向下搜索，否则，尝试下一个选择。如果该层的所有选择都已经尝试过，那么我们向上回溯。
递归版本：
void eight_queue_recursive( int *solution, int dimension, int row )
{//dimension表示棋盘的维数，row表示放置第几行的皇后
if( row > dimension ) return;
int i;
for( i = 0; i < dimension; ++i )//尝试每一列
{
solution[row-1] = i+1;
if( if_valid( solution, row ) )//如果合法
{
if( row < dimension )//还有皇后没放
eight_queue_recursive( solution, dimension, row+1 );
else
print( solution, dimension );
}
solution[row-1] = 0;
}
}
一般的回溯算法可以描述如下：
backtrack(k) for 每个x∈Xk if x is valid xk←x;将xk加入v if v 为最终解then print the solution else if v 是部分解then backtrack(k+1) end for
迭代版本：
void eight_queue( int *solution, int dimension )
{
int k = 0;//k表示第几个皇后
while( k >= 0 )//要判断k是否>0
{
while( solution[k] < dimension )//判断k是否会超过dimension
{
solution[k]+=1;
if( if_valid( solution, k+1 ) )
{
if( k < (dimension-1) )
++k;
else
print( solution, dimension );
}
}
solution[k] = 0;//回溯
--k;
}
}
在判断某个位置是否可以放皇后时，需要注意如下规律：
1.从左上角到右下角的主对角线或其平行线（斜率-1）上，下标之差（行号-列号）相
等。
2.斜率为+1的斜线上，元素的2个下标之和（行号+列号）值相等。
即若两个皇后的位置分别为（i,j)和（k,l),且i-j=k-l 或 i+j = k+l,那么这两个皇后位于一条斜线上。上面两个方程又和转化为i-k = j-l 和 i-k = l-j
即只要|i-k| = |l-j|,那么这两个皇后在一条斜线上，位置冲突.运用上面的规律，if_valid会大大简化。
今天上午写了非递归的，运行的时候竟然有几千个解，很纳闷，而且是重复着输出。调试了半天，原来是最外层的while循环条件应该是k>=0,最初写成了 k<dimension，但是这样也不应该输出几千个解啊，当k==-1时应该直接就崩溃了啊，所以应该是输出第92个结果后应该就段错误啊。这个想法害我不浅啊，怎么也看不出来什么错。最后就尝试输出solution[-1]，原以为会出现错误，结果真的输出来了啊。原来c语言中数组越界访问程序不是直接就崩溃的，以后写程序要注意了。
上面的程序同样适用于N皇后问题，试了一下，把8换成18后，程序竟然可以得到几十万个解，当然程序没跑完我就给停了。