Stack overflow error bruteforcing a magic square. Any possible solution?

Question

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

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.

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);.

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 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).

Any possible solution?

Answer 1

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

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

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)

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

So now we enter the code set m[pos] from the previous value (9) back to the value we started with (1) then we do the "recursive" step, calling generate_magic() with the values (n==3, pos=7, and m[pos]==1)

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

n == 3 and pos == 8
Now we have:
n == 3 and 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 and 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.

---

Side note:

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

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