# Magic square and backtracking

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

• It's not clear how your code "works" with the 5✕5 and 6✕6 inputs you posted, given const int N = 3;. Nov 12, 2022 at 21:33

# 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.

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]) {
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]) {
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.