xlii. Magic Squares

Problem. Arrange $\mathrm{1..}{n}^2$ in an $n\times n$ grid so that every row, column and both main diagonals have the same sum, the magic constant $M_n=\frac{n(n^2+1)}{2}$ ($15,34,65,111,\dots$). Possible for every $n\ne 2$.

$n$	Method	Idea
odd	Siamese (de la Loubère)	walk up-right, wrap around; step down when the cell is taken
$n\equiv 0(\mathrm{mod}4)$ (doubly even)	complement the diagonals of every $4\times 4$ block	write $\mathrm{1..}{n}^2$ in order, replace $v$ by $n^2+1-v$ on the marked cells
$n\equiv 2(\mathrm{mod}4)$ (singly even, $n\ge 6$)	LUX (Conway)	take an odd square of order $k=n/2$, blow each cell up into a $2\times 2$ block filled in an L, U or X pattern
$n=2$	impossible	$a+b=a+c$ forces $b=c$

Order	Number of magic squares (rotations and reflections counted)
3	8 (all are the Lo Shu square up to symmetry)
4	7040 (880 up to symmetry; Frénicle, 1693)
5	$8\cdot 275305224$ (Schroeppel, 1973, computer count)

vector<vector<int>> magicSquareAny(int n) {           // any n != 2; values 1..n^2
    vector<vector<int>> a(n, vector<int>(n));
    if (n % 2 == 1) {                                  // Siamese
        int r = 0, c = n / 2;
        for (int v = 1; v <= n * n; v++) {
            a[r][c] = v;
            int nr = (r - 1 + n) % n, nc = (c + 1) % n;
            if (a[nr][nc]) nr = (r + 1) % n, nc = c;
            r = nr, c = nc;
        }
    } else if (n % 4 == 0) {                           // doubly even
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            int v = i * n + j + 1;
            a[i][j] = (i % 4 == j % 4 || i % 4 + j % 4 == 3) ? n * n + 1 - v : v;
        }
    } else {                                           // LUX, n = 2k, k = 2m + 1 odd
        int k = n / 2, m = (k - 1) / 2;
        auto A = magicSquareAny(k);
        static const int pat[3][2][2] = {{{4, 1}, {2, 3}}, {{1, 4}, {2, 3}}, {{1, 4}, {3, 2}}};   // L, U, X
        for (int i = 0; i < k; i++) for (int j = 0; j < k; j++) {
            int t = i <= m ? 0 : i == m + 1 ? 1 : 2;   // rows 0..m: L, row m+1: U, the rest: X
            if (j == m && i == m) t = 1;               // swap the middle L with the U below it
            if (j == m && i == m + 1) t = 0;
            for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++) a[2 * i + x][2 * j + y] = 4 * (A[i][j] - 1) + pat[t][x][y];
        }
    }
    return a;
}

Proof: the magic constant, the odd and doubly even methods, and the 3 × 3 squares

Constant. The $n$ rows partition the grid, so each row sums to $\frac{1}{n}{\sum }_{v=1}^{n^2}v=\frac{n(n^2+1)}{2}$.

Odd and doubly even. The Siamese walk and the diagonal-complement construction are proved magic in Grid and Matrix Constructions (same code).

$3\times 3$. The middle row, middle column and both diagonals all pass through the centre $c$ and together cover every cell once, plus the centre three more times: $4\cdot 15=45+3c$, so $c=5$, and every line through the centre pairs opposite cells summing to $10$. If $1$ were in a corner, its row and column would each need two other numbers summing to $14$ from $\{2,3,4,6,7,8\}$ ($9$ is opposite, on the diagonal); only $6+8$ works, and it cannot be used twice. So $1$ sits in the middle of an edge with $9$ opposite; the line through $1$ along the edge needs a pair summing to $14$ from the rest: $\{6,8\}$, in two orders; then all other cells are forced by the opposite-sum rule. That gives $4$ (position of $1$) $\cdot 2$ (order of $6,8$) $=8$ squares, the symmetries of the Lo Shu. The 4 × 4 count 7040 was confirmed by an exhaustive search (rows as 4-subsets summing to 34, then row and column arrangements).

Proof: LUX is magic

Let $A$ be the odd magic square of order $k=2m+1$ with constant $M_k$. Block $(i,j)$ holds $4(A_{ij}-1)+p$ for the four entries $p\in \{1,2,3,4\}$ of its pattern, so all values $\mathrm{1..4}{k}^2$ appear once. Pattern sums:

Pattern	top row	bottom row	left column	right column	$\searrow$ diagonal	$\swarrow$ diagonal
L $\begin{array}{cc}4& 1\\ 2& 3\end{array}$	5	5	6	4	7	3
U $\begin{array}{cc}1& 4\\ 2& 3\end{array}$	5	5	3	7	4	6
X $\begin{array}{cc}1& 4\\ 3& 2\end{array}$	5	5	4	6	3	7

Each big row or column takes two entries from each of $k$ blocks of one block row or column, contributing $\sum 8(A-1)=8M_k-8k$ from the offsets; each big diagonal takes two entries from each diagonal block of $A$, contributing the same. It remains to show the pattern parts sum to $5k$ every time; then every line sums to $8M_k-3k=4k^3+k=M_{2k}$.

Rows: every pattern gives 5 per row. Columns: every block column has $m+1$ L’s, one U and $m-1$ X’s (the swap in column $m$ only exchanges an L and a U), so the left column gives $6(m+1)+3+4(m-1)=10m+5$ and the right column $4(m+1)+7+6(m-1)=10m+5$. Main diagonal (blocks $(i,i)$, using the $\searrow$ entries): L for $i<m$, U at $i=m$ (swapped) and at $i=m+1$, X for $i\ge m+2$: $7m+4+4+3(m-1)=10m+5$. Anti-diagonal (blocks $(i,2m-i)$, using the $\swarrow$ entries): L for $i<m$, U at $i=m$ (swapped) and at $i=m+1$ (column $m-1$ of the U row), X after: $3m+6+6+7(m-1)=10m+5$. Since $10m+5=5k$, the square is magic. Checked for every $n\le 60$, $n\ne 2$.

Related notes

• Grid and Matrix Constructions
• Latin Squares and Euler’s 36 Officers (Euler built magic squares from orthogonal Latin squares)