patterncppMinor

Magic square and backtracking

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

andmagicbacktrackingsquare

Problem

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

What do you think?

```
#include
#include
#include

const int N = 3;
const int Possibili_N = N*N;
const int Magic_Constant = (N((NN)+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=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

Solution

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

Prefer to use the C++ header `, 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{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  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 used_numbers;  // true if used; false if available
    std::vector 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 row_totals;
    std::vector 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::s

Code Snippets

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

#include <string.h>

using namespace std;

long BackTracking_Cicle = 0;
    int N_Square = 0;

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

Context

StackExchange Code Review Q#81965, answer score: 3

Revisions (0)

No revisions yet.