魔方和回溯 C++

Question

我必须编写一个程序来求解 NxN 幻方，数字从 1 到 N^2。它适用于 3x3，部分填充的 4x4，但是，在两个小时内，它无法找到部分填充的 5x5 的解决方案。

这是我的代码：

#include <iostream>
#include <fstream>
#include <string.h>

const int N = 3;
const int Possibili_N = N*N;
const int Magic_Constant = (N*((N*N)+1))/2;

using namespace std;

class MagicSquare{
    bool Num_Possibili[Possibili_N];  // true se non è stato preso, false se è stato preso
    int Square[N][N];
    int BackTracking_Cicle;
    int N_Square;

    void Set_NumPossibili();
    bool SearchEmpty(int &Row, int &Col);
    bool CheckSum();
    bool CheckRows();
    bool CheckCols();
    bool CheckDiags();
    void Set_BackTrackingCicle()        { BackTracking_Cicle = 0;};
    void Increase_BackTrackingCicle()   { BackTracking_Cicle++; };
    void Set_NSquare()                  { N_Square = 0;};
    void Increase_NSquare()             { N_Square++; };

public:
    MagicSquare(){};
    ~MagicSquare(){};
    bool Set_MagicSquare(string FilePath);
    bool Calc_MagicSquare();
    void Stamp_MagicSquare();
    int Get_BackTrackingCicle()         { return BackTracking_Cicle; };
    int Get_NSquare()                   { return N_Square; }
};
bool MagicSquare::Set_MagicSquare(string FilePath)
{   ifstream StartFile;
    StartFile.open(FilePath.c_str(), ios::in);
    string Buffer;

    if(StartFile.is_open())
    {   Set_NumPossibili();
        Set_BackTrackingCicle();
        Set_NSquare();

        for(int i=0; i<N; i++)
        {   getline(StartFile, Buffer);

            for(int j=0, k=0; j<N; j++, k+=3)
            {   Square[i][j] = ((Buffer[k]-'0')*10)+(Buffer[k+1]-'0');

                if(Square[i][j] != 0)
                    Num_Possibili[Square[i][j]-1] = false;
            }
        }

        StartFile.close();
        return true;
    }
    else
        return false;
}

void MagicSquare::Set_NumPossibili()
{   for(int i=0; i < Possibili_N; i++)
        Num_Possibili[i] = true;
}

void MagicSquare::Stamp_MagicSquare()
{   for(int i=0; i<N; i++)
    {   for(int j=0; j<N; j++)
            if(Square[i][j] == 0)
                cout << '-' << "\t";
            else
                cout << Square[i][j] << "\t";
        cout << endl;
    }
    cout << endl;
}

bool MagicSquare::Calc_MagicSquare()
{   int Row, Col;

    if(SearchEmpty(Row, Col))
    {   for(int i=0; i < Possibili_N; i++)
        {   if(Num_Possibili[i])
            {   Square[Row][Col] = i+1;
                Num_Possibili[i] = false;

                Calc_MagicSquare();

                // Backtracking
                Square[Row][Col] = 0;
                Num_Possibili[i] = true;
                Increase_BackTrackingCicle();
            }
        }
    }
    else
    {   if(CheckSum())
        {   Stamp_MagicSquare();
            Increase_NSquare();
        }
    }

    return false;
}

bool MagicSquare::SearchEmpty(int &Row, int &Col)
{   for(Row=0; Row<N; Row++)
        for(Col=0; Col<N; Col++)
            if(Square[Row][Col] == 0)
                return true;
    return false;
}

bool MagicSquare::CheckSum()
{   if(CheckDiags() && CheckRows() && CheckCols())
        return true;
    return false;
}

bool MagicSquare::CheckRows()
{   bool Check = true;

    for(int i=0, j, Sum; i<N && Check; i++)
    {   j=0; Sum=0;

        while(j<N)
        {   Sum += Square[i][j];
            if(Square[i][j] == 0)
                return false;
            j++;
        }
        if(Sum == Magic_Constant)
            Check = true;
        else
            Check = false;
    }

    return Check;
}

bool MagicSquare::CheckCols()
{   bool Check = true;

    for(int i=0, j, Sum; i<N && Check; i++)
    {   j=0; Sum=0;

        while(j<N)
        {   Sum += Square[j][i];
            if(Square[j][i] == 0)
                return false;
            j++;
        }

        if(Sum == Magic_Constant)
            Check = true;
        else
            Check = false;
    }

    return Check;
}

