#include "windows.h"
#define N 8 /* 定义棋盘大小 */
int place(int k)/* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */
void backtrack(int i)/* 主递归函数，搜索解空间中第i层子树 */
void chessboard()/* 每找到一个解,打印当前棋盘状态 */
static int sum, /* 当前已找到解的个数 */
x[N]/* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */
int main(void)
{
backtrack(0)
system("pause")
return 0
}
int place(int k)
{
/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */
/* x[k] 时，两皇后在同一列上；abs(k - j) == abs(x[j] - x[k]) 时，两皇 */
/* 后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。*/
for (int j = 0j <kj ++)
if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0
return 1
}
void backtrack(int t)
{
/* t == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案 */
if (t == N) chessboard()
else
for (int i = 0i <Ni ++) {
x[t] = i
if (place(t)) backtrack(t + 1)
}
}
void chessboard()
{
printf("第%d种解法:\n", ++ sum)
for (int i = 0i <Ni ++) {
for (int j = 0j <Nj ++)
if (j == x[i]) printf("@ ")
else printf("* ")
printf("\n")
}
printf("\n")
}
#include <stdio.h>#include <stdlib.h>#define TRUE 1 #define FALSE 0 void nqueen(int,int*)int attack (int,int,int*)void output(int,int*)void main() { int *queen,nprintf("输入皇后数量，个数不大于8\n")scanf("%d",&n)if(n>8){ printf("输入错误")return} queen=(int*)malloc(n*sizeof(int))if(queen==NULL) printf("分配内存失败")else { printf("%d皇后的结果如下\n",n)nqueen(n,queen)output(n,queen)} } void output(int n,int *queen) /*输出结果，*为空的格子，Q为皇后在的格子*/ { int i,jfor(i=0i<ni++) { printf("第%d行，第%d列为皇后位置",i,queen[i])for(j=0j<nj++) { if(j==queen[i]) printf("Q")else printf("*")} printf("\n")} } int attack (int row,int col,int *queen) /*测试（row,col)上的皇后是否遭受攻击，若是传1，若否传0*/ { int i=0,atk=FALSE while(!atk &&i<row) { atk=((queen[i]==col) || (queen[i]-col==row-i) || (queen[i]-i==col-row))i++} return atk} void nqueen(int n,int* queen) /*i为行数，j为列数,解决n皇后问题*/ { int i=0,j=0queen[i]=0while (i<n) { if(!attack(i,j,queen)) { queen[i]=jif(i==n-1) returnj=0i++} else { while(j>=n-1) { i--j=queen[i]+1} j++} } }
