-2

I have to write a program that solves a NxN Magic Square, with digits from 1 to N^2. It works properly with 3x3, partially filled 4x4, but, in two hours, it can't find a solution for partially filled 5x5.

This is my code:

#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;
}

I have to also calculate the number of Backtracking Cycles, but, with this code, I have 986406 cycles, and it's higher than I expected. How can I improve this program?

EDIT: The partial filled 5x5 is

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

Thank you in advance.

4

2 回答 2

0

这是新代码：

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;
    }

这样对吗？

于 2015-02-19T20:49:38.813 回答
0

在Calc_MagicSquare()中，您可以在行/列/诊断无效时立即停止探索：

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;
}

CheckInvalidSum()当行/列/诊断true已满（不是0）并且总和不同于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;
}
于 2015-02-19T18:53:20.020 回答