八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。例如，八皇后问题的一个解为：

#include
#include

#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章 回溯法