Я должен написать программу, которая решает Волшебный квадрат 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
Заранее спасибо.
В 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;
}
Это новый код:
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;
}
Это правильно?