C语言八皇后问题

解题分析:这个问题是由高斯首先提出的。

解决这一问题的最直接方法是穷举出所有摆法。我们先用回溯的思想按行递推出一种合理方案。开始棋盘为空，第一个皇后可以放在第一行的任意一个位置。我们把它试置在芦核（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=1i<=ni++)<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=1i<=ni++)<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>}

八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线庆段上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象誉颂誉棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述樱猜更形象、更生动，使教学能产生良好的效果。下面是用Turbo C实现的八皇后问题的图形程序，能够演示全部的92组解。八皇后问题动态图形的实现

如下是8皇后的程序：

#include<stdio.h>

#include<stdlib.h>

void eightqueen(int a[][99],int n)

void print(int a[][99])

int up(int a[][99],int row,int col)

int down(int a[][99],int row,int col)

int left(int a[][99],int row,int col)

int right(int a[][99],int row,int col)

int num=0

main()

{

int a[99][99]={0},n //将皇后的位置放在一个二维的数组里面，a[i][j]=1表示该位置有一个皇后

eightqueen(a,0)

system("pause")

return 0

}

void print(int a[][99]) //输出当前的一种合理的走法。

{

int i,row,col

printf("Case %d\n",num)

for(row=0row<8row++)

{

for(col=0col<8col++)

{

printf("%d ",a[row][col])

}

printf("\n")

}

printf("\n")

}

void eightqueen(int a[][99],int row) //通过回溯法计算8皇没备后的走法。

{

int col,i

for(col=0col<=7col++)

{

//判断都前位置是否是合理的位置。

if ((up(a,row,col)==0)&&(down(a,row,col)==0)&&(left(a,row,col)==0)&&(right(a,row,col)==0))

{

a[row][col]=1//如果是，将当前位置置为1（摆放一个皇后）

if(row==7) //所有的8个皇后都已经摆放好了，输出当前的情况。

{

num++

print(a)

}

else

{

eightqueen(a,row+1)//在row+1摆放下一个皇后。

}

a[row][col]=0

}

}

}

//判断同一行岩唤列是否有其他的皇后

int up(int a[][99],int row,int col)

{

int i

for(i=0i<8i++)

{

if(a[i][col]==1)

{

return 1

}

}

return 0

}

//粗察凯判断同一行上是否有其他的皇后

int down(int a[][99],int row,int col)

{

int i

for(i=0i<8i++)

{

if(a[row][i]==1)

{

return 1

}

}

return 0

}

//判断左上到右下的对接线上是否有其他的皇后

int left(int a[][99],int row,int col)

{

int i

for(i=0i<8i++)

{

if(((row+i)<8)&&((col+i)<8))

{

if(a[row+i][col+i]==1)

{

return 1

}

}

if(((row-i)>=0)&&((col-i)>=0))

{

if(a[row-i][col-i]==1)

{

return 1

}

}

}

return 0

}

//判断左下到右上的对接线上是否有其他的皇后

int right(int a[][99],int row,int col)

{

int i

for(i=0i<8i++)

{

if(((row+i)<8)&&((col-i)>=0)) //

{

if(a[row+i][col-i]==1)

{

return 1

}

}

if(((row-i)>=0)&&((col+i)<8)) //这儿的判断有问题，

{

if(a[row-i][col+i]==1)

{

return 1

}

}

}

return 0

}

---