Question

How to generate a random 4×4 binary magic square (using only 0 and 1) in C++

Answer 1

#include <iostream>
#include <vector>
#include <array>
#include <random>
#include <functional>

/*
    ============================================================
    Generate a random 4×4 magic square containing only 0 and 1.

    A valid square must satisfy:
      • All rows sum to the same target value.
      • All columns sum to that same target value.
      • Both diagonals also match that target value.

    The algorithm:
      1. Precompute all 4‑bit binary rows.
      2. Group rows by their sum.
      3. Use backtracking with pruning to generate all magic squares.
      4. Select one at random.

    This avoids brute‑forcing all 2^16 grids and is efficient.
    ============================================================
*/

// Generate all binary rows of length 4
std::vector<std::array<int,4>> generateBinaryRows() {
    std::vector<std::array<int,4>> rows;
    for (int n = 0; n < 16; ++n) {
        std::array<int,4> row{};
        for (int i = 0; i < 4; ++i)
            row[3 - i] = (n >> i) & 1;
        rows.push_back(row);
    }
    
    return rows;
}

// Generate all magic squares
std::vector<std::vector<std::array<int,4>>> generateAllMagicSquares() {
    auto rows = generateBinaryRows();

    // Group rows by sum
    std::vector<std::vector<std::array<int,4>>> rowsBySum(5);
    for (auto &r : rows)
        rowsBySum[ r[0] + r[1] + r[2] + r[3] ].push_back(r);

    std::vector<std::vector<std::array<int,4>>> results;

    // Try all possible magic sums
    for (int target = 0; target <= 4; ++target) {
        auto &candidates = rowsBySum[target];

        std::vector<std::array<int,4>> square;
        std::array<int,4> colSums{0,0,0,0};

        // Backtracking function
        std::function<void(int)> build = [&](int rowIndex) {
            if (rowIndex == 4) {
                // Check diagonals
                int mainDiag = square[0][0] + square[1][1] + square[2][2] + square[3][3];
                int antiDiag = square[0][3] + square[1][2] + square[2][1] + square[3][0];

                if (mainDiag == target && antiDiag == target)
                    results.push_back(square);

                return;
            }

            for (auto &row : candidates) {
                bool feasible = true;

                // Column pruning
                for (int c = 0; c < 4; ++c) {
                    if (colSums[c] + row[c] > target) {
                        feasible = false;
                        break;
                    }
                }
                if (!feasible) continue;

                // Place row
                square.push_back(row);
                std::array<int,4> oldCols = colSums;
                for (int c = 0; c < 4; ++c) colSums[c] += row[c];

                build(rowIndex + 1);

                // Undo row
                square.pop_back();
                colSums = oldCols;
            }
        };

        build(0);
    }

    return results;
}

int main() {
    auto allSquares = generateAllMagicSquares();

    if (allSquares.empty()) {
        std::cout << "No magic squares found.\n";
        return 0;
    }

    // Random selection
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(0, allSquares.size() - 1);

    auto &sq = allSquares[ dist(gen) ];

    std::cout << "Random 4×4 binary magic square:\n";
    for (auto &row : sq) {
        for (int v : row) std::cout << v << " ";
        std::cout << "\n";
    }
}


/*
run:

Random 4×4 binary magic square:
0 1 1 1 
1 1 0 1 
1 1 1 0 
1 0 1 1 

*/

 

70+ SQL courses for beginners and professionals

Answer 2

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

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

// Builds a 4x4 square from a 16-bit mask: bit i becomes cell i (0 or 1).
Square buildSquareFromMask(unsigned mask) {
    Square sq{};
    for (int i = 0; i < 16; ++i) {
        sq[i] = (mask >> i) & 1;
    }
    
    return sq;
}

// Checks whether a square is "magic": every row, every column, and both
// diagonals must all 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, 4> rowSum{}, colSum{};
    int mainDiag = 0, antiDiag = 0;

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

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

// Scans all 65,536 possible 4x4 binary grids and collects every one that
// satisfies the magic-square property. This exhaustive pass is cheap
// (constant-size, ~2^16 iterations) and guarantees we know the full
// population to sample from uniformly.
std::vector<Square> collectAllMagicSquares() {
    std::vector<Square> results;
    results.reserve(4096); // rough headroom; avoids repeated reallocations

    for (unsigned mask = 0; mask < 65536u; ++mask) {
        Square candidate = buildSquareFromMask(mask);
        int sum;
        if (isMagic(candidate, sum)) {
            results.push_back(candidate);
        }
    }
    
    return results;
}

// Prints a square in a readable grid layout, plus its magic sum.
void printSquare(const Square& sq) {
    for (int r = 0; r < 4; ++r) {
        for (int c = 0; c < 4; ++c) {
            std::cout << sq[r * 4 + c] << (c < 3 ? ' ' : '\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 4x4 binary magic squares 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 4x4 binary magic squares.\n"
              << "Randomly selected one:\n\n";
    printSquare(chosen);
}


/*
run:

Found 34 valid 4x4 binary magic squares.
Randomly selected one:

1 0 0 1
0 1 1 0
1 0 0 1
0 1 1 0
Magic sum per row/column/diagonal: 2

*/

 

70+ SQL courses for beginners and professionals