Question

c语言编程：八皇后问题

八皇后问题是指求解如何在国际象棋8*8棋盘上无冲突地放置八个皇后棋子。因为在国际象棋里，皇后的移动方式是横竖交叉，所以在任意一个皇后所在位置的水平、竖直和斜45度线上都不可能有其他皇后的存在。一个完整无冲突的八皇后棋子分布称为八皇后问题的一个解。求所有解。要求使用递归算法。

Answer 1

/***八皇后问题**/

#include<stdio.h>
int row[8]= {0}, col[8] = {0};//四个辅助数组用来确定
int right[15] ={0},left[15] = {0};//是否那人能够放皇后
int sum = 0; //计数器,用来计共有多少组可行解
int X[8]; //用X[i]以及他的值表示皇后的位置
void OutPut()
{
int i,j;
for(i=0;i<=7;i++)
{
for(j=0;j<=7;j++)
{
if(j==X[i])
printf("A");
else
printf(".");
}
printf("\n");
}
}

void NQuene(int m) // 递归求解
{
int i = 0 ;
int flag ; // 标志变量
if(m>=8)
{
sum++;
printf("No %d:\n",sum);
OutPut();
}
else
{
for(i=0;i<8;i++)
{
X[m]=i ; //第m行i列
flag= row[m]||col[i]||right[m-i+7]||left[i+m];//flag为1表明此位置不能存放皇后
if(!flag) //标志为0表明可以存放皇后
{
row[m]=1 , col[i]=1; //X[m]=i后相应的位置后
right[m-i+7]=1, left[i+m]=1; //对应的辅助数组的相应位置标记为1
NQuene(m+1);
row[m]=0 , col[i] = 0; //递归后释放相应的数值
right[m-i+7]=0, left[i+m]= 0;
}//if
}//for
}//else
}
void main()
{
int m=0;
NQuene(m);
getch();
}