四阶幻方 v1.1 向2064ms进发

改进了一下程序，在我的p4 3.2上以2064ms运算完7040个
到此告一段落，880的版本不想写了，麻烦，研究一下五阶的，好像好复杂。371993326789901217467999448150835200000000个组合，呼呼。

开头的两个include 是iostream 和time.h，万恶的代码显示器

cpp 代码

#include
#include

using namespace std;

struct uni
{
    int a,b,c,d;
};

uni can[3000];
int sum = 0,sum_all = 0;

void get_all_num()
{
    for(int i = 1;i <= 16;++i)
    {
        for(int j = 1;j <= 16;++j)
        {
            for(int k = 1; k <= 16; ++k)
            {
                for(int l = 1;l <= 16;++l)
                {
                    if(i != j && i != k && i != l && j != k && j != l && k != l)
                        if(i + j + k + l == 34)
                        {
                            can[sum].a = i;
                            can[sum].b = j;
                            can[sum].c = k;
                            can[sum].d = l;
                            ++sum;
                        }
                }
            }
        }
    }
}

void p_rint(const int sq[])
{
    cout << "i wIll gIvE yOu sOme coLoR 2CC! " << sum_all <
    cout << sq[0] << " " << sq[1] << " " << sq[2] << " " << sq[3] << endl;
    cout << sq[4] << " " << sq[5] << " " << sq[6] << " " << sq[7] << endl;
    cout << sq[8] << " " << sq[9] << " " << sq[10] << " " << sq[11] << endl;
    cout << sq[12] << " " << sq[13] << " " << sq[14] << " " << sq[15] << endl << endl;
}

bool caca(const int sq[])
{
    if(sq[0] + sq[4] + sq[8] + sq[12] !=34)
        return false;
    if(sq[2] + sq[6] + sq[10] + sq[14] !=34)
        return false;
    return true;
}

bool detec_2(const int sq[])
{
    int km2[17];
    int i,m;
    for(i = 0;i <= 16;++i)
    {
        km2[i] = 0;
    }

    for(m = 0;m < 16;++m)
    {
        km2[sq[m]]++;
        if(km2[sq[m]] > 1)
            return false;
    }

    return true;
}
bool detec_1(const int c1[],const int c2[])
{
    int km2[17],i;
    for(i = 0;i < 16;++i)
    {
        km2[i] = 0;
    }

    km2[c1[0] - 1]++;
    km2[c1[1] - 1]++;
    km2[c1[2] - 1]++;
    km2[c1[3] - 1]++;

    km2[c2[0] - 1]++;
    km2[c2[1] - 1]++;
    km2[c2[2] - 1]++;
    km2[c2[3] - 1]++;

    for(i = 0;i < 16;i++)
    {
        if(km2[i] > 1)
            return false;
    }

    return true;
}

void fill_in_line(const int c1[],const int c2[])
{
    int sq[16],k,l;

    sq[0] = c1[0];
    sq[5] = c1[1];
    sq[10] = c1[2];
    sq[15] = c1[3];

    sq[3] = c2[0];
    sq[6] = c2[1];
    sq[9] = c2[2];
    sq[12] = c2[3];

    for(k = 1;k <= 16;k++)
    {
        sq[4] = k;
        if(k != c1[0] && k != c1[1] && k != c1[2] && k != c1[3] && k != c2[0] && k != c2[1] && k != c2[2] && k != c2[3])
        {
            for(l = 1;l <= 16;++l)
            {
                sq[1] = l;
                if(l != sq[4])
                {
                    sq[7] = 34 - sq[4] - sq[5] - sq[6];
                    sq[11] = 34 - sq[3] - sq[7] - sq[15];
                    sq[8] = 34 - sq[9] - sq[10] - sq[11];
                    sq[13] = 34 - sq[1] - sq[5] - sq[9];
                    sq[14] = 34 - sq[12] - sq[13] - sq[15];
                    sq[2] = 34 - sq[0] - sq[1] - sq[3];

                    if(sq[7] > 0 && sq[11] > 0 && sq[8] > 0 && sq[13] > 0 && sq[14] > 0 && sq[2] > 0 &&
                       sq[7] <= 16 && sq[11] <= 16 && sq[8] <= 16 && sq[13] <= 16 && sq[14] <= 16 && sq[2] <= 16)
                    {
                            if((sq[0] + sq[1] + sq[4] + sq[5] == sq[10] + sq[11] + sq[14] + sq[15]) &&
                                (sq[2] + sq[3] + sq[6] + sq[7] == sq[8] + sq[9] + sq[12] + sq[13]) &&
                                caca(sq) && detec_2(sq))
                            {
                                sum_all++;
                                p_rint(sq);
                            }
                    }
                }
            }
        }
    }

}
void fill_in_eight()
{
    int cse1[4],cse2[4];

    for(int i = 0;i < sum;++i)
    {
        for(int j = 0;j < sum;++j)
        {
            if( i!=j )
            {
                cse1[0] = can[i].a;
                cse1[1] = can[i].b;
                cse1[2] = can[i].c;
                cse1[3] = can[i].d;

                cse2[0] = can[j].a;
                cse2[1] = can[j].b;
                cse2[2] = can[j].c;
                cse2[3] = can[j].d;

                if(detec_1(cse1,cse2))
                {
                    fill_in_line(cse1,cse2);
                }
            }

        }
    }
}

int main()
{
    time_t t;
    t = clock();

    get_all_num();
    fill_in_eight();

    cout << "time consumed: " << clock() - t << " ms"<< endl;
    return 0;
}

评论

1 楼 metaphy 2007-11-01  

大学时候用C写过一次，算法类似。
当时在学校机房的破机器上跑了2分多钟，也是7000多个解。