Почему мой алгоритм Magic Square находит только половину возможных решений?

Question

Magic Square - это 2-й массив, который должен быть заполнен цифрами от 1 to n^2 таким образом, чтобы сумма всех строк, столбцов и диагонали составляла (n*(n^2 + 1)/2). Так что в массиве 3x3 это 3*(3*3 + 1)/2) = 3*10/2 = 15, в массиве 4x4 это 4*17/2 = 34 и т. Д. 3x3 имеет 8 возможных решений, а 4x4 - чуть выше 7000, а 5x5 - миллиарды, если я правильно помню. Мое задание - найти все возможные решения за разумное время. 3x3 - это мгновенные 8 решений. Однако в 4x4 я получаю только 3456 из 7000+ решений в 17-20 секунд (6+, если я удалю печать на экран).

#include <iostream> 
#include <windows.h> 
#include <ctime> 

using namespace std; 

//n is the size of the square 
//k is n^2 
int n = 0, k = 0; 

//nr is the number of solutions 
unsigned int nr = 0; 

//The magic Square 
int y[20][20]; 

bool member[20]; 
bool dbug = false; 

//SUM of the ROW is (n*(n*n + 1)/2) 
bool rowAccept(int p) { 
    int sum = 0; 

    for (int i = 1; i <= n; i++) 
     sum += y[p][i]; 

    return (sum == (n*(k + 1)/2)); 
} 

//SUM of the COLUMN is (n*(n*n + 1)/2) 
bool colAccept(int i, int j) { 
    int sum = 0; 

    for (int p = 1; p <= n - 1; p++) 
     sum += y[p][i]; 

    sum += j; 

    return (sum == (n*(k + 1)/2)); 
} 

/* 
x x y y 
x x y y 
z z t t 
z z t t 

Each of these sub squares will have the SUM of (n*(n*n + 1)/2) if it's a valid square 
Also the middle sub square: 
x y 
z t 
*/ 
inline bool subAccept(int p, int i, int j) { 
    return (y[p - 1][i - 1] + y[p - 1][i] + y[p][i - 1] + j == 34); 
} 


/* 
These corners have to have the SUM of (n*(n*n + 1)/2) if it's a valid square 

x _ x _  _ x _ x 
_ _ _ _  _ _ _ _ 
x _ x _  _ x _ x 
_ _ _ _  _ _ _ _ 


_ _ _ _  _ _ _ _ 
x _ x _  _ x _ x 
_ _ _ _  _ _ _ _ 
x _ x _  _ x _ x 
*/ 
inline bool miniCorners(int p, int i, int j) { 
    return (y[p - 2][i - 2] + y[p - 2][i] + y[p][i - 2] + j == 34); 
} 


//Check if the SUM of the diagonal is (n*(n*n + 1)/2) 
bool diag(int j) { 
    int sum = 0; 

    for (int k = 1; k < n; k++) 
     sum += y[k][k]; 

    sum += j; 

    return (sum == 34); 
} 


//Check if the SUM of the other diagonal(sorry I don't know what it is called in english) is (n*(n*n + 1)/2) 
bool revDiag(int j) { 
    int sum = 0; 

    for (int k = 1; k < n; k++) 
     sum += y[k][n - k + 1]; 

    sum += j; 

    return (sum == 34); 
} 

//Print to screen 
void show() { 
    for (int i = 1; i <= n; i++) { 
     for (int j = 1; j <= n; j++) 
      if (y[i][j] > 9) 
       cout << " " << y[i][j]; 
      else 
       cout << " " << y[i][j]; 
     cout << endl; 
    } 
    cout << endl; 

    if (dbug) { 
     cin.get(); 
    } 
} 

