What You Will Learn

Prerequisites

Finish the previous two lectures first so the magic square program feels natural. You need the duplicate check from lecture 51 and the diagonal index rules from lecture 52, because the checker below reuses both ideas.

What Makes a Matrix Magic?

For this exercise, a square matrix is magic when two conditions hold together:

1. All elements are distinct, so no value appears twice.
2. The sum of every row, every column, the principal diagonal and the secondary diagonal is the same number. That number is called the magic constant.

The distinctness rule matters. A matrix filled with 5s has equal sums everywhere, yet nobody calls it magic. (A “normal” magic square also demands that the numbers are exactly 1 to n x n; our checker is slightly more general and accepts any distinct values.)

The Magic Constant Formula

When a square uses the numbers 1 to n x n, the magic constant is fixed by the size: n * (n * n + 1) / 2. It follows because all numbers add up to n*n*(n*n+1)/2, and that total splits evenly across n rows.

Designing the Magic Square Program Checker

A good checker runs its tests from cheapest and most likely to fail to the most expensive, and it returns the moment something fails. Our order is: distinct elements, then rows, then columns, then diagonals. The target total comes from the first row, so the checker needs no formula and also works for squares that do not use 1 to n x n.

Magic Square Program in C: Checker and Generator

The program has three parts: is_magic checks a matrix, make_siamese builds an odd-sized magic square, and main tests three hand-written matrices and one generated one. The small helper at(m, n, r, c) keeps the expression r * n + c in a single place, so a typo cannot spread through five loops.

Program: ex53a.c

/* ex53a.c - magic square checker plus an odd-order generator */
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stddef.h>

static int at(const int *m, int n, int r, int c)
{
    return m[r * n + c];
}

static bool is_magic(const int *m, int n)
{
    int total = n * n;
    int target = 0;

    /* rule 1: every element must be distinct */
    for (int p = 0; p < total - 1; p++)
        for (int q = p + 1; q < total; q++)
            if (m[p] == m[q]) {
                printf("  rejected: value %d repeats\n", m[p]);
                return false;
            }

    /* the first row decides the target every other line must match */
    for (int c = 0; c < n; c++)
        target += at(m, n, 0, c);

    for (int r = 0; r < n; r++) {
        int sum = 0;
        for (int c = 0; c < n; c++)
            sum += at(m, n, r, c);
        if (sum != target) {
            printf("  rejected: row %d sums to %d, expected %d\n", r, sum, target);
            return false;
        }
    }
    for (int c = 0; c < n; c++) {
        int sum = 0;
        for (int r = 0; r < n; r++)
            sum += at(m, n, r, c);
        if (sum != target) {
            printf("  rejected: column %d sums to %d, expected %d\n", c, sum, target);
            return false;
        }
    }

    int d1 = 0, d2 = 0;
    for (int i = 0; i < n; i++) {
        d1 += at(m, n, i, i);
        d2 += at(m, n, i, n - 1 - i);
    }
    if (d1 != target || d2 != target) {
        printf("  rejected: diagonals are %d and %d, expected %d\n", d1, d2, target);
        return false;
    }

    printf("  accepted: magic constant = %d\n", target);
    return true;
}

/* Siamese method: start top-middle, step up-right, drop down if blocked. */
static void make_siamese(int *m, int n)
{
    int r = 0, c = n / 2;

    memset(m, 0, sizeof(int) * (size_t)n * (size_t)n);
    for (int k = 1; k <= n * n; k++) {
        m[r * n + c] = k;

        int nr = (r - 1 + n) % n;
        int nc = (c + 1) % n;
        if (m[nr * n + nc] != 0) {   /* cell already used: move down instead */
            nr = (r + 1) % n;
            nc = c;
        }
        r = nr;
        c = nc;
    }
}

static void print_matrix(const int *m, int n)
{
    for (int r = 0; r < n; r++) {
        printf("   ");
        for (int c = 0; c < n; c++)
            printf("%3d", at(m, n, r, c));
        printf("\n");
    }
}

