6
\$\begingroup\$

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

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\$
1
  • \$\begingroup\$ It's not clear how your code "works" with the 5✕5 and 6✕6 inputs you posted, given const int N = 3;. \$\endgroup\$ Nov 12, 2022 at 21:33

1 Answer 1

3
\$\begingroup\$

Avoid non-standard extensions

These array declarations are not valid C++:

    bool Num_Possibili[Possibili_N];  // true se non è stato preso, false se è stato preso
    int Square[N][N];

To make them valid, N and Possibili_N need to be compile-time constants, which can be achieved in current C++ using constexpr.

But I don't think we want to fix the square size at compilation time like that - instead, we should be able to construct a magic square of any (positive integer) size without recompilation. We could use std::vector instead of raw arrays for storage in that case.


Use namespaces effectively

#include <string.h>

Prefer to use the C++ header <cstring>, which declares its identifiers in the std namespace.

using namespace std;

Please don't do this, as it completely negates the benefit of namespaces. It can make your program harder to work with, and in the worst case, it cause the meaning of your code to silently change when you include another library or compile against a newer version of the C++ standard.


Use const where appropriate

Consider which of the member functions should modify the magic square. All other member functions should be declared const.


Constructor and destructor

The constructor and destructor can be declared = default - or better, omitted entirely. But we should be initialising BackTracking_Cicle (is that a typo for "Cycle"?) and N_Square, probably by default initialisers:

    long BackTracking_Cicle = 0;
    int N_Square = 0;

Don't flush output streams

There's a lot of unnecessary flushing of output, using std::endl, where plain newline ('\n') would be more appropriate.


Set_MagicSquare() would be more flexible as a >> operator, and Stamp_MagicSquare() as a << operator:

    friend std::istream& operator>>(std::istream&, MagicSquare&);
    friend std::ostream& operator<<(std::ostream&, const MagicSquare&);

Use a linear array for simplicity

If we represent the contents of the square as a linear array, rather than as an array of arrays, then many operations become easier. We could read in the same format we write (tab/newline separated) very simply:

std::istream& operator>>(std::istream& is, MagicSquare& p)
{
    p.Set_NumPossibili();
    p.Set_BackTrackingCicle();
    p.Set_NSquare();

    std::copy_n(std::istream_iterator<std::size_t>{is}, p.Square.size(), p.Square.begin());
    for (auto i: p.Square) {
        p.Num_Possibili[i] = false;
    }

    return is;
}

std::ostream& operator<<(std::ostream& os, const MagicSquare& p)
{
    std::size_t i = 0;
    for (auto e: p.Square) {
        os << e
           << (++i == p.n ? i = 0, '\n' : '\t');
    }
    return os << '\n';
}

And checking becomes easier, as we can use the same code for rows, columns and diagonals just by using appropriate stride values:

bool MagicSquare::check_line(std::size_t ix, std::size_t stride) const
{
    std::size_t sum = 0;
    for (std::size_t i = 0;  i < n;  ++i) {
        if (sum += Square[ix] > Magic_Constant()) { return false; }
        ix += stride;
    }
    return sum == Magic_Constant();
}

bool MagicSquare::CheckSum() const
{
    // Rows
    for (std::size_t i = 0;  i < n * n;  i += n) {
        if (!check_line(i, 1)) { return false; }
    }
    // Columns
    for (std::size_t i = 0;  i < n;  ++i) {
        if (!check_line(i, n)) { return false; }
    }
    // Diagonals
    return check_line(0, n+1) && !check_line(n-1, n-1);
}

// CheckRows, CheckCols and CheckDiags removed

Avoid re-computing line totals

There's a lot of recomputation of row and column totals. However, we can save most of this by keeping the values around in the class, and just updating them with the new values. To demonstrate, it's probably easiest if I start from scratch.

Start with the square size, available numbers and contents:

class MagicSquare
{
    // Use a signed type for value, so we can do subtractions and comparisons
    // with negative values.
    using value_type = std::int_fast32_t;

    std::size_t n;              // side length
    std::vector<bool> used_numbers;  // true if used; false if available
    std::vector<value_type> square;

Now, record how many elements we need to add in each horizontal, vertical and diagonal line, and the amount they must sum to:

    struct line_count {
        std::size_t empty_cells;
        value_type sum_remaining;

        // return true unless magic-square constraints are violated
        bool update(std::size_t count_diff, value_type value_diff)
        {
            empty_cells -= count_diff;
            sum_remaining -= value_diff;
            return empty_cells ? sum_remaining > 0 : !sum_remaining;
        }
    };

    std::vector<line_count> row_totals;
    std::vector<line_count> col_totals;
    line_count diagonals[2];

With this in place, we can construct a square, and set any of its elements, updating the counts appropriately:

    static constexpr value_type magic_total(value_type n) {
        return n * (n * n + 1) / 2;
    }

public:
    explicit MagicSquare(std::size_t n)
        : n{n},
          used_numbers(n * n + 1),
          square(n * n),
          row_totals(n, {n, magic_total(n)}),
          col_totals(n, {n, magic_total(n)}),
          diagonals{{n, magic_total(n)}, {n, magic_total(n)}}
    {
    }

Now we can use these to solve the square more quickly (still using the same algorithm):

