八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。例如，八皇后问题的一个解为：
显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，n皇后问题的可能解用一个n元向量X=(x1,x2, …,xn)表示，其中，1≤i≤n并且1≤xi≤n，即第i个皇后放在第i行第xi列上。
由于两个皇后不能位于同一列上，所以，解向量X必须满足约束条件：
xi≠xj （式1）
若两个皇后摆放的位置分别是(i, xi)和(j, xj)，在棋盘上斜率为-1的斜线上，满足条件i－j= xi－xj，在棋盘上斜率为1的斜线上，满足条件i＋j= xi＋xj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件：
|i－xi|≠|j－xj| （式2）
为了简化问题，下面讨论四皇后问题。
四皇后问题的解空间树是一个完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点
到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。
回溯法求解4皇后问题的搜索过程
下面附上八皇后问题的C代码，八皇后问题一共有92种方案
#include <stdio.h>
#include <math.h>
#define N_QUEENS 8
void Queen();
int Place(int * x, int k);
int solutions = 0; //总的解决方案数目
int main(void)
{
Queen();
printf("Total %d solutions\n", solutions);
return 0;
}
void Queen()
{
int i, k;
int x[N_QUEENS+1]; //为了表述方便，我们不使用x[0]，因此数组大小多加1
k = 1;
for (i = 1; i <= N_QUEENS; i++)//初始化
x[i] = 0;
while (k >= 1)
{
x[k]++;//在下一列放置第k个皇后
while (x[k] <= N_QUEENS && !Place(x, k))
x[k]++;//只要有冲突，就搜索下一列，试图找到第一个不冲突的
if (x[k] > N_QUEENS)//这说明第k行所有的都冲突，重置x[k]，回溯，这两行代码才是关键
{
x[k] = 0;
k--;
}
else if(k < N_QUEENS)//放置下一个皇后
{
k++;
}
else // 得到一个解，输出
{
for (i = 1; i <= N_QUEENS; i++)
printf("%d, ", x[i]);
printf("\n");
solutions++;
// return; //如果只想得到一个解，而不是所有的解，那么需要return 语句
}
}
}
int Place(int * x, int k)//考察皇后k放置在x[k]列是否发生冲突,发生冲突返回0，否则返回1
{
int i;
for (i = 1; i < k; i++)
if (x[k] == x[i] || abs(k-i) == abs(x[k]-x[i]))
return 0;
return 1;
}
参考 资料 ：北京科技大学 罗熊 《算法设计与分析》课件 第6章 回溯法