Magic square

Fill an n×n grid (n odd) with 1 to n² so every row, column and diagonal has the same sum, by the Siamese method: one up, one right.

In a magic square all rows, columns and both diagonals have the same sum: n(n² + 1) / 2.

Read the full explanation ↓

Time: O(n²)
Space: O(n²)
Horowitz–Sahni, chapter 1

Input:

n=3PDF export

The 3×3 square (the Lo Shu): every row, column and diagonal adds up to 15.

def magic_square(n):
if n % 2 == 0:
return None
square = [[0] * n for _ in range(n)]
r, c = 0, n // 2
for k in range(1, n * n + 1):
square[r][c] = k
nr, nc = (r - 1) % n, (c + 1) % n # up and to the right, wrapping around
if square[nr][nc] != 0:
nr, nc = (r + 1) % n, c
r, c = nr, nc
return square

Invariant: The numbers run along wrapped diagonals, n per diagonal; then one step down starts the next diagonal.

Start

k—

r—

c—

The table is still empty.

Local variables

Orange = changed in this step

Call stack

magic_square()line 1

Step 1 of 54

Explanation

The idea

In a magic square all rows, columns and both diagonals have the same sum: n(n² + 1) / 2.

The Siamese method (n odd)

Put 1 in the middle of the top row.
Put each next number one up and one right; if you leave the grid, come back on the other side (the grid wraps around).
If that square is taken, put the number one below the previous one instead.

The numbers run along wrapped diagonals; each diagonal holds exactly n squares, and every row and column gets exactly one number from each group of n, which is why the sums agree.

What to watch in the trace

The table is the square; notice that after every n numbers there is one step down.