bool MagicSquare::CheckDiags()
{   bool Check = false;
    int Sum = 0;

    for(int i=0, j=0; i<N; i++, j++)
    {   Sum += Square[i][j];

        if(Square[i][j] == 0)
            return false;
    }

    if(Sum == Magic_Constant)
    {   Sum = 0;
        for(int i=N-1, j=0; i>=0; i--, j++)
        {   Sum += Square[i][j];

            if(Square[i][j] == 0)
                return false;

            if(Sum == Magic_Constant)
                Check = true;
            else
                Check = false;
        }
    }

    return Check;
}

int main()
{   MagicSquare Puzzle;
    string FilePath = "PartialSquare.txt";


    if(Puzzle.Set_MagicSquare(FilePath))
    {   Puzzle.Stamp_MagicSquare();

        cout << "La Costante Magica di un quadrato " << N << "x" << N;
        cout << " e': " << Magic_Constant << endl;

        Puzzle.Calc_MagicSquare();

        cout << "Numero di Quadrati Magici trovati: " << Puzzle.Get_NSquare() << endl;
        cout << "Numero di Cicli di Backtracking: " << Puzzle.Get_BackTrackingCicle() << endl;
    }
    else
        cout << "Errore nell'apertura del file." << endl;

    return 0;
}

我还必须计算回溯循环数，但是，使用这段代码，我有 986406 个循环，它比我预期的要高。我该如何改进这个程序？

编辑：部分填充的 5x5 是

00-00-00-20-03
04-00-25-00-00
00-00-00-00-09
00-00-01-00-00
00-06-00-02-00

提前致谢。

Answer 1

在Calc_MagicSquare()中，您可以在row/column/diag无效时立即停止探索：

if (Num_Possibili[i]) {
    Square[Row][Col] = i + 1;
    Num_Possibili[i] = false;

    if (CheckInvalidSum()) {
        // Backtracking
        Increase_BackTrackingCicle();
    } else {
        // Continue exploration
        Calc_MagicSquare();
    }
    // restore State.
    Square[Row][Col] = 0;
    Num_Possibili[i] = true;
}

with CheckInvalidSum() which return true which row/column/diag is full (not 0) and sum is different than Magic_Constant.

int RowSum(int row) const
{
    int sum = 0;

    for (int col = 0; col != N; ++col) {
        sum += Square[row][col];
    }
    return sum;
}

bool IsRowFull(row) const
{
    for (int col = 0; col != N; ++col) {
        if (Square[row][col] == 0) {
            return false;
        }
    }
    return true;
}

bool CheckInvalidSum() const
{
    for (int row == 0; row != N; ++row) {
         if (IsRowFull(row) && RowSum(row) != Magic_Constant) {
              return true; 
         }
    }
    // Similar stuff for column and diag
    return false;
}

优化说明：在修改Square[Row][Col]之前，网格应该是正确的，你可以只测试行Row和列Col（和对角线）而不是完整的网格。所以代码变成：

bool CheckInvalidSum(int row, int col) const
{
    if (IsRowFull(row) && RowSum(row) != Magic_Constant) {
         return true; 
    }
    // Similar stuff for column and diag
    return false;
}

Answer 2

这是新代码：

bool MagicSquare::Calc_MagicSquare()
{   int Row, Col;

    if(SearchEmpty(Row, Col))
    {   for(int i=0; i < Possibili_N; i++)
        {   if(Num_Possibili[i])
            {   Square[Row][Col] = i+1;
                Num_Possibili[i] = false;

                if(!CheckInvalidSum())
                    Calc_MagicSquare();

                // BackTracking
                Square[Row][Col] = 0;
                Num_Possibili[i] = true;
                Increase_BackTrackingCicle();
            }
        }
    }
    else
        if(CheckSum())
        {   Stamp_MagicSquare();
            Increase_NSquare();
        }

    return false;
}

这是另一种方法：

bool MagicSquare::CheckInvalidSum()
{   int Sum=0;

    //Check Row
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
        {   if(Square[i][j] == 0)
                return true;
            Sum += Square[i][j];
        }

    if(Sum != Magic_Constant)
        return true;

    // Check Col
    Sum = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
        {   if(Square[j][i] == 0)
                return true;
            Sum += Square[j][i];
        }

        if(Sum != Magic_Constant)
            return true;

        return false;
    }

对吗？

魔方和回溯 C++

Magic Square and Backtracking C++

c++

backtracking

magic-square