Question

C语言八皇后问题

八皇后问题：在国际象棋中，能否在空棋盘上摆放八个皇后，并使其中任意两个皇后不能在同一行或同一列或同一对角线上，并编写完整的摆放八皇后问题的程序。要求：第一个皇后的起始位置由键盘输入，国际象棋的棋盘为8*8的方格。

Answer 1

解题分析:这个问题是由高斯首先提出的。
解决这一问题的最直接方法是穷举出所有摆法。我们先用回溯的思想按行递推出一种合理方案。开始棋盘为空，第一个皇后可以放在第一行的任意一个位置。我们把它试置在（1，1）。这样，满足J=1或I=J的格子都不能再放皇后了。第二个皇后置在第二行，J可取3..8中的任意一列，我们先试放在（2，3）。那么第三行的J可以取4..8，先试（3，4）。以此类推，第四个皇后在（4，2）（（4，7），（4，8）也可）；然后是（5，6）（（5，8）也可）；第六行就只有（6，8）这一个位置可选。这时，第七行已没有空位置可放，说明前面皇后的位置试选得不对。回溯到上一行，由于第六行已没有其他位置可选择，只能删除（6，8）这个皇后，再退到第五行，把（5，6）的皇后移到（5，8）。这样，第六行又没有可选位置了，回溯到第四行，把（4，2）移到（4，7）……最后，得出第一种可行方案：（1，1），（2，5），（3，8），（4，6），（5，3），（6，7），（7，2），（8，4）。
我们可以编写一个程序，让计算机按上述思路穷举出所有摆法(网上也很多，搜“八皇后”)。经计算机穷举，共有92种摆法。其实，这其中只有12种基本摆法，每种基本摆法又可经对称（水平、竖直、及沿两对角线翻转）、旋转（90、180、270度）等几何变换得出另外7种。这8种摆法的实质是一样的。那么，摆法共应有12*8=96种，为什么是92种呢？原来，在这12种基本摆法中，有一种是中心对称图形！用国际象棋记录法是：a4,b6,c8,d2,e7,f1,g3,h5.
推而广之还有所谓“N皇后问题”，即 在N*N的棋盘上，放置N个皇后。4皇后有2个答案，5后有10答，6后有4答，7后有40答，9后有352答，10后有724答。 超级简单，自己写的N皇后：(如果你硬要八就将N改为8就行了)源程序如下:
#include<stdio.h>
int q[20];
int count=0;
void print(int n)
{int i;<br>count++;<br>for(i=1;i<=n;i++)<br> {printf("(%d,%d)",i,q[i]);<br> }
printf("\n");
}
int Place(int i,int k)
{int j;<br>j=1;<br>while(j<k)<br> {if((q[j]==i) || abs(q[j]-i)==abs(j-k)) return 0;<br> j++;<br> }
return 1;
}
void Queens(int k,int n)
{int i;<br>if(k>n)<br> print(n);<br>else<br> {for(i=1;i<=n;i++)<br> if(Place(i,k)==1) <br> {q[k]=i;<br> Queens(k+1,n);<br> }
}
}
int main()
{int n;<br>scanf("%d",&n);<br>Queens(1,n);<br>getch();<br>return 0;<br>}

Answer 2

#include <stdio.h>
#define N 8
void main()
{
void move(int a[][N],int n);
int Judge(int a[][N]);
//a[N][N]表示棋盘，每个元素表示一个位置，为0表示没有放置皇后，为1表示放置皇后
//num记录摆放方法的数目
int a[N][N]={0},i,j,n=0,num=0;
//初始条件，让每个皇后都处于每行的第一列
for(i=0;i<N;i++)
a[i][0]=1;
//判断是否所有的皇后都移到最后一列了
while(!n)
{
move(a,N-1);
if(Judge(a))
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if (a[i][j])
printf("%2d",j);
/*
for(j=0;j<N;j++)
printf(" %d",a[i][j]);
printf("\n");
*/
}
num++;
printf("\t\t%d\n",num);
}
//只有所有的皇后都移到最后一列时，最后一列值均为1，他们的乘积为1；否则为0
for(i=0,n=1;i<N;i++)
n*=a[i][N-1];
}
}
//是否符合规则
int Judge(int a[][N])
{
int sum,x,y,i,j,k;

for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if(a[i][j])
{
//求同一列的皇后数，用于判断是否有皇后处于同一列

for(k=0,sum=0;k<N;k++)
if(a[k][j])
sum++;
//判断是不是在同一列，同一列数目超过1了
if(sum>1)
return(0);
//同行就不用判断了，因为赋初值时，每行只有一个皇后 //判断是不是在同一对角线上
//左上
for(x=i-1,y=j-1;x>=0&&y>=0;x--,y--)
if(a[x][y])
return(0);
//右下
for(x=i+1,y=j+1;x<N&&y<N;x++,y++)
if(a[x][y])
return(0);
//左下
for(x=i-1,y=j+1;x>=0&&y<N;x--,y++)
if(a[x][y])
return(0);
//右上
for(x=i+1,y=j-1;x<N&&y>=0;x++,y--)
if(a[x][y])
return(0);
}
}
return(1);
}
//将第n行的皇后向后移动一个位置
void move(int a[][N],int n)
{
int j;
for(j=0;j<N;j++)
if(a[n][j])
if(j<N-1) //不是最后一列时，向下一列移动
{
a[n][j]=0;
a[n][j+1]=1;
return;
}
else //是最后一列时，向本行列首移动，并且移动上一行
{
a[n][j]=0;
a[n][0]=1;
move(a,n-1);
return;
}
}

Answer 3

#include <stdio.h> static char Queen[8][8]; /*存放棋盘*/
static int a[8]; /*存放棋盘列的状况*/
static int b[15]; /*存放棋盘主对角线的状况*/
static int c[15]; /*存放棋盘从对角线的状况*/
static int iQueenNum=0; /*存放方法次数*/ void qu(int i); int main(int argc, char *argv[])
{
int iLine,iColumn; /* 行 列*/ /*初始化棋盘*/
for (iLine=0;iLine <8;iLine++){
a[iLine] = 0;
for (iColumn=0;iColumn <8;iColumn++){
Queen[iLine][iColumn] = '* ';
}
}
/*初始化主, 从对角线*/
for (iLine=0;iLine <15;iLine++){
b[iLine] = c[iLine] = 0;
} qu(0);

system( "pause ");
return 0;
} void qu(int i){
int iColumn; for (iColumn=0;iColumn <8;iColumn++){
if (a[iColumn]==0 && b[i-iColumn+7]==0 && c[i+iColumn]==0){ /*判断是否可以摆放皇后*/
Queen[i][iColumn] = '@ ';
a[iColumn] = 1; /*标记此位置已经摆放*/
b[i-iColumn+7] = 1; /*标记此位置已经摆放*/
c[i+iColumn] = 1; /*标记此位置已经摆放*/ if (i <7){ /*继续进行遍历*/
qu(i+1);
} else{ /*输出棋盘状态*/
int iLine,iColumn;
printf( "%d\n ",++iQueenNum);
for (iLine=0;iLine <8;iLine++){
for (iColumn=0;iColumn <8;iColumn++){
printf( "%c ",Queen[iLine][iColumn]);
}
printf( "\n ");
}
printf( "\n\n\n ");
system( "pause ");
}

/*如果出现错误, 则回溯*/
Queen[i][iColumn] = '* ';
a[iColumn] = 0;
a[i-iColumn+7] = 0;
c[i+iColumn] = 0;
}
}