//Call all the above functions to see if it's a Magic Square 
inline bool magic(int p, int i, int j) { 
    //3x3 Magic Sqaure 
    //These are only patterns, only the colAccept(i, j) is called 
    //This works fine 
    if (n == 3) { 
     if (p == 2 && i == 1 && j != 1 && j != 9 && y[1][2] != 1 && y[1][2] != 9) 
      return false; 

     if (p == 2 && i == 3 && j != 1 && j != 9 && y[1][2] != 1 && y[1][2] != 9 && (y[2][1] != 1 || y[2][1] != 9)) 
      return false; 

     if (p == 3 && i == 2 && j != 1 && j != 9 && y[1][2] && y[1][2] && y[2][1] != 1 && y[2][1] != 9 && y[2][3] != 1 && y[2][3] != 9) 
      return false; 

     if (p == 2 && i == 2 && j != 5) 
      return false; 

     if (p == 3 && !colAccept(i, j)) 
      return false; 

     return true; 
    } 
    //4x4 Magic Sqaure 
    //All the functions are needed and some more patterns checking 
    //3456 solutions in 17-20 seconds instead of 7000+ (around 7008 or 7080, can't remember and can't find it anywhere) 
    else if (n == 4) 
    { 
     //    SubAccept#1 
    //------------------------------------------ 
    if (p == 2 && i == 2 && !subAccept(p, i, j)) 
     return false; 

    if (p == 2 && i == 4 && !subAccept(p, i, j)) 
     return false; 

    if (p == 3 && i == 3 && !subAccept(p, i, j)) 
     return false; 
    //------------------------------------------ 


    /* 
    _ _ _ _ 
    x _ _ x 
    x _ _ x 
    _ _ _ _ 

    SUM(x) = (n*(n*n + 1)/2) 
    */ 
    if (p == 3 && i == 4) 
     return ((y[2][1] + y[2][4] + y[3][1] + j) == 34); 


    //    MiniCorners 
    //-------------------------------------------- 
    if (p == 3 && i == 3 && !miniCorners(p, i, j)) 
     return false; 

    if (p == 3 && i == 4 && !miniCorners(p, i, j)) 
     return false; 

    if (p == 4 && i == 3 && !miniCorners(p, i, j)) 
     return false; 

    if (p == 4 && i == 4 && !miniCorners(p, i, j)) 
     return false; 
    //-------------------------------------------- 


    /* 
    x _ _ _ 
    _ _ _ y 
    _ _ _ y 
    x _ _ _ 

    x + x = y + y 
    */ 
    if (p == 4 && i == 1) 
     return ((j + y[1][1]) == (y[2][4] + y[3][4])); 

    /* 
    _ _ _ x 
    _ y _ _ 
    _ _ y _ 
    x _ _ _ 

    x + x = y + y 
    */ 
    if (p == 4 && i == 1) 
     return ((y[1][4] + j) == (y[2][2] + y[3][3])); 

    /* 
    x _ _ x 
    _ _ _ _ 
    _ _ _ _ 
    _ y y _ 

    x + x = y + y 
    */ 
    if (p == 4 && i == 3) 
     return ((j + y[4][2]) == (y[1][4] + y[1][1])); 

    /* 
    _ x x _ 
    _ _ _ _ 
    _ _ _ _ 
    _ x x _ 

    SUM(x) = (n*(n*n + 1)/2) 
    */ 
    if (p == 4 && i == 3) 
     return ((y[1][2] + y[1][3] + y[4][2] + j) == 34); 


    //other diagonal 
    if (p == 4 && i == 1 && !revDiag(j)) 
     return false; 

    //If in last ROW check for COLUMN SUM = (n*(n*n + 1)/2) 
    if (p == 4 && !colAccept(i, j)) 
     return false; 

    //diagonal 
    if (p == 4 && i == 4 && !diag(j)) 
     return false; 



    //    SubAccept#2 
    //------------------------------------------ 
    if (p == 4 && i == 2 && !subAccept(p, i, j)) 
     return false; 

    if (p == 4 && i == 4 && !subAccept(p, i, j)) 
     return false; 
    //------------------------------------------ 

    return true; 
    } 
    else 
    { 
     cout << "You only have time for 3x3 and 4x4.\n"; 
     exit(0); 
    } 
} 

//Basically permutations with backtracking 
void perm(int i, int p) { 
    for (int j = 1; j <= k; j++) { 
     //If the number is not already in the square AND if the criteria for magic square is met 
     if (!member[j] && magic(p, i, j)) { 
      y[p][i] = j;   //Add to the magic square 
      member[j] = true;  //It is now a member 
      if (i < n) {    
       perm(i + 1, p);  //If FIRST ROW isn't full go again 
      } 
      else if (rowAccept(p)) {//If the SUM of the row is (n*(n*n + 1)/2) {3x3: 15; 4x4: 34} continue 
       if (p == n) {  //If we are in the last ROW 
        show();    //Show the solution 
        p = 1;     //back to 1st ROW 
        nr++;   //Count the solutions 
       } 
       else { 
        perm(1, p + 1); //If it isn't the last ROW go to the next one 
       } 
      } 

      member[j] = false;  //Number is no longer a member 
     }        //I'm not sure this is in the right place but I no longer know where to move it 
    } 
} 

int main() { 
    //Make sure there are no members 
    for (int j = 1; j <= k; j++) 
     member[j] = false; 

    //3x3 or 4x4; else exit(0) 
    cout << "Magic Square size 3x3 or 4x4 ?\n"; 
    cin >> n; 
    k = n*n; 

    //Stop at every solution ? 
    cout << "Debug ?(0/1)\n"; 
    cin >> dbug; 

    //Start timing and GO 
    int start_s = clock(); 
    perm(1, 1); 
    int stop_s = clock(); 

    cout << "Result: " << nr << endl; 
    cout << "Time: " << (stop_s - start_s)/double(CLOCKS_PER_SEC) << " seconds\n"; 
} 

Я знаю, что это долго и мой спагетти не так легко следовать, но я попытался прокомментировать, как лучше всего, как я мог. Также я прошу прощения за публикацию всего этого, но я не знаю, какая часть испортила количество решений.

Answer 1

РЕШЕННЫЙ!
Есть два типа магических квадратов, как выясняется.
С одной стороны, они ограничены числами n^2 (мой случай), с другой стороны, они могут содержать любые числа, если rowSUM, colSUM и diagSUM равны.
Условия в моей магической (...) функции относительно subAccept(), miniCorners() и других условий нарушения не применяются в моем случае. Я их вынул, но теперь код медленнее, но результат правильный.