Magic Square combinations lister (logic error)

[jadmacro]

Hi,

I have been working on a C++ program that will list all possible combinations (should be 3456 combinations) of a 4 by 4 Magic Square. In case you don't know how they work:

-16 numbers (all of different values 1-16)
-All columns and rows must sum 34
-All diagonals and 4 quadrants must also sum 34 (I didn't add this yet because I was just trying it with columns and rows first but it didn't work)

Example:

1 4 14 15
13 16 2 3
8 5 11 10
12 9 7 6



So here's the code:

#include <iostream>

using namespace std;

int answersArray[3456][4][4], currentAnswer=0;

//Prototypes
void fillArray(int square[][4]);
void printIt(int num);

int main()
{
    int square[4][4];
    while (currentAnswer < 3456)
    {
        fillArray(square);
        printIt(currentAnswer - 1);
    }
    cout << "\nPress enter key to continue...";
    cin.get();
    return 0;
}

void printIt(int num)
{
    for(int i=0; i < 4; i++)
    {
        for(int j=0; j < 4; j++)
            cout << answersArray[num][j][i] << " ";
        cout << "\n";
    }
    cout << "\n";
}

bool inSquare(int val, int square[][4]) //returns true if val is already in square
{
    int count;
    count = 0;
    for(int x=0; x < 4; x++)
        for(int y=0; y < 4; y++)
        {
            if(square[x][y] == val) count++;
            if(count > 1) return true;
        }
    return false;
}

bool checkNumbers(int square[][4])
{
    bool getOut;
    for(int i=1; i < 16; i++)
    {
        getOut = true;
        for(int x=0; x < 4; x++)
        {
            for(int y=0; y < 4; y++)
                if(square[x][y] == i)
                {
                    getOut = false;
                    break;
				}
            if(getOut == false) break;
        }
        if(getOut == true) return false;
    }
    return true;
}

bool inAnswersArray(int square[][4])
{
    int x, y;
    if(currentAnswer == 0) return false;
    for(int i=0; i < currentAnswer; i++)
    {
        x = 0;
        y = 0;
        while(square[x][y] == answersArray[i][x][y])
        {
            x++;
            if(x == 3)
            {
	 	        x = 0;
	 	        y++;
            }
            if(y == 4) return true; //if y == 4 and still in loop then
        }                            //it's already in answers array
    }
    return false;
}
        
bool goodSquare(int square[][4])
{
    int total;
    if(!checkNumbers(square)) return false;
    if(inAnswersArray(square)) return false;
    
    //Check 34's
    /* rows */
    for(int x=0; x < 4; x++)
    {
        total = 0;
        for(int y=0; y < 4; y++)
            total += square[x][y];
        if(total != 34) return false;
    }
    /* columns */
    for(int x=0; x < 4; x++)
    {
        total = 0;
        for(int y=0; y < 4; y++)
            total += square[x][y];
        if(total != 34) return false;
    }
    /* quadrants */
    total = square[0][0] + square[0][1] + square[1][0] + square[1][1];
    if(total != 34) return false;
    total = square[2][0] + square[3][0] + square[2][1] + square[3][1];
    if(total != 34) return false;
    total = square[0][2] + square[1][2] + square[0][3] + square[1][3];
    if(total != 34) return false;
    total = square[2][2] + square[2][3] + square[3][2] + square[3][3];
    if(total != 34) return false;
    /* diagonals */
    total = square[0][0] + square[1][1] + square[2][2] + square[3][3];
    if(total != 34) return false;
    total = square[3][0] + square[2][1] + square[1][2] + square[0][3];
    if(total != 34) return false;
    //End check 34's
    
    //Save to answers Array
    for(int i=0; i < 4; i++)
        for(int j=0; j < 4; j++)
            answersArray[currentAnswer][j][i] = square[j][i];
    currentAnswer++;
    return true;
}

bool miniCheck(int &fill, int square[][4], int y, bool row)
{
    if(row == true) 
	    fill = 34 - square[0][y] - square[1][y] - square[2][y];
    else
        fill = 34 - square[y][0] - square[y][1] - square[y][2];
    if(fill < 1 || fill > 16) return false;
    return true;
}
    

