Question

How to generate a random 3×3 magic square in C++

Answer 1

#include <iostream>
#include <vector>
#include <array>
#include <algorithm> // next_permutation
#include <random>

// A square is stored as 9 cells in row-major order: index = row*3 + col
using Square = std::array<int, 9>;

// Checks whether a square is magic: every row, every column, and both
// diagonals must sum to the same value. Returns true and writes that
// common sum into magicSum if the square qualifies.
bool isMagic(const Square& sq, int& magicSum) {
    std::array<int, 3> rowSum{}, colSum{};
    int mainDiag = 0, antiDiag = 0;

    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            int v = sq[r * 3 + c];
            rowSum[r] += v;
            colSum[c] += v;
            if (r == c)     mainDiag += v; // top-left to bottom-right
            if (r == 2 - c) antiDiag += v; // top-right to bottom-left
        }
    }

    magicSum = rowSum[0];
    for (int r = 0; r < 3; ++r) if (rowSum[r] != magicSum) return false;
    for (int c = 0; c < 3; ++c) if (colSum[c] != magicSum) return false;
    
    return mainDiag == magicSum && antiDiag == magicSum;
}

// Enumerates all 9! = 362,880 permutations of {1,...,9} using
// std::next_permutation (which generates permutations in lexicographic
// order with no duplicates and no extra bookkeeping), and collects every
// arrangement that forms a magic square. This exhaustive pass is cheap:
// 362,880 iterations, each doing O(1) work, comfortably fast at runtime.
std::vector<Square> collectAllMagicSquares() {
    std::vector<Square> results;
    results.reserve(8); // exactly 8 magic squares exist for digits 1-9

    Square current;
    std::iota(current.begin(), current.end(), 1); // fill with 1..9

    do {
        int sum;
        if (isMagic(current, sum)) {
            results.push_back(current);
        }
    } while (std::next_permutation(current.begin(), current.end()));

    return results;
}

// Prints a square in a readable grid layout, plus its magic sum.
void printSquare(const Square& sq) {
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            std::cout << sq[r * 3 + c] << (c < 2 ? ' ' : '\n');
        }
    }
    int sum;
    isMagic(sq, sum);
    std::cout << "Magic sum per row/column/diagonal: " << sum << '\n';
}

int main() {
    // Step 1: build the full list of valid 3x3 magic squares (digits 1-9) once.
    std::vector<Square> allMagicSquares = collectAllMagicSquares();

    if (allMagicSquares.empty()) {
        std::cerr << "No magic squares found (unexpected).\n";
        return 1;
    }

    // Step 2: pick one uniformly at random using a proper random engine
    // (Mersenne Twister seeded from a hardware entropy source), rather
    // than relying on rand()/srand().
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<std::size_t> dist(0, allMagicSquares.size() - 1);

    const Square& chosen = allMagicSquares[dist(rng)];

    std::cout << "Found " << allMagicSquares.size()
              << " valid 3x3 magic squares (digits 1-9).\n"
              << "Randomly selected one:\n\n";
    printSquare(chosen);
}



/*
run:

Found 8 valid 3x3 magic squares (digits 1-9).
Randomly selected one:

6 1 8
7 5 3
2 9 4
Magic sum per row/column/diagonal: 15

*/

 

70+ SQL courses for beginners and professionals