Question

How to generate all possible 3X3 magic squares in C

Answer 1

#include <stdio.h>
#include <stdbool.h>

/*
    Generate all 3×3 magic squares using a structured backtracking approach.

    A 3×3 magic square uses the numbers 1–9 exactly once.
    Every row, column, and diagonal must sum to the same constant (15).

    Instead of brute‑forcing all 9! permutations, the program prunes early:
    - As soon as a row or column cannot possibly reach 15, exploration stops.
    - This reduces the search space dramatically.
*/

#define MAGIC_SUM 15

// Check whether a fully filled square is magic
static bool is_magic(const int g[9]) {
    return
        g[0] + g[1] + g[2] == MAGIC_SUM &&
        g[3] + g[4] + g[5] == MAGIC_SUM &&
        g[6] + g[7] + g[8] == MAGIC_SUM &&
        g[0] + g[3] + g[6] == MAGIC_SUM &&
        g[1] + g[4] + g[7] == MAGIC_SUM &&
        g[2] + g[5] + g[8] == MAGIC_SUM &&
        g[0] + g[4] + g[8] == MAGIC_SUM &&
        g[2] + g[4] + g[6] == MAGIC_SUM;
}

// Check whether a partially filled square is still viable
static bool valid_partial(const int g[9]) {
    // Helper: check a line only if all cells are filled
    #define CHECK(a,b,c) \
        ((g[a] && g[b] && g[c]) ? (g[a] + g[b] + g[c] == MAGIC_SUM) : true)

    if (!CHECK(0,1,2)) return false;
    if (!CHECK(3,4,5)) return false;
    if (!CHECK(6,7,8)) return false;

    if (!CHECK(0,3,6)) return false;
    if (!CHECK(1,4,7)) return false;
    if (!CHECK(2,5,8)) return false;

    if (!CHECK(0,4,8)) return false;
    if (!CHECK(2,4,6)) return false;

    return true;
}

static void generate_magic_squares(int g[9], bool used[10], int index, int *count) {
    if (index == 9) {
        if (is_magic(g)) {
            (*count)++;
            printf("Magic square:\n");
            for (int i = 0; i < 9; i++) {
                printf("%d%c", g[i], (i % 3 == 2 ? '\n' : ' '));
            }
            printf("\n");
        }
        return;
    }

    for (int n = 1; n <= 9; n++) {
        if (!used[n]) {
            g[index] = n;
            used[n] = true;

            // Prune early if partial grid already violates constraints
            if (valid_partial(g)) {
                generate_magic_squares(g, used, index + 1, count);
            }

            // Undo choice
            used[n] = false;
            g[index] = 0;
        }
    }
}

int main(void) {
    int grid[9] = {0};
    bool used[10] = {false};
    int count = 0;

    generate_magic_squares(grid, used, 0, &count);

    printf("Total: %d magic squares\n", count);
    
    return 0;
}


/*
run:

Magic square:
2 7 6
9 5 1
4 3 8

Magic square:
2 9 4
7 5 3
6 1 8

Magic square:
4 3 8
9 5 1
2 7 6

Magic square:
4 9 2
3 5 7
8 1 6

Magic square:
6 1 8
7 5 3
2 9 4

Magic square:
6 7 2
1 5 9
8 3 4

Magic square:
8 1 6
3 5 7
4 9 2

Magic square:
8 3 4
1 5 9
6 7 2

Total: 8 magic squares

*/

 

70+ SQL courses for beginners and professionals