void fillArray(int square[][4])
{
    for(square[0][0]=1; square[0][0] < 17; square[0][0]++)
    {
        for(square[1][0]=1; square[1][0] < 17; square[1][0]++)
        {
            if(inSquare(square[1][0], square)) continue;
            for(square[2][0]=1; square[2][0] < 17; square[2][0]++)
            {
                if(inSquare(square[2][0], square)) continue;
                if(!miniCheck(square[3][0], square, 0, true)) continue;
                for(square[0][1]=1; square[0][1] < 17; square[0][1]++)
                {
                    if(inSquare(square[0][1], square)) continue;
                    for(square[1][1]=1; square[1][1] < 17; square[1][1]++)
                    {
                        if(inSquare(square[1][1], square)) continue;
                        for(square[2][1]=1; square[2][1] < 17; square[2][1]++)
                        {
                            if(inSquare(square[2][1], square)) continue;
                            if(!miniCheck(square[3][1], square, 1, true)) continue;
                            for(square[0][2]=1; square[0][2] < 17; square[0][2]++)
                            {
                                if(inSquare(square[0][2], square)) continue;
                                for(square[1][2]=1; square[1][2] < 17; square[1][2]++)
                                {
                                    if(inSquare(square[1][2], square)) continue;
                                    for(square[2][2]=1; square[2][2] < 17; square[2][2]++)
                                    {
		 					            if(inSquare(square[2][2], square)) continue;
		 					            if(!miniCheck(square[3][2], square, 2, true)) continue;
		 					            if(!miniCheck(square[0][3], square, 0, false)) continue;
		 					            if(!miniCheck(square[1][3], square, 1, false)) continue;
		 					            if(!miniCheck(square[2][3], square, 2, false)) continue;
		 					            if(!miniCheck(square[3][3], square, 3, false)) continue;
                                        if(goodSquare(square))
                                            return;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

When I run it though it pretty much just lags and does nothing. Why isn't it finding any combinations and printing them out?

Any help would be great. Thanks!

[jsmith]

look at line 132.

also, why do you have two loops for smSquare[2] on 111 and 114?

[tition]

as far as I know, the number of 4x4 sudokus is 216, as I counted them with the program I posted as a reply to your earlier post,

http://www.cplusplus.com/forum/general/7856/

Where did you get the 3456 number from? I am pretty sure it is wrong (I doubt I made a programming mistake, since all the sudokus looked ok).

[tition]

A few algorithmic suggestions.

First, your check whether the entries of your sudoku are different is wrong! You should use

if(! inSquare(smSquare[1], smSquare, 1))continue;

instead!


Second, where do you check the diagonals and the four quadrants? Third, you don't need to check the first three rows and columns since they sum up correctly due to the way you defined them:
bgSquare[3][0] = 34 - smSquare[0] - smSquare[1] - smSquare[2];
Fourth, where do you check whether the entries are greater than zero?

You have 16 positions, and total 14 relations between them (4 relations from columns, 4 relations from rows, 4 from quadrants and 2 from diagonals). Now those relations should be close to "linearly independent", that means, not many of them can be derived from the others.

That said, you dont need 9 parameters to fill in your sudoku! To find out exaclty how many parameters you need, you should make a Gaussian elimination on a 14x16 matrix, which can be done for example by Excel or some other program (but it will take you some time to do).

If you don't know all words used in the preceding paragraph, don't worry, you don't need all that jazz (although it will make your program run instantaneously). You can do some immediate optimizations however, based on the same "linear algebra" idea.

Here is what can be done with bgSquare[1][1]

    bgSquare[0][0] = smSquare[0];
    bgSquare[1][0] = smSquare[1];
    bgSquare[2][0] = smSquare[2];
    bgSquare[3][0] = 34- bgSquare[2][0] -bgSquare[1][0] - bgSquare[0][0]; 
    bgSquare[0][1] = smSquare[4];
    bgSquare[1][1] = 34- bgSquare[0][0] -bgSquare[1][0] - bgSquare[0][1]; 
 //you dont need smSquare[5]
 

You can do lots of such optimizations throughout your code...

[jadmacro]

tition, I know that stuff could be sped up with optimizations, and I know I didn't check for diagonals and quadrants yet, but right now the program is just printing out 0's and I need to figure that problem out firs. Any idea why? It should be printing something out where all columns and rows sum 34 at least. I edited the fixed code in the original post. Could you take a look at it and tell me why it's just printing out 0's?

Thanks a lot.

[rossman231]

here's line 114:
if(! inSquare(smSquare[3], smSquare, 3)) continue;
you've gotten a little ahead of yourself. smSquare[3] theoretically doesn't exist yet, you wanted those 3's to be 2's. And you continued this pattern all the way down. Double-check your inSquare lines.

[tition]

Substitute (lines 14-18)

    for(int i=0; i < 3456; i++)
    {
        fillArray(smSquare);
        printIt(i);
    }

with

currentAnswer=0;
smSquare[0]=0;
   while (currentAnswer<3456)
    {
        fillArray(smSquare);
        printIt(i);
    }

Fix the for cycle in bool inSquare (line 37) to

for(int i=0; i <= currentSpot; i++)

Also, you need to check that your bgSquare[*][*] entries are positive! Otherwise you will get negative numbers in your sudoku.

[jadmacro]

tition, I finally got it working, but it's taking roughly a second and a half per combination. Do you have any ideas on how I could speed this up a bit? I edited the code with the working version. If you can think of any optimizations that I can do to speed it up it would really help me out.

Thanks again for all the help!