八皇后问题，是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

 

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。

#include <stdio.h>
int Queenes[8]={0},Counts=0;
int Check(int line,int list){//遍历该行之前的所有行int index;for (index=0; index<line; index++) {//挨个取出前面行中皇后所在位置的列坐标int data=Queenes[index];//如果在同一列，该位置不能放if (list==data) {return 0;}//如果当前位置的斜上方有皇后，在一条斜线上，也不行if ((index+data)==(line+list)) {return 0;}//如果当前位置的斜下方有皇后，在一条斜线上，也不行if ((index-data)==(line-list)) {return 0;}}//如果以上情况都不是，当前位置就可以放皇后return 1;
}
//输出语句
void print()
{printf("第%d种解法：\n",Counts);int line;for (line = 0; line < 8; line++){int list;for (list = 0; list < Queenes[line]; list++)printf("* ");printf("0 ");for (list = Queenes[line] + 1; list < 8; list++){printf("* ");}printf("\n");}printf("================\n\n");}
void eight_queen(int line){//在数组中为0-7列int list;for (list=0; list<8; list++) {//对于固定的行列，检查是否和之前的皇后位置冲突if (Check(line, list)) {//不冲突，以行为下标的数组位置记录列数Queenes[line]=list;//如果最后一样也不冲突，证明为一个正确的摆法if (line==7) {//统计摆法的Counts加1Counts++;//输出这个摆法print();//每次成功，都要将数组重归为0Queenes[line]=0;return;}//继续判断下一样皇后的摆法，递归eight_queen(line+1);//不管成功失败，该位置都要重新归0，以便重复使用。Queenes[line]=0;}}
}
int main() {//调用回溯函数，参数0表示从棋盘的第一行开始判断eight_queen(0);printf("摆放的方式有%d种",Counts);return 0;
}