4
\$\begingroup\$

I have to write a program that solves a NxN Magic Square, with digits from 1 to N2.

What do you think?

#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];
    long BackTracking_Cicle;
    int N_Square;

    void Set_NumPossibili();
    bool SearchEmpty(int &Row, int &Col);
    bool CheckInvalidSum(int Row, int Col);
    bool IsRowFull(int Row);
    bool IsColFull(int Col);
    int  RowSum(int Row);
    int  ColSum(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();
    long 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;

                if(CheckInvalidSum(Row, Col)) 
                    // BackTracking
                    Increase_BackTrackingCicle();
                else
                    Calc_MagicSquare();

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

    return false;
}

bool MagicSquare::CheckInvalidSum(int Row, int Col)
{   if (IsRowFull(Row) && RowSum(Row) != Magic_Constant)
        return true;
    if (IsColFull(Col) && ColSum(Col) != Magic_Constant)
        return true;

    return false;
}

bool MagicSquare::IsRowFull(int Row)
{   for(int i=0; i<N; i++)
        if(Square[Row][i] == 0)
            return false;
    return true;
}

bool MagicSquare::IsColFull(int Col)
{   for(int i=0; i<N; i++)
        if(Square[i][Col] == 0)
            return false;
    return true;
}

int MagicSquare::RowSum(int Row)
{   int Sum=0;

    for(int i=0; i<N; i++)
        Sum += Square[Row][i];

    return Sum;
}

int MagicSquare::ColSum(int Col)
{   int Sum=0;

    for(int i=0; i<N; i++)
        Sum += Square[i][Col];

    return Sum;
}

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

It works with these partial magic squares:

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

06-00-03-00-00-01
00-11-27-00-08-00
19-00-00-15-00-24
00-20-00-21-00-00
25-00-10-00-26-12
00-05-00-04-02-00
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.