问题描述：使用回溯法解决N皇后问题时，1到8都没有问题，九算到一大半就报错了
本帖最后由 t6am3 于 2018-3-18 10:55 编辑如描述， 编译环境VC6.0 使用回溯法，一到八都没有问题， 算9的时候算了一大半了，突然溢出了，代码如下
#include <stdio.h>
#define M 9
int Stack;//记录路径的栈
int pr = -1;//栈顶指针
int count = 0;//完成计数器
int CanWe( int (*chess), int i, int j )//判断此位置是否能下
{
int k;
for( k=0; k < i; k++ )
if( chess == 1 )
return 0;
for( k=1; i-k >-1 && j+k < M; k++ )
if( chess == 1 )
return 0;
for( k=1; i-k > -1 && j-k > -1; k++ )
if( chess == 1 )
return 0;
return 1;
}
void init( int (*chess) )//初始化
{
int i, j;
for( i=0; i < M; i++ )
{
for( j=0; j < M; j++ )
chess = 0;
}
}
void print( int (*chess) )//打印当前棋盘
{
int i, j;
for( i=0; i < M; i++ )
{
for( j=0; j < M; j++ )
{
printf("%d", chess);
if( j != M-1 )
printf(" ");
}
putchar('\n');
}
printf("\n\n");
}
void Move( int (*chess), int i, int j )
{
while( j < M )//如果这一行还有商量的余地
{
if( CanWe(chess, i, j) )
{
chess = 1;
Stack[++pr] = j;
break;
}
j++;
}
if( j == M )//如果这一行没得谈就退栈， 上一步重新下
{
j = Stack;
chess = 0;//把下过的痕迹消除
if( !( pr == -1 && j == M-1 ) )//只要不是退栈到栈空且一颗子都无法落就继续下棋
Move(chess, i-1, j+1);
}
else if( i == M-1 )
{
print(chess);//如果最后一颗子都下了 就打印棋盘并计数
count++;
chess = 0;//把最后一步抹了
pr--;
j = Stack;
chess = 0;//把倒数第二步给抹了重新下
Move(chess, i-1, j+1);
}
else if( i != M-1 )//如果这次下了，而棋子还没下完就继续下
Move(chess, i+1, 0);
}
int main()
{
int chess;
init(chess);
Move(chess, 0, 0);
printf("Totally %d methods\n", count);
} {:10_266:}就没有大佬愿意救一下我这个小萌新吗……跨考考研CS大后天就机试了，请各位大佬走过路过给我看看啊！
页:
[1]