堆栈溢出错误暴力破解幻方。任何可能的解决方案？ [英] Stack overflow error bruteforcing a magic square. Any possible solution?

问题描述

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

Here my problem, for an exercise I need to generate a magic square by bruteforcing it in backtracking.

我想这可能是有用的矩阵分配为载体，改变坐标的功能。正如你可以用一个3x3幻方甚至想象它给了我一个堆栈溢出问题。

I thought it could be useful to allocate the matrix as a vector and a function that changes the coordinates. As you can imagine even with a 3x3 magic square it gave me a stack overflow problem.

调试它，我发现了这一点，或多或少，在发电的一半，更precisely其中函数 chk_magic（INT *米，INT N）叫 change_coord（I，J，M，N）; 。

Debugging it i discovered it happen, more or less, at half of the generating, more precisely where the function chk_magic(int *m, int n) call change_coord(i, j, m, n);.

这是整个code，在那里我已经签署了中断程序就行了。

Here it is the entire code, where I've signed the line that interrupt the program.

#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];
}

周围的Googling我发现，单号有这容易产生它的算法，但问题仍然存在为偶数（而且我的教授希望它暴力破解递归）。

Googling around I discovered that for odd numbers there is an algorithm which generate it easily, but the problem persist for even numbers (furthermore my professor want it with bruteforce recursion).

任何可能的解决方案？

推荐答案

这是功课，所以我不打算解决您的code ......不过，我会做一些分析，供您向您展示问题。 FYI：你真的应该学会使用调试器和跟踪您的code

This is homework, so I'm not going to fix your code... however I'll do some analysis for you to show you the issue. FYI: You really should learn to use a debugger and trace your code.

在这里你的大问题是，你的递归的逻辑只是来回反射两个街区之间，没有最低的一步，从而您填写太多的函数调用的缓冲区，并得到一个堆栈溢出：

Your big problem here is that your "recursive" logic just bounces back and forth between two blocks, there's no "lowest step" and thus you fill the buffer with too many function calls and get a stack overflow:

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）。

So when you call this function you have m* == your memory block, n == 3 and pos == 8 (3*3-1).

我把引号递归，因为你没有做一个递减的一步，这code每次调用运行 generate_magic（）用同样的参数一遍又一遍（ N 总是3， POS 始终是8个）

I put "recursive" in quotes, because you're not doing a decremental step, this code runs each time calling generate_magic() with the same parameters over and over again (n is always 3, pos is always 8)

经过几次反复 M [POS] 将递增1到9，现在，如果检查失败，我们跳下去下一个块：

After a few iterations m[pos] will increment from 1 up to 9, now that if check fails and we jump down to the next block:

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

所以，现在我们就从previous值输入code组M [POS]（9）回到我们开始（1），然后我们做了递归的步骤，称<$ c中的价值$ C> generate_magic（）与值（ n ==可3 ， POS = 7 和 M [POS] == 1 ）

好了，我们已经开始从头再来使用不同的值这个时候，对不对？我们第一次：

Ok, so we've started all over again with different values this time, right? First time we had:

n ==可3 和 POS == 8
结果现在我们有：结果
n ==可3 和 POS == 7

哎呀，但会发生什么，当我们打的第一个递归再调用？

Oops, but what happens when we hit that first "recursive" call again?

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

这是怎么回事我们的下一个条目重置：

That's going to reset our next entry to:

n ==可3 和 POS == 8

这是越来越行不通快。迟早所有的这些功能​​/参数推栈上会杀了我们，因为我们正在进入一个无限循环。

This is getting nowhere fast. Sooner or later all these function/parameter pushes on the stack will kill us because we're getting into an infinite loop.

边注：

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

您想的sizeof（INT），而不是的sizeof（INT *）因为你的字符串 INT 在你的矩阵，而不是指向 INT 秒。

You wanted sizeof(int), not sizeof(int*) since you're string ints in your matrix, not pointers to ints.

这篇关于堆栈溢出错误暴力破解幻方。任何可能的解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！