八皇后问题是一个古老而著名的问题。该问题是19世纪著名的数学家高斯1850年提出：在一个8*8国际象棋盘上，有8个皇后，每个皇后占一格；要求皇后之间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法？
回溯算法也叫试探法，它是一种搜索问题的解的方法。冋溯算法的基本思想是在一个包含所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
八皇后问题有很多中解法，其中使用回溯法进行求解是其中一种。而回溯发也是最直接的一种解法，也较容易理解。
八皇后问题的回溯法算法，可以采用一维数组来进行处理。数组的下标i表示棋盘上的第i列，a[i]的值表示皇后在第i列所放的位置。例如，a[1]=5，表示在棋盘的第例的第五行放一个皇后。程序中首先假定a[1]=1，表示第一个皇后放在棋盘的第一列的第一行的位置上，然后试探第二列中皇后可能的位置，找到合适的位置后，再处理后续的各列，这样通过各列的反复试探，可以最终找出皇后的全部摆放方法。
八皇后问题可以使用回溯法进行求解，程序实现如下：
#include<stdio.h>
#define Queens 8 //定义结果数组的大小，也就是皇后的数目
int a[Queens+1]; //八皇后问题的皇后所在的行列位置，从1幵始算起，所以加1
int main(){ int i, k, flag, not_finish=1, count=0; //正在处理的元素下标，表示前i-1个元素已符合要求，正在处理第i个元素 i=1; a[1]=1; //为数组的第一个元素赋初值
printf("八皇后的可能配置是:\n");
while(not_finish){ //not_finish=l:处理尚未结束 while(not_finish && i<=Queens){ //处理尚未结束且还没处理到第Queens个元素 for(flag=1,k=1; flag && k<i; k++) //判断是否有多个皇后在同一行 if(a[k]==a[i]) flag=0;
for (k=1; flag&&k<i; k++) //判断是否有多个皇后在同一对角线 if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) ) flag=0;
if(!flag){ //若存在矛盾不满足要求，需要重新设置第i个元素 if(a[i]==a[i-1]){ //若a[i]的值已经经过一圈追上a[i-1]的值 i--; //退回一步，重新试探处理前一个元素
if(i>1 && a[i]==Queens) a[i]=1; //当a[i]为Queens时将a[i]的值置1 else if(i==1 && a[i]==Queens) not_finish=0; //当第一位的值达到Queens时结束 else a[i]++; //将a[il的值取下一个值 }else if(a[i] == Queens) a[i]=1; else a[i]++; //将a[i]的值取下一个值 }else if(++i<=Queens) if(a[i-1] == Queens ) a[i]=1; //若前一个元素的值为Queens则a[i]=l else a[i] = a[i-1]+1; //否则元素的值为前一个元素的下一个值 }
if(not_finish){ ++count; printf((count-1)%3 ? "\t[%2d]:" : "\n[%2d]:", count);
for(k=1; k<=Queens; k++) //输出结果 printf(" %d", a[k]); if(a[Queens-1]<Queens ) a[Queens-1]++; //修改倒数第二位的值 else a[Queens-1]=1;
i=Queens -1; //开始寻找下一个满足条件的解 } }}
输出结果：
八皇后的可能配置是:
[ 1]: 1 5 8 6 3 7 2 4[ 2]: 1 6 8 3 7 4 2 5[ 3]: 1 7 4 6 8 2 5 3[ 4]: 1 7 5 8 2 4 6 3[ 5]: 2 4 6 8 3 1 7 5[ 6]: 2 5 7 1 3 8 6 4[ 7]: 2 5 7 4 1 8 6 3[ 8]: 2 6 8 3 1 4 7 5[ 9]: 2 6 1 7 4 8 3 5[10]: 2 7 3 6 8 5 1 4[11]: 2 7 5 8 1 4 6 3[12]: 2 8 6 1 3 5 7 4[13]: 3 5 7 1 4 2 8 6[14]: 3 5 8 4 1 7 2 6[15]: 3 5 2 8 1 7 4 6[16]: 3 5 2 8 6 4 7 1[17]: 3 6 8 1 4 7 5 2[18]: 3 6 8 1 5 7 2 4[19]: 3 6 8 2 4 1 7 5[20]: 3 6 2 5 8 1 7 4[21]: 3 6 2 7 1 4 8 5[22]: 3 6 2 7 5 1 8 4[23]: 3 6 4 1 8 5 7 2[24]: 3 6 4 2 8 5 7 1[25]: 3 7 2 8 5 1 4 6[26]: 3 7 2 8 6 4 1 5[27]: 3 8 4 7 1 6 2 5[28]: 3 1 7 5 8 2 4 6[29]: 4 6 8 2 7 1 3 5[30]: 4 6 8 3 1 7 5 2[31]: 4 6 1 5 2 8 3 7[32]: 4 7 1 8 5 2 6 3[33]: 4 7 3 8 2 5 1 6[34]: 4 7 5 2 6 1 3 8[35]: 4 7 5 3 1 6 8 2[36]: 4 8 1 3 6 2 7 5[37]: 4 8 1 5 7 2 6 3[38]: 4 8 5 3 1 7 2 6[39]: 4 1 5 8 2 7 3 6[40]: 4 1 5 8 6 3 7 2[41]: 4 2 5 8 6 1 3 7[42]: 4 2 7 3 6 8 1 5[43]: 4 2 7 3 6 8 5 1[44]: 4 2 7 5 1 8 6 3[45]: 4 2 8 5 7 1 3 6[46]: 4 2 8 6 1 3 5 7[47]: 5 7 1 3 8 6 4 2[48]: 5 7 1 4 2 8 6 3[49]: 5 7 2 4 8 1 3 6[50]: 5 7 2 6 3 1 4 8[51]: 5 7 2 6 3 1 8 4[52]: 5 7 4 1 3 8 6 2[53]: 5 8 4 1 3 6 2 7[54]: 5 8 4 1 7 2 6 3[55]: 5 1 4 6 8 2 7 3[56]: 5 1 8 4 2 7 3 6[57]: 5 1 8 6 3 7 2 4[58]: 5 2 4 6 8 3 1 7[59]: 5 2 4 7 3 8 6 1[60]: 5 2 6 1 7 4 8 3[61]: 5 2 8 1 4 7 3 6[62]: 5 3 8 4 7 1 6 2[63]: 5 3 1 6 8 2 4 7[64]: 5 3 1 7 2 8 6 4[65]: 6 8 2 4 1 7 5 3[66]: 6 1 5 2 8 3 7 4[67]: 6 2 7 1 3 5 8 4[68]: 6 2 7 1 4 8 5 3[69]: 6 3 5 7 1 4 2 8[70]: 6 3 5 8 1 4 2 7[71]: 6 3 7 2 4 8 1 5[72]: 6 3 7 2 8 5 1 4[73]: 6 3 7 4 1 8 2 5[74]: 6 3 1 7 5 8 2 4[75]: 6 3 1 8 4 2 7 5[76]: 6 3 1 8 5 2 4 7[77]: 6 4 7 1 3 5 2 8[78]: 6 4 7 1 8 2 5 3[79]: 6 4 1 5 8 2 7 3[80]: 6 4 2 8 5 7 1 3[81]: 7 1 3 8 6 4 2 5[82]: 7 2 4 1 8 5 3 6[83]: 7 2 6 3 1 4 8 5[84]: 7 3 8 2 5 1 6 4[85]: 7 3 1 6 8 5 2 4[86]: 7 4 2 5 8 1 3 6[87]: 7 4 2 8 6 1 3 5[88]: 7 5 3 1 6 8 2 4[89]: 8 2 4 1 7 5 3 6[90]: 8 2 5 3 1 7 4 6