#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 3
#define CELLS (N * N)
#define MAX_MAGIC_SQUARES 8 /* exact count for digits 1-9 */
/* A square is stored as 9 ints in row-major order: index = row*3 + col */
typedef struct {
int cell[CELLS];
} Square;
/* Advances 'arr' (length n) to the next lexicographic permutation in place.
* Returns 1 if a next permutation exists, 0 if 'arr' was already the last
* (fully descending) permutation. This is the standard constant-amortized
* algorithm: find the rightmost ascent, find the smallest element to its
* right that is still larger, swap, then reverse the suffix. */
int next_permutation(int *arr, int n) {
int i = n - 2;
while (i >= 0 && arr[i] >= arr[i + 1]) {
--i;
}
if (i < 0) {
return 0; /* already the last permutation */
}
int j = n - 1;
while (arr[j] <= arr[i]) {
--j;
}
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
for (int lo = i + 1, hi = n - 1; lo < hi; ++lo, --hi) {
tmp = arr[lo]; arr[lo] = arr[hi]; arr[hi] = tmp;
}
return 1;
}
/* Checks whether 'sq' is magic: every row, every column, and both
* diagonals must sum to the same value. Returns 1 and writes that common
* sum into *magic_sum if the square qualifies; returns 0 otherwise. */
int is_magic(const Square *sq, int *magic_sum) {
int row_sum[N] = {0}, col_sum[N] = {0};
int main_diag = 0, anti_diag = 0;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
int v = sq->cell[r * N + c];
row_sum[r] += v;
col_sum[c] += v;
if (r == c) main_diag += v; /* top-left to bottom-right */
if (r == N - 1 - c) anti_diag += v; /* top-right to bottom-left */
}
}
*magic_sum = row_sum[0];
for (int r = 0; r < N; ++r) if (row_sum[r] != *magic_sum) return 0;
for (int c = 0; c < N; ++c) if (col_sum[c] != *magic_sum) return 0;
return (main_diag == *magic_sum) && (anti_diag == *magic_sum);
}
/* Enumerates all 9! = 362,880 permutations of {1,...,9} via
* next_permutation (lexicographic order, no duplicates, no extra memory),
* and collects every arrangement that forms a magic square into 'out'.
* Returns the number of magic squares found. This exhaustive pass is
* cheap: 362,880 iterations of O(1) work, well under a second at runtime. */
int collect_all_magic_squares(Square out[MAX_MAGIC_SQUARES]) {
int current[CELLS];
for (int i = 0; i < CELLS; ++i) {
current[i] = i + 1; /* fill with 1..9 */
}
int count = 0;
do {
Square candidate;
for (int i = 0; i < CELLS; ++i) {
candidate.cell[i] = current[i];
}
int sum;
if (is_magic(&candidate, &sum)) {
if (count < MAX_MAGIC_SQUARES) {
out[count++] = candidate;
}
}
} while (next_permutation(current, CELLS));
return count;
}
/* Prints a square in a readable grid layout, plus its magic sum. */
void print_square(const Square *sq) {
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
printf("%d%c", sq->cell[r * N + c], (c < N - 1) ? ' ' : '\n');
}
}
int sum;
is_magic(sq, &sum);
printf("Magic sum per row/column/diagonal: %d\n", sum);
}
int main(void) {
/* Step 1: build the full list of valid 3x3 magic squares (digits 1-9)
* once. There are exactly 8, so a fixed-size array is sufficient and
* avoids any dynamic memory management. */
Square all_magic_squares[MAX_MAGIC_SQUARES];
int count = collect_all_magic_squares(all_magic_squares);
if (count == 0) {
fprintf(stderr, "No magic squares found (unexpected).\n");
return 1;
}
/* Step 2: pick one uniformly at random. Seed the standard library's
* pseudo-random generator once from the current time, then use
* rand() with the classic scaling trick to get an unbiased index
* in range [0, count). */
srand((unsigned int)time(NULL));
int index = rand() % count;
const Square *chosen = &all_magic_squares[index];
printf("Found %d valid 3x3 magic squares (digits 1-9).\n", count);
printf("Randomly selected one:\n\n");
print_square(chosen);
return 0;
}
/*
run:
Found 8 valid 3x3 magic squares (digits 1-9).
Randomly selected one:
4 9 2
3 5 7
8 1 6
Magic sum per row/column/diagonal: 15
*/
