#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
============================================================
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.
============================================================
*/
#define ROWS 16
#define SIZE 4
/* Generate all 4-bit binary rows */
void generate_binary_rows(int rows[ROWS][SIZE]) {
for (int n = 0; n < ROWS; n++) {
for (int i = 0; i < SIZE; i++)
rows[n][SIZE - 1 - i] = (n >> i) & 1;
}
}
/* Store all magic squares found */
typedef struct {
int squares[500][SIZE][SIZE];
int count;
} MagicList;
/* Backtracking search */
void search_magic(int target, int (*candidates)[SIZE], int cand_count,
MagicList *list, int square[SIZE][SIZE],
int col_sums[SIZE], int row_index) {
if (row_index == SIZE) {
/* Check diagonals */
int main_diag = 0, anti_diag = 0;
for (int i = 0; i < SIZE; i++) {
main_diag += square[i][i];
anti_diag += square[i][SIZE - 1 - i];
}
if (main_diag == target && anti_diag == target) {
/* Save square */
for (int r = 0; r < SIZE; r++)
for (int c = 0; c < SIZE; c++)
list->squares[list->count][r][c] = square[r][c];
list->count++;
}
return;
}
for (int i = 0; i < cand_count; i++) {
int feasible = 1;
/* Column pruning */
for (int c = 0; c < SIZE; c++) {
if (col_sums[c] + candidates[i][c] > target) {
feasible = 0;
break;
}
}
if (!feasible) continue;
/* Place row */
for (int c = 0; c < SIZE; c++) {
square[row_index][c] = candidates[i][c];
}
int old_cols[SIZE];
for (int c = 0; c < SIZE; c++) {
old_cols[c] = col_sums[c];
col_sums[c] += candidates[i][c];
}
search_magic(target, candidates, cand_count, list, square, col_sums, row_index + 1);
/* Undo */
for (int c = 0; c < SIZE; c++)
col_sums[c] = old_cols[c];
}
}
/* Generate all magic squares */
MagicList generate_all_magic_squares() {
MagicList list = { .count = 0 };
int rows[ROWS][SIZE];
generate_binary_rows(rows);
/* Group rows by sum */
int grouped[5][ROWS][SIZE];
int group_count[5] = {0};
for (int i = 0; i < ROWS; i++) {
int sum = rows[i][0] + rows[i][1] + rows[i][2] + rows[i][3];
int idx = group_count[sum]++;
for (int j = 0; j < SIZE; j++)
grouped[sum][idx][j] = rows[i][j];
}
/* Try all target sums */
for (int target = 0; target <= 4; target++) {
int square[SIZE][SIZE];
int col_sums[SIZE] = {0};
search_magic(target, grouped[target], group_count[target],
&list, square, col_sums, 0);
}
return list;
}
int main() {
srand((unsigned)time(NULL));
MagicList list = generate_all_magic_squares();
if (list.count == 0) {
printf("No magic squares found.\n");
return 0;
}
/* Pick one at random */
int idx = rand() % list.count;
printf("Random 4×4 binary magic square:\n");
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++)
printf("%d ", list.squares[idx][r][c]);
printf("\n");
}
return 0;
}
/*
run:
Random 4×4 binary magic square:
0 1 0 1
0 1 0 1
1 0 1 0
1 0 1 0
*/
