Magic square and backtracking

Question

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

• Toby Speight: It's not clear how your code "works" with the 5✕5 and 6✕6 inputs you posted, given const int N = 3;.

Answer 1

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.