magic.cpp

解决16 * 16幻方问题的解决办法。算法非常好

// -------------------------------------------------------------------------
// class Magic 

#include <stdio.h>
#include <windows.h>

typedef unsigned OpType; 

enum ConstValue
{
    dimValue = 4,                                           // 维数
    sizeValue = dimValue * dimValue,                        // 数据个数
    sumValue = sizeValue * (sizeValue-1) / 2 / dimValue,    // 和数
}; 

enum OpCode
{
    opFill    = 0x00000,    // 填充(参数个数n) arg1, arg2 ... argn
    opCalc    = 0x10000,    // 计算(参数个数n=4) 待计算项(arg1), arg2, arg3, arg4
    opLT    = 0x20000,      // 小于(参数个数n=2) arg1, arg2
    opcodeMask = 0xf0000,
}; 

const OpType _g_sprmList[] = // 如果dimValue != 4，需要改写这里
{
    opFill|3,        0, 1, 2,
    opLT  |2,        1, 2,
    opCalc|4,        3, 0, 1, 2,
    opFill|3,        4, 5, 6,
    opCalc|4,        7, 4, 5, 6,
    opFill|1,        8,
    opCalc|4,        12, 0, 4, 8,
    opCalc|4,        9, 3, 6, 12,
    opCalc|4,        13, 1, 5, 9,
    opFill|1,        10,
    opCalc|4,        11, 8, 9, 10,
    opCalc|4,        14, 2, 6, 10,
    opCalc|4,        15, 0, 5, 10,
}; 

const OpType* _g_sprmEnd = _g_sprmList + sizeof(_g_sprmList)/sizeof(OpType); 

class Magic
{
private:
    bool m_isUsed[sizeValue];            // 哪些数用过了。
    unsigned m_nFillValue[sizeValue];    // 所填充的值。
    unsigned m_nResultCount; 

    void _Calc(const OpType* arg, const OpType* sprmNext)
    {
        unsigned nCalcValue = sumValue;
        for (int i = 1; i < dimValue; ++i)
            nCalcValue -= m_nFillValue[arg[i]]; 

        if (nCalcValue >= sizeValue || m_isUsed[nCalcValue])
            return; 

        m_nFillValue[arg[0]] = nCalcValue;
        m_isUsed[nCalcValue] = true;
        _Exec(sprmNext);
        m_isUsed[nCalcValue] = false;
    } 

    void _Fill(const OpType* arg, const OpType* sprmNext)
    {
        for (unsigned nValue = 0; nValue < sizeValue; ++nValue)
        {
            if (!m_isUsed[nValue])
            {
                m_nFillValue[*arg] = nValue;
                m_isUsed[nValue] = true;
                if (arg+1 == sprmNext)
                    _Exec(sprmNext);
                else
                    _Fill(arg+1, sprmNext);
                m_isUsed[nValue] = false;
            }
        }
    } 

    void _LT(const OpType* arg, const OpType* sprmNext)
    {
        if (m_nFillValue[arg[0]] < m_nFillValue[arg[1]])
        {
            _Exec(sprmNext);
        }
    } 

    void _Exec(const OpType* sprm)
    {
        if (sprm == _g_sprmEnd)
        {
#if (1) // 是否输出结果
            const unsigned* nValue = m_nFillValue;
            ++m_nResultCount;
            printf("\n---> result %d:\n", m_nResultCount);
            for (int i = 0; i < dimValue; ++i)
            {
                for (int j = 0; j < dimValue; ++j)
                {
                    printf("%2d ", 1 + *nValue++);
                }
                printf("\n");
            }
#endif
        }
        else
        {
            const OpType opcode = (*sprm & opcodeMask);
            const OpType oplen = (*sprm++ & ~opcodeMask);
            const OpType* sprmNext = sprm + oplen;
            if (opcode == opCalc)
                _Calc(sprm, sprmNext);
            else if (opcode == opFill)
                _Fill(sprm, sprmNext);
            else
                _LT(sprm, sprmNext);
        }
    } 

public:
    void Run()
    {
        DWORD tick1 = GetTickCount(); 

        m_nResultCount = 0;
        for (int i = 0; i < sizeValue; ++i)
            m_isUsed[i] = false; 

        _Exec(_g_sprmList);
        
        DWORD tick2 = GetTickCount();
        printf("\n--> elapsed %d ticks!\n", tick2 - tick1);
    }
}; 

  

int main()
{
    Magic magic; 

    magic.Run();
    getchar();
    return 0;
}