int main(void)
{
    int lo_shu[3][3]  = { {2, 7, 6}, {9, 5, 1}, {4, 3, 8} };
    int bad_col[3][3] = { {2, 7, 6}, {9, 5, 1}, {4, 8, 3} };
    int dup[3][3]     = { {1, 2, 3}, {4, 5, 6}, {7, 8, 1} };
    int made5[5 * 5];

    printf("lo_shu:\n");
    is_magic(&lo_shu[0][0], 3);
    printf("bad_col:\n");
    is_magic(&bad_col[0][0], 3);
    printf("dup:\n");
    is_magic(&dup[0][0], 3);

    make_siamese(made5, 5);
    printf("generated 5x5:\n");
    print_matrix(made5, 5);
    is_magic(made5, 5);
    return 0;
}

Walking Through is_magic

• The first double loop compares every pair of the n x n values stored in the flat array, exactly like the matrix duplicate check from lecture 51.
• Rows and columns each use one outer loop that resets sum to 0 for every line. Forgetting that reset is the most common bug in this exercise.
• The diagonals share one loop, reusing the two index rules from lecture 52.
• Each failure prints which rule broke and the actual and expected sums, which makes the output a debugging tool instead of a bare “no”.

The Siamese Method for Odd Orders

Instead of searching for a magic square, you can build one. The Siamese method works for every odd n and needs only these rules:

1. Put 1 in the middle of the top row.
2. For each next number, move one step up and one step right. Wrap around the edges: off the top lands on the bottom row, off the right side lands on column 0.
3. If the target cell is already filled, move one step down from the current cell instead.

In the code, (r - 1 + n) % n performs the upward wrap without ever producing a negative number. Adding n before the remainder is a standard trick, because the % operator on a negative operand gives a negative result in C. The generator also uses memset to zero the array first, so that “0” can mean “empty cell”.

Build and Run

gcc -std=c11 -Wall -Wextra -o ex53a ex53a.c
./ex53a

Expected output:

lo_shu:
  accepted: magic constant = 15
bad_col:
  rejected: column 1 sums to 20, expected 15
dup:
  rejected: value 1 repeats
generated 5x5:
    17 24  1  8 15
    23  5  7 14 16
     4  6 13 20 22
    10 12 19 21  3
    11 18 25  2  9
  accepted: magic constant = 65

Check the generated 5 x 5 square against the formula: 5 * (25 + 1) / 2 = 65, and the checker agrees. The bad_col matrix is a nice teaching case. Its rows all add up to 15, but swapping the last two numbers of the bottom row breaks column 1, which now adds up to 20. A checker that only tested rows would have wrongly accepted it.

Complexity and Memory

If you know the values must be 1 to n x n, replace the quadratic duplicate test with a seen table of n x n flags and a range check. That drops the first step from O(n to the power 4) to O(n squared).

Common Mistakes and Troubleshooting

• Skipping the distinct test. A grid of identical numbers passes every sum test.
• Not resetting the running sum at the start of each row or column.
• Checking only one diagonal. Both must be tested.
• Using the Siamese method for even n. The simple rules fail; even orders need different constructions.
• Taking a negative modulo. (r - 1) % n is -1 when r is 0 and the array index goes out of range. Add n first.
• Hard-coding a target such as 15. That only works for 3 x 3. Derive it from the first row or from the formula.

Best Practices for a Magic Square Program

• In any magic square program, return early with a clear reason. Validation code is read more often when it fails than when it passes.
• Put index arithmetic in one helper so a fix has one place to go.
• Test your checker with known good, known bad and edge inputs before trusting it, just as the main function does here.
• Use the same layered validation habit for firmware inputs: check length, range, uniqueness, and checksum, in that order.

Summary and Key Takeaways

• A magic matrix has distinct values and one common sum for all rows, columns and both diagonals.
• For a normal square of order n the magic constant is n(n squared + 1)/2.
• Read the target from the first row so the checker stays general.
• The Siamese method generates odd-order squares with one pass and a modulo wrap.

