回 帖 发 新 帖 刷新版面

主题:难道是递归的问题?

是一道八皇后问题
说明:
    问题的提出:八皇后是个古老而有趣的游戏,是由高斯于1850年首先提出的。
要求在国际象棋的棋盘上放置八个皇后,使其不能相互攻击,即任意两个皇后不能处于
棋盘的同一行、同一列和同一条对角线上。试问有多少种放法?
    基本思想是:先把皇后放在(0,0)位置,然后把1号皇后放在(1,j)位置,
使其满足要求。接着放2号皇后,依此类推。遇到某个皇后如把她无论放在该行的任意
位置均不满足要求,则前一个皇后放置不当,须重新放置前一皇后,如8个皇后均按要
求放置好,这就是一次成功的摆法。 

我在网上看到了一种递归的解法,程序可以得出正确结果。
问题在注释里,大家帮忙分析下。

int result = 1;
int chess[8];

// 根据前面几行的子,检查这一行所放的子是否合法
int check( int n )
{
 int i;
    for (i = 1; i <= n - 1; i++)
    {
     if (chess[n] == chess[i] + (n - i) || 
      chess[n] == chess[i] - (n - i) || 
      chess[n] == chess[i] ) 
      return 0;
    }
    return 1;
}
// 函数:打印结果
void show_chess(void)
{
 int i;
    printf("Result - %d\n", result);
    for (i = 1; i <= 8; i++)        // 当i = 8时,难道数组不会越界? 
    {
     printf("(%d): %d\n", i, chess[i]);
    }
    ++result;
}
// 递归函数:放子
void putchess( int n )
{
    int i;
    if (n <= 8)               //这里也是呀 
    {
     for (i = 1; i <= 8; i++)  // 将第n行从第一格(i)开始往下放
     {
      chess[n] = i;
      if (check(n) == 1) // 若可放,则检查是否放满
      {
       if (n == 8) 
          show_chess(); // 若已放满到8行时,则表示找出一种解,打印出来
       else 
         putchess(n + 1); // 若没放满则放下一行 putchess(n+1)
      }
    }
   }
}
int main()
{
    printf("This is for 8 X 8 matrix.\n");
    putchess(1); // 从每一行开始放子
    
    system("pause");
    return 0;
}

回复列表 (共6个回复)

沙发

越界了 只是没有出问题而已 说不定什么时候就出问题了
所以还是把int chess[8]改成int chess[9]比较好(如果不喜欢用chess[0]这个空间的话 )

板凳

这种比较简单:
#include<stdio.h>
#include<math.h>
int n=8;
int sum=0;
int x[8]={0};
int place(int k) /*约束函数*/
{
    int j;
    for(j=0;j<k;j++)
        if(fabs(k-j)==fabs(x[k]-x[j])||(x[k]==x[j])) return 0;
    return 1;
}
void backtruce(int t) /*回溯办法*/
{
    int i;
    if(t>=n){
        putchar('\n');
        printf("{");
        for(i=0;i<n;i++)
            printf("%2d",x[i]);
        printf("}");
    }
    else 
        for(i=0;i<n;i++){
            x[t]=i;
            if(place(t)) backtruce(t+1);
        }
}

void main(void)
{
    printf("本例利用回溯法求杰八皇后问题,答案以一维向量的形式输出,如{0,1,2,3,4,5,6,7}表示八个皇后分别放在第0行的第0列,第1行的第1列,第2行的第2列&#8226;&#8226;&#8226;\n");
   backtruce(0);
}

3 楼

我把chess[8]这个数组的大小该成任意的大小然后编译运行都没有问题,好像这个数组根本没有用,到底是怎么回事呀?我用的dev c++5.0和vs2008

4 楼

C默认应该是不会对越界进行判断的吧,尤其是在编译的时候不会自动检查,问题一般是出在运行时。

5 楼

问题是它运行是也没有错,到底是怎么回事呀?

6 楼

你好.我是全职网赚工作者.
如果你有时间有电脑.
想在网络上创业.请联系我..
项目绝对真实.详情QQ空间资料
加盟请联系 QQ908889846

我来回复

您尚未登录,请登录后再回复。点此登录或注册