Question

How to generate all possible 3X3 magic squares in C++

Answer 1

#include <array>
#include <vector>
#include <iostream>

/*
    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, we prune early:
    - As soon as a row or column cannot possibly reach 15, we stop exploring.
    - This dramatically reduces the search space.
*/

// Represents a 3×3 grid
using Grid = std::array<int, 9>;

// Check whether a partially filled grid is still viable
bool isValidPartial(const Grid& g, int filledCount) {
    // Magic constant for 3×3
    constexpr int target = 15;

    // Helper lambda to check a line only if all its cells are filled
    auto checkLine = [&](int a, int b, int c) {
        if (g[a] != 0 && g[b] != 0 && g[c] != 0) {
            return (g[a] + g[b] + g[c]) == target;
        }
        return true; // not fully filled → cannot judge yet
    };

    // Check rows
    if (!checkLine(0,1,2)) return false;
    if (!checkLine(3,4,5)) return false;
    if (!checkLine(6,7,8)) return false;

    // Check columns
    if (!checkLine(0,3,6)) return false;
    if (!checkLine(1,4,7)) return false;
    if (!checkLine(2,5,8)) return false;

    // Check diagonals
    if (!checkLine(0,4,8)) return false;
    if (!checkLine(2,4,6)) return false;

    return true;
}

// Check full magic square
bool isMagic(const Grid& g) {
    constexpr int target = 15;
    auto sum = [&](int a, int b, int c) { return g[a] + g[b] + g[c]; };

    return
        sum(0,1,2) == target &&
        sum(3,4,5) == target &&
        sum(6,7,8) == target &&
        sum(0,3,6) == target &&
        sum(1,4,7) == target &&
        sum(2,5,8) == target &&
        sum(0,4,8) == target &&
        sum(2,4,6) == target;
}

// Backtracking search
void generateMagicSquares(Grid& g, std::vector<bool>& used, int index,
                          std::vector<Grid>& results) {
    if (index == 9) {
        if (isMagic(g)) {
            results.push_back(g);
        }
        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 (isValidPartial(g, index + 1)) {
                generateMagicSquares(g, used, index + 1, results);
            }

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

int main() {
    Grid grid{};
    std::vector<bool> used(10, false); // numbers 1–9
    std::vector<Grid> results;

    generateMagicSquares(grid, used, 0, results);

    // Print results
    for (const auto& g : results) {
        std::cout << "Magic square:\n";
        for (int i = 0; i < 9; ++i) {
            std::cout << g[i] << (i % 3 == 2 ? '\n' : ' ');
        }
        std::cout << '\n';
    }

    std::cout << "Total: " << results.size() << " magic squares\n";
}



/*
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