c - 暴力破解幻方时出现堆栈溢出错误。有什么可能的解决办法吗？

Question

这是我的问题，对于一个练习，我需要通过在回溯中暴力破解它来生成魔方。

我认为将矩阵分配为 vector 和更改坐标的函数可能很有用。你可以想象，即使使用 3x3 幻方，它也会给我带来堆栈溢出问题。

调试它时我发现它或多或少发生在生成的一半，更准确地说是函数chk_magic(int *m, int n)调用change_coord(i, j) ，m，n)；。

这是完整的代码，我在其中签署了中断程序的行。

#include <stdio.h>
#include <stdlib.h>

int chk_magic(int*, int);
void generate_magic(int*, int, int);
int change_coord(int, int, int*, int);

int back_f;

int main()
{
    int i, j, n=3, *m;
    //printf("Inserisci la dimensione del quadrato: ");
    //scanf("%d", &n);

    m=malloc(n*n*sizeof(int*));
    for(i=0; i<(n*n); i++)
    {
        m[i]=1;
    }
    printf("Generazione in corso (se la dimensione e' maggiore di 4 potrebbero volerci minuti)...\n");
    generate_magic(m, n, n*n-1);
    for(i=0; i<n; i++)
    {
        for(j=0; j<n; j++)
        {
            printf("%3d ", change_coord(i, j, m, n));
        }
        printf("\n");
    }

    return 0;
}

int chk_magic(int *m, int n)
{
    int i, j, magic_n, orizzontal_buffer, vertical_buffer, flag;
    flag=0;
    magic_n=n*(n*n + 1)/2;

    for(i=0; i<n; i++)
    {
        orizzontal_buffer=0;
        vertical_buffer=0;

        for(j=0; j<n; j++)
        {
            orizzontal_buffer+=change_coord(i, j, m, n); // <<-- HERE! HALP!
            vertical_buffer+=change_coord(j, i, m, n);
        }
        if(vertical_buffer!=magic_n || orizzontal_buffer!=magic_n)
        {
            flag=1;
            return flag;
        }
    }
    orizzontal_buffer=0;
    vertical_buffer=0;
    for(i=0, j=n-1; i<n; i++, j--)
    {
        orizzontal_buffer=change_coord(i, i, m, n);
        vertical_buffer=change_coord(i, j, m, n);
    }
    if(vertical_buffer!=magic_n || orizzontal_buffer!=magic_n)
        {
            flag=1;
        }

    return flag;
}

void generate_magic(int *m, int n, int pos)
{
    if(m[pos]<n*n)
    {
        m[pos]++;
        back_f=chk_magic(m, n);
        if(back_f==0)
        {
            return;
        }
        generate_magic(m, n, n*n-1);
        return;
    }
    if(m[pos]==n*n)
    {
        if(back_f==0)
        {
            return;
        }
        m[pos]=1;
        generate_magic(m, n, pos-1);
        return;
    }
    if(pos==-1)
    {
        return;
    }
    return;
}

int change_coord(int x, int y, int *m, int dim)
{
    return m[(x*dim)+y];
}

谷歌搜索后我发现，对于奇数，有一种算法可以轻松生成它，但对于偶数，问题仍然存在(此外，我的教授希望通过暴力递归来实现)。

有什么可能的解决方案吗？

Answer 1

这是家庭作业，所以我不会修复你的代码...但是我会为你做一些分析来向你展示问题。仅供引用:您确实应该学习使用调试器并跟踪代码。

<小时/>

这里的大问题是你的“递归”逻辑只是在两个 block 之间来回反弹，没有“最低步骤”，因此你用太多函数调用填充缓冲区并导致堆栈溢出:

void generate_magic(int *m, int n, int pos)
{
    if(m[pos]<n*n)
    {
        m[pos]++;
        back_f=chk_magic(m, n);
        if(back_f==0)
        {
            return;
        }
        generate_magic(m, n, n*n-1);  <--- 'Recursive' step

所以当你调用这个函数时，你有m* ==你的内存块，n == 3和pos == 8( 3*3-1)。

我将“递归”放在引号中，因为您没有执行递减步骤，每次使用相同的参数一遍又一遍地调用 generate_magic() 时，此代码都会运行(n 始终为 3，pos 始终为 8)

经过几次迭代后，m[pos] 将从 1 增加到 9，现在如果检查失败，我们会跳到下一个 block :

if(m[pos]==n*n)
{
    if(back_f==0)
    {
        return;
    }
    m[pos]=1;
    generate_magic(m, n, pos-1);  <- 'Recursive' step

现在我们将代码集 m[pos] 从之前的值 (9) 输入到我们开始的值 (1)，然后执行“递归”步骤，调用 generate_magic() 值为 (n==3、pos=7 和 m[pos]==1)

好的，所以这次我们用不同的值重新开始，对吗？我们第一次:

n == 3 和 pos == 8
现在我们有:
n == 3 和 pos == 7

哎呀，但是当我们再次执行第一个“递归”调用时会发生什么？

generate_magic(m, n, n*n-1);

这会将我们的下一个条目重置为:

n == 3 和 pos == 8

这一切进展很快。迟早所有这些函数/参数压入堆栈都会杀死我们，因为我们进入了无限循环。

<小时/>

旁注:

malloc(n*n*sizeof(int*));

您需要 sizeof(int)，而不是 sizeof(int*)，因为您的矩阵中是字符串 int，而不是指针到ints。