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

t6am3 · 发表于 2018-3-18 12:12:50

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

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

x

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

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

登录/注册后可看大图

（前天发的这个帖子沉了，

，跨考考研复试在即，十分着急，加悬赏再发一次。。（怎么加啊啊啊啊啊啊。。。））

#include <stdio.h>

#define M 9

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

int CanWe( int (*chess)[M], int i, int j )//判断此位置是否能下
{
    int k;
    for( k=0; k < i; k++ )
        if( chess[k][j] == 1 )
            return 0;
    for( k=1; i-k >-1 && j+k < M; k++ )
        if( chess[i-k][j+k] == 1 )
            return 0;
    for( k=1; i-k > -1 && j-k > -1; k++ )
        if( chess[i-k][j-k] == 1 )
            return 0;
    return 1;
}

void init( int (*chess)[M] )//初始化
{
    int i, j;
    for( i=0; i < M; i++ )
    {
        for( j=0; j < M; j++ )
            chess[i][j] = 0;
    }
}

void print( int (*chess)[M] )//打印当前棋盘
{
    int i, j;
    for( i=0; i < M; i++ )
    {
        for( j=0; j < M; j++ )
        {
            printf("%d", chess[i][j]);
            if( j != M-1 )
                printf(" ");
        }
        putchar('\n');
    }
    printf("\n\n");
}

void Move( int (*chess)[M], int i, int j )
{
    while( j < M )//如果这一行还有商量的余地
    {
        if( CanWe(chess, i, j) )
        {
            chess[i][j] = 1;
            Stack[++pr] = j;
            break;
        }
        j++;
    }
    if( j == M )//如果这一行没得谈就退栈， 上一步重新下
    {
        j = Stack[pr--];
        chess[i-1][j] = 0;//把下过的痕迹消除
        if( !( pr == -1 && j == M-1 ) )//只要不是退栈到栈空且一颗子都无法落就继续下棋
            Move(chess, i-1, j+1);
    }
    else if( i == M-1 )
    {
        print(chess);//如果最后一颗子都下了 就打印棋盘并计数
        count++;     
        chess[i][j] = 0;//把最后一步抹了
        pr--; 
        j = Stack[pr--];
        chess[i-1][j] = 0;//把倒数第二步给抹了重新下
        Move(chess, i-1, j+1);  
    }
    else if( i != M-1 )//如果这次下了，而棋子还没下完就继续下
        Move(chess, i+1, 0);
}

int main()
{
    int chess[M][M];

    init(chess);

    Move(chess, 0, 0);

    printf("Totally %d methods\n", count);
}

最佳答案

月排行榜 / 总排行榜

累丶点

2018-3-18 14:23:16