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>}

分类: 电脑/网络 >>程序设计 >>其他编程语言

问题描述:

题目:在8*8的国际棋盘中，共有64个格子，最多将五个皇后放入棋盘中，就可以控制住整个棋盘，不论对方的棋子放在哪个格子中，都会被吃掉，编一个C程序，求出这样的五个“皇后”所有可能的布局。

解析:

楼主，你说的应该是8皇后问题吧？

这是个大概的源码，稍微改下应该就能用了

#include<stdio.h>

#define N 8

int col=1,row=1,slash=1,bslash=1

int a[N][N]

int p,q,k,l

int num=0

void trial(int i)

{

int j/*注 意，这里的j 一定要设为内部变量*/

if(i==N)

{

num++

for(k=0k

{

for(l=0l

{

if(a[k][l]==1)

printf("@")

else printf("*")

}

printf("n")

}

printf("nn")

getchar()

}

else

{

for(j=0j

{

for(k=0k

if(a[k][j]==1)

{

col=0

break

} /*列*/

p=i-1

q=j+1

while((p>=0)&&(q

{

if(a[p][q]==1)

{

slash=0

break

}

p--

q++

}

p=i-1

q=j-1/*对角*/

while((p>=0)&&(q>=0))

{

if(a[p][q]==1)

{

bslash=0

break

}

p--

q--

} /*斜对角*/

if((col==1)&&(slash==1)&&(bslash==1)) /*条件判断*/

{

a[i][j]=1

trial(i+1)

}

col=1slash=1bslash=1

a[i][j]=0

}

}

}

void main()

{

trial(0)

printf("%dn",num)

getchar()

}

---