0

ここで私の問題です。演習では、バックトラックでブルートフォースして魔方陣を生成する必要があります。

行列をベクトルと座標を変更する関数として割り当てると便利だと思いました。ご想像のとおり、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];
}

グーグルで調べてみると、奇数の場合は簡単に生成するアルゴリズムがあることがわかりましたが、偶数の場合は問題が解決しません（さらに、私の教授はブルートフォース再帰でそれを望んでいます）。

可能な解決策はありますか？

4

1 に答える 1