用C语言写出八皇后算法

#include<stdio.h>
#include<stdlib.h>

#define MAX 8 // 定义棋盘大小为8

int queen[MAX]; // 用数组存放每个皇后所在的列数
int count = 0; // 记录解的个数

void print() // 输出解
{
int i,j;
printf("第%d个解为：\n",count);
for(i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
{
if(queen[i] == j) // 当前位置为皇后
printf("Q ");
else
printf("* "); // 当前位置为空
}
printf("\n");
}
printf("\n");
}

int check(int n) // 判断当前位置是否合法
{
int i;
for(i=0;i<n;i++)
if(queen[i] == queen[n] || abs(queen[i]-queen[n]) == abs(i-n))
return 0; // 与前面的皇后在同一列或对角线上，不合法
return 1;
}

void backtrack(int n) // 回溯法
{
int i;
if(n == MAX)
{
count++;
print();
return;
}
for(i=0;i<MAX;i++)
{
queen[n] = i; // 皇后放在第i列
if(check(n)) // 判断是否合法
backtrack(n+1); // 继续尝试下一个皇后的位置
}
}

int main()
{
backtrack(0);
printf("共有%d个解\n",count);
return 0;
}