Магический квадрат и переполнение стека

Я должен написать программу, которая решает Волшебный квадрат NxN, с цифрами от 1 до N ^ 2.
Он работает правильно с 3×3, частично заполненным 4×4, но через два часа он не может найти решение для частично заполненного 5×5.

Это мой код:

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

void Set_NumPossibili();
bool SearchEmpty(int &Row, 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();
int 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;

Calc_MagicSquare();

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

return false;
}

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

Я также должен рассчитать количество циклов обратного отслеживания, но с этим кодом у меня 986406 циклов, и это больше, чем я ожидал.
Как я могу улучшить эту программу?

РЕДАКТИРОВАТЬ: частично заполненный 5×5

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

Заранее спасибо.

-2

Решение

В Calc_MagicSquare(), вы можете прекратить исследование, как только строка / столбец / диаграмма недействительны:

if (Num_Possibili[i]) {
Square[Row][Col] = i + 1;
Num_Possibili[i] = false;

if (CheckInvalidSum()) {
// Backtracking
Increase_BackTrackingCicle();
} else {
// Continue exploration
Calc_MagicSquare();
}
// restore State.
Square[Row][Col] = 0;
Num_Possibili[i] = true;
}

с CheckInvalidSum() которые возвращаются true когда строка / столбец / диаграмма заполнены (не 0) и сумма отличается от Magic_Constant,

int RowSum(int row) const
{
int sum = 0;

for (int col = 0; col != N; ++col) {
sum += Square[row][col];
}
return sum;
}

bool IsRowFull(row) const
{
for (int col = 0; col != N; ++col) {
if (Square[row][col] == 0) {
return false;
}
}
return true;
}

bool CheckInvalidSum() const
{
for (int row == 0; row != N; ++row) {
if (IsRowFull(row) && RowSum(row) != Magic_Constant) {
return true;
}
}
// Similar stuff for column and diag
return false;
}

Примечание по оптимизации: как и раньше Square[Row][Col] изменено, сетка должна быть правильной, вы можете просто проверить строку Row и колонка Col (и диагональ) вместо полной сетки. Так что код становится:

bool CheckInvalidSum(int row, int col) const
{
if (IsRowFull(row) && RowSum(row) != Magic_Constant) {
return true;
}
// Similar stuff for column and diag
return false;
}
0

Другие решения

Это новый код:

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())
Calc_MagicSquare();

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

return false;
}

И это другой метод:

bool MagicSquare::CheckInvalidSum()
{   int Sum=0;

//Check Row
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
{   if(Square[i][j] == 0)
return true;
Sum += Square[i][j];
}

if(Sum != Magic_Constant)
return true;

// Check Col
Sum = 0;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
{   if(Square[j][i] == 0)
return true;
Sum += Square[j][i];
}

if(Sum != Magic_Constant)
return true;

return false;
}

Это правильно?

0

По вопросам рекламы [email protected]