    bool solve(std::size_t start = 0)
    {
        if (start == n * n) {
            // terminate recursion
            return true;
        }

        // for each empty square
        for (std::size_t i = start;  i < n * n;  ++i) {
            if (square[i]) {
                // already filled in
                continue;
            }

            // try each available number
            for (std::size_t j = 1;  j <= n * n;  ++j) {
                if (!used_numbers[j]) {
                    // try it
                    if (set_value(i, j) && solve(i + 1)) {
                        return true; // success!
                    }
                }
            }

            // undo, to allow our caller to backtrack
            set_value(i, 0);
            break;
        }

        // no solution found
        return false;
    }

    bool set_value(std::size_t i, value_type value)
    {
        const std::size_t row = i / n;
        const std::size_t col = i % n;

        auto& v = square[row * n + col];
        auto const count_diff = !!value - !!v;
        auto const value_diff = value - v;

        used_numbers[v] = false;
        used_numbers[value] = true;

        v = value;

        // N.B. don't use short-circuit && here, as we need side-effects
        // of update()
        bool is_valid = true;
        is_valid &= row_totals[row].update(count_diff, value_diff);
        is_valid &= col_totals[col].update(count_diff, value_diff);
        if (row == col) {
            is_valid &= diagonals[0].update(count_diff, value_diff);
        }
        if (row + col + 1 == n) {
            is_valid &= diagonals[1].update(count_diff, value_diff);
        }
        return is_valid;
    }

Full code

#include <iterator>
#include <ostream>
#include <vector>

class MagicSquare
{
    // Use a signed type for value, so we can do subtractions and comparisons
    // with negative values.
    using value_type = std::int_fast32_t;

    std::size_t n;              // side length
    std::vector<bool> used_numbers;  // true if used; false if available
    std::vector<value_type> square;

    struct line_count {
        std::size_t empty_cells;
        value_type sum_remaining;

        // return true unless magic-square constraints are violated
        bool update(std::size_t count_diff, value_type value_diff)
        {
            empty_cells -= count_diff;
            sum_remaining -= value_diff;
            return empty_cells ? sum_remaining > 0 : !sum_remaining;
        }
    };

    std::vector<line_count> row_totals;
    std::vector<line_count> col_totals;
    line_count diagonals[2];

    static constexpr value_type magic_total(value_type n) {
        return n * (n * n + 1) / 2;
    }

public:
    explicit MagicSquare(std::size_t n)
        : n{n},
          used_numbers(n * n + 1),
          square(n * n),
          row_totals(n, {n, magic_total(n)}),
          col_totals(n, {n, magic_total(n)}),
          diagonals{{n, magic_total(n)}, {n, magic_total(n)}}
    {
    }

    friend std::istream& operator>>(std::istream& is, MagicSquare& p)
    {
        std::size_t i = 0;
        for (std::istream_iterator<value_type> iter{is}, end{};  iter != end;  ++iter) {
            p.set_value(i++, *iter);
            if (i == p.square.size()) {
                break;
            }
        }
        return is;
    }

    friend std::ostream& operator<<(std::ostream& os, const MagicSquare& p)
    {
        std::size_t i = 0;
        for (auto e: p.square) {
            os << e
               << (++i == p.n ? i = 0, '\n' : '\t');
        }
        return os << '\n';
    }

    bool set_value(std::size_t i, value_type value)
    {
        const std::size_t row = i / n;
        const std::size_t col = i % n;

        auto& v = square[row * n + col];
        auto const count_diff = !!value - !!v;
        auto const value_diff = value - v;

        used_numbers[v] = false;
        used_numbers[value] = true;

        v = value;

        // N.B. don't use short-circuit && here, as we need side-effects
        // of update()
        bool is_valid = true;
        is_valid &= row_totals[row].update(count_diff, value_diff);
        is_valid &= col_totals[col].update(count_diff, value_diff);
        if (row == col) {
            is_valid &= diagonals[0].update(count_diff, value_diff);
        }
        if (row + col + 1 == n) {
            is_valid &= diagonals[1].update(count_diff, value_diff);
        }
        return is_valid;
    }

    bool solve(std::size_t start = 0)
    {
        if (start == n * n) {
            // terminate recursion
            return true;
        }

        // for each empty square
        for (std::size_t i = start;  i < n * n;  ++i) {
            if (square[i]) {
                // already filled in
                continue;
            }

            // try each available number
            for (std::size_t j = 1;  j <= n * n;  ++j) {
                if (!used_numbers[j]) {
                    // try it
                    if (set_value(i, j) && solve(i + 1)) {
                        return true; // success!
                    }
                }
            }

            // undo, to allow our caller to backtrack
            set_value(i, 0);
            break;
        }

        // no solution found
        return false;
    }
};

#include <cstdlib>
#include <iostream>
#include <sstream>
int main()
{
    MagicSquare puzzle{5};

    std::istringstream input{
        "00\t00\t00\t20\t03\n"
        "04\t00\t25\t00\t00\n"
        "00\t00\t13\t00\t09\n"
        "00\t00\t01\t00\t00\n"
        "00\t06\t00\t02\t00\n"
    };
    input >> puzzle;

    if (!input) {
        std::cerr << "Failed to load puzzle\n";
        return EXIT_FAILURE;
    }

    std::cout << puzzle;
    if (!puzzle.solve()) {
        std::cerr << "Failed to solve puzzle\n";
        return EXIT_FAILURE;
    }

    std::cout << puzzle;
}

Further suggestions

We may be able to change the algorithm to discount dead-ends more quickly, e.g. by inferring the missing value to use when a line has only one empty space in it. However, for this review I've kept to the algorithm presented, and leave those improvements as an exercise for the interested reader.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.