You have now written a magic square program in C that both verifies and generates squares, using only arrays, loops and functions. Next we walk through a matrix in spiral order and flip its rows and columns.

Frequently Asked Questions

/* ex53a.c - magic square checker plus an odd-order generator */
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stddef.h>

static int at(const int *m, int n, int r, int c)
{
    return m[r * n + c];
}

static bool is_magic(const int *m, int n)
{
    int total = n * n;
    int target = 0;

    /* rule 1: every element must be distinct */
    for (int p = 0; p < total - 1; p++)
        for (int q = p + 1; q < total; q++)
            if (m[p] == m[q]) {
                printf("  rejected: value %d repeats\n", m[p]);
                return false;
            }

    /* the first row decides the target every other line must match */
    for (int c = 0; c < n; c++)
        target += at(m, n, 0, c);

    for (int r = 0; r < n; r++) {
        int sum = 0;
        for (int c = 0; c < n; c++)
            sum += at(m, n, r, c);
        if (sum != target) {
            printf("  rejected: row %d sums to %d, expected %d\n", r, sum, target);
            return false;
        }
    }
    for (int c = 0; c < n; c++) {
        int sum = 0;
        for (int r = 0; r < n; r++)
            sum += at(m, n, r, c);
        if (sum != target) {
            printf("  rejected: column %d sums to %d, expected %d\n", c, sum, target);
            return false;
        }
    }

    int d1 = 0, d2 = 0;
    for (int i = 0; i < n; i++) {
        d1 += at(m, n, i, i);
        d2 += at(m, n, i, n - 1 - i);
    }
    if (d1 != target || d2 != target) {
        printf("  rejected: diagonals are %d and %d, expected %d\n", d1, d2, target);
        return false;
    }

    printf("  accepted: magic constant = %d\n", target);
    return true;
}

/* Siamese method: start top-middle, step up-right, drop down if blocked. */
static void make_siamese(int *m, int n)
{
    int r = 0, c = n / 2;

    memset(m, 0, sizeof(int) * (size_t)n * (size_t)n);
    for (int k = 1; k <= n * n; k++) {
        m[r * n + c] = k;

        int nr = (r - 1 + n) % n;
        int nc = (c + 1) % n;
        if (m[nr * n + nc] != 0) {   /* cell already used: move down instead */
            nr = (r + 1) % n;
            nc = c;
        }
        r = nr;
        c = nc;
    }
}

static void print_matrix(const int *m, int n)
{
    for (int r = 0; r < n; r++) {
        printf("   ");
        for (int c = 0; c < n; c++)
            printf("%3d", at(m, n, r, c));
        printf("\n");
    }
}

int main(void)
{
    int lo_shu[3][3]  = { {2, 7, 6}, {9, 5, 1}, {4, 3, 8} };
    int bad_col[3][3] = { {2, 7, 6}, {9, 5, 1}, {4, 8, 3} };
    int dup[3][3]     = { {1, 2, 3}, {4, 5, 6}, {7, 8, 1} };
    int made5[5 * 5];

    printf("lo_shu:\n");
    is_magic(&lo_shu[0][0], 3);
    printf("bad_col:\n");
    is_magic(&bad_col[0][0], 3);
    printf("dup:\n");
    is_magic(&dup[0][0], 3);

    make_siamese(made5, 5);
    printf("generated 5x5:\n");
    print_matrix(made5, 5);
    is_magic(made5, 5);
    return 0;
}

gcc -std=c11 -Wall -Wextra -o ex53a ex53a.c
./ex53a

lo_shu:
  accepted: magic constant = 15
bad_col:
  rejected: column 1 sums to 20, expected 15
dup:
  rejected: value 1 repeats
generated 5x5:
    17 24  1  8 15
    23  5  7 14 16
     4  6 13 20 22
    10 12 19 21  3
    11 18 25  2  9
  accepted: magic constant = 65