鱼C论坛

 找回密码
 立即注册
查看: 1796|回复: 5

[已解决]问题描述:使用回溯法解决N皇后问题时,1到8都没有问题,九算到一大半就报错了

[复制链接]
发表于 2018-3-18 12:12:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 t6am3 于 2018-3-18 12:44 编辑

如描述, 编译环境VC6.0 使用回溯法,一到八都没有问题, 算9的时候算了一大半了,突然溢出了,代码如下


                               
登录/注册后可看大图


(前天发的这个帖子沉了, , 跨考考研复试在即, 十分着急, 加悬赏再发一次。。(怎么加啊啊啊啊啊啊。。。))
  1. #include <stdio.h>

  2. #define M 9

  3. int Stack[M];//记录路径的栈
  4. int pr = -1;  //栈顶指针
  5. int count = 0;//完成计数器

  6. int CanWe( int (*chess)[M], int i, int j )//判断此位置是否能下
  7. {
  8.     int k;
  9.     for( k=0; k < i; k++ )
  10.         if( chess[k][j] == 1 )
  11.             return 0;
  12.     for( k=1; i-k >-1 && j+k < M; k++ )
  13.         if( chess[i-k][j+k] == 1 )
  14.             return 0;
  15.     for( k=1; i-k > -1 && j-k > -1; k++ )
  16.         if( chess[i-k][j-k] == 1 )
  17.             return 0;
  18.     return 1;
  19. }

  20. void init( int (*chess)[M] )//初始化
  21. {
  22.     int i, j;
  23.     for( i=0; i < M; i++ )
  24.     {
  25.         for( j=0; j < M; j++ )
  26.             chess[i][j] = 0;
  27.     }
  28. }

  29. void print( int (*chess)[M] )//打印当前棋盘
  30. {
  31.     int i, j;
  32.     for( i=0; i < M; i++ )
  33.     {
  34.         for( j=0; j < M; j++ )
  35.         {
  36.             printf("%d", chess[i][j]);
  37.             if( j != M-1 )
  38.                 printf(" ");
  39.         }
  40.         putchar('\n');
  41.     }
  42.     printf("\n\n");
  43. }

  44. void Move( int (*chess)[M], int i, int j )
  45. {
  46.     while( j < M )//如果这一行还有商量的余地
  47.     {
  48.         if( CanWe(chess, i, j) )
  49.         {
  50.             chess[i][j] = 1;
  51.             Stack[++pr] = j;
  52.             break;
  53.         }
  54.         j++;
  55.     }
  56.     if( j == M )//如果这一行没得谈就退栈, 上一步重新下
  57.     {
  58.         j = Stack[pr--];
  59.         chess[i-1][j] = 0;//把下过的痕迹消除
  60.         if( !( pr == -1 && j == M-1 ) )//只要不是退栈到栈空且一颗子都无法落就继续下棋
  61.             Move(chess, i-1, j+1);
  62.     }
  63.     else if( i == M-1 )
  64.     {
  65.         print(chess);//如果最后一颗子都下了 就打印棋盘并计数
  66.         count++;     
  67.         chess[i][j] = 0;//把最后一步抹了
  68.         pr--;
  69.         j = Stack[pr--];
  70.         chess[i-1][j] = 0;//把倒数第二步给抹了重新下
  71.         Move(chess, i-1, j+1);  
  72.     }
  73.     else if( i != M-1 )//如果这次下了,而棋子还没下完就继续下
  74.         Move(chess, i+1, 0);
  75. }

  76. int main()
  77. {
  78.     int chess[M][M];

  79.     init(chess);

  80.     Move(chess, 0, 0);

  81.     printf("Totally %d methods\n", count);
  82. }
复制代码
最佳答案
2018-3-18 14:23:16
t6am3 发表于 2018-3-18 14:18
请问你装了VC6.0 编译器吗 我的就是, 难道是调用堆栈过多溢出?…… 有这种溢出理由的吗?

VC的原因,你可以换一个编译器就可以了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-18 13:18:05 | 显示全部楼层
9不是对了吗?请问哪里错了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-18 13:20:10 | 显示全部楼层
累丶点 发表于 2018-3-18 13:18
9不是对了吗?请问哪里错了

我这边dev运行没有报错,也没有溢出
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2018-3-18 14:18:21 | 显示全部楼层
累丶点 发表于 2018-3-18 13:20
我这边dev运行没有报错,也没有溢出

请问你装了VC6.0 编译器吗 我的就是, 难道是调用堆栈过多溢出?…… 有这种溢出理由的吗?
1521353804(1).jpg
1521353850(1).jpg
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-18 14:23:16 | 显示全部楼层    本楼为最佳答案   
t6am3 发表于 2018-3-18 14:18
请问你装了VC6.0 编译器吗 我的就是, 难道是调用堆栈过多溢出?…… 有这种溢出理由的吗?

VC的原因,你可以换一个编译器就可以了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-3-18 14:28:47 | 显示全部楼层
累丶点 发表于 2018-3-18 14:23
VC的原因,你可以换一个编译器就可以了

好的, 谢谢!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 21:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表