C language isMagicsquare function: What logic error is in my function code?

Question

Although the output with the my current examples is correct, my code seems to have a logic error that doesn't give the right output for other cases.

I have previously addressed this issue:

"What would happen in your code if there are no repeated numbers, all numbers are used, your last column sum is correct, but your second-last column sum is incorrect?"

Any help would be very much appreciated.

My current code:

/* Magic Square */
#include <stdio.h>

#define MAX_N 100
#define TRUE  1
#define FALSE 0

int isMagicSquare(int square[MAX_N][MAX_N], int n);

int main(void) {
    int square1[MAX_N][MAX_N] = {
            {4, 9, 2},
            {3, 5, 7},
            {8, 1, 6}};

    // should print TRUE
    int check1 = isMagicSquare(square1, 3);
    if (check1 == TRUE) {
        printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }

    int square2[MAX_N][MAX_N] = {
            {20,  6,  7, 17},
            { 9, 15, 14, 12},
            {13, 11, 10, 16},
            { 8, 18, 19, 5} };

            /*{ 1 , 2 , 3 , 4 , },
            { 5 , 6 , 7 , 8 , },
            { 9 , 10, 11, 12, },
            { 13, 14, 15, 16,} };*/

            /*{16, 2, 3, 13,}, 
            {5, 11, 10, 8 ,},
            {9,  7, 6, 12 ,},
            {4, 14, 15, 1, } };*/ 

    // should print FALSE
    int check2 = isMagicSquare(square2, 4);
    if (check2 == TRUE) {
        printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }

    int square3[MAX_N][MAX_N] = {
            {17, 24,  1, 15,  8},
            {23,  5,  7, 16, 14},
            { 4,  6, 13, 22, 20},
            {10, 12, 19,  3, 21}, 
            {11, 18, 25,  9,  2}};

    // should print FALSE
    int check3 = isMagicSquare(square3, 5);
    if (check3 == TRUE) {
        printf("TRUE\n");
    } else {
        printf("FALSE\n");
    }

    return 0;
}

int isMagicSquare(int square[MAX_N][MAX_N], int n) {
    int row, col;
    int drow, dcol;
    int sum, sum1, sum2, sum3;
    int boolean = 0;

    //For Diagonals
    sum = 0;
    for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            if (row == col)
                sum += square[row][col];
        }
    }

    for (row = 0; row < n; row++) {
        sum3 = 0;
        for (col = 0; col < n; col++) {
            sum3 += square[n-row-1][col]; 
        }
        if (sum == sum3)
            boolean = 1;
        else {
            return FALSE;
        }
    }

    //For Rows
    for (row = 0; row < n; row++) {
        sum1 = 0;
        for (col = 0; col < n; col++) {
            sum1 = sum1 + square[row][col];
        }
        if (sum == sum1)
            boolean = 1;
        else {
            return FALSE;
        }
    }

    //For Columns
    for (row = 0; row < n; row++) {
        sum2 = 0;
        for (col = 0; col < n; col++) {
            sum2 = sum2 + square[col][row];
        }
        if (sum == sum2)
            boolean = 1;
        else {
            return FALSE;
        }
    }

    if (boolean == 1) {
        //Check if All Numbers is used

        for (row = 0; row < n; row++) {
            for (col = 0; col < n; col++) {
                if(square[row][col] > n*n || square[row][col] < 0) {
                    boolean = 0;
                    break;
                }
            }
        }

        //Check for Repeating Numbers
        for (row = 0; row < n; row++) {
            for(col = 0; col < n; col++) {

                for(drow = row + 1; drow < n; drow++){
                    for(dcol = col + 1; dcol < n; dcol++) {
                        if(square[row][col] == square[drow][dcol]) {
                            boolean = 0;
                            break;
                        }
                    }   
                }
            }
        }
        // if Statement End
    }
    else {
        boolean = 0;
    }

    if (boolean == 1)
        return TRUE;
    else
        return FALSE;
}

... it works, but there's a bug? We may be using the word differently. How are you identifying the bug? — Dave Newton, Mar 02 '19 at 22:32
Your diagonal checking is probably wrong. It seems to be looping over all possible diagonals, rather than just the two principal diagonals. You should add printing code to your `isMagicSquare` function so as to identify what it is checking and why it came to the decision it did. — Jonathan Leffler, Mar 02 '19 at 22:35
`//Check if All Numbers is used` code is highly inefficient `O(n*n*n*n)` A reasonable concern with `MAX_N 100`. An alternative could sort the values and then check therm `O(n* log n)` — chux - Reinstate Monica, Mar 02 '19 at 22:44
@JonathanLeffler I think I see the problem with my counter diagonal code. Thanks. For my problem, it asked me to have an output of TRUE or FALSE only on a new line for every magic square checked, so I didn't include any printfs'. — Vinxent, Mar 02 '19 at 22:48
@Vinxent: what you submit may be different from what you write while you're developing and debugging the code. You could consider [`#define` macro for debug printing in C](https://stackoverflow.com/questions/1644868/define-macro-for-debug-printing-in-c) but that's probably overkill. While you're debugging, add printing statements. When you submit the code, comment them out, or delete them; they've served their purpose. Or keep them if you're using debugging macros — just disable the debugging. — Jonathan Leffler, Mar 02 '19 at 22:53
@chux I'm not quite sure what you meant by `O(n*n*n*n)` and `O(n* log n)` — Vinxent, Mar 02 '19 at 22:59

Benjam · Accepted Answer · 2019-03-02T23:12:15.363

it seems the sum3 var is reinitialized to 0 inside the computation loop, plus the diagonal sum equality check should be outside of the loop.

I would rework it this way:

//For Diagonals
sum = 0;
sum3 = 0;
for (row = 0; row < n; row++) {
    sum  += square[row][row];
    sum3 += square[row][n - 1 - row];
}
if (sum == sum3)
    boolean = 1;
else {
    return FALSE;
}

BTW I simplified a bit the diagonal calculation since it is linear, there is no need for 2 nested loops.

I found some other bugs in the final checks:

-0 should not be a valid value

-return instead of just breaking (break only exists the inner loop, the outer loop continues)

for (row = 0; row < n; row++) {
    for (col = 0; col < n; col++) {
        if(square[row][col] > n*n || square[row][col] <= 0) {
            return FALSE;
        }
    }
}

//Check for Repeating Numbers
int storedNumbers[n * n];
for (row = 0; row < n; row++) {
    for(col = 0; col < n; col++) {
        storedNumbers[row + n * col] = square[row][col];
    }
}

Then scan storedNumbers for duplicates. Searching for duplicate values in an array

cheers

The code worked (for the other cases)! So the diagonals were the problem. Thank you very much! — Vinxent, Mar 02 '19 at 22:56

Jonathan Leffler · Answer 2 · 2019-03-02T23:34:01.703

You can use a more compact scheme to check that all numbers 1 .. (n*n) are used with no duplicates using code such as:

int counts[n * n];  // Can't use an initializer with a VLA
memset(counts, '\0', sizeof(counts));

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (square[i][j] <= 0 || square[i][j] > n * n)
            return FALSE;
        counts[square[i][j] - 1]++;  // Map 1..n*n to 0..n*n-1
        // if (++counts[square[i][j] - 1] > 1)
        //     return FALSE;
    }
}

for (int i = 0; i < n * n; i++)
{
    if (counts[i] != 1)
        return FALSE;
}

Since there are n*n elements to check, this code uses space and time that is linear with respect to the number of elements in the magic square, which is within a constant factor of optimal.

C language isMagicsquare function: What logic error is in my function code?

2 Answers2