xvi. Grid and Matrix Constructions

Target	Construction
Latin square	$L_{ij}=(i+j)\mathrm{mod}n$
orthogonal Latin squares, $n$ odd	$L_{ij}=(i+j)\mathrm{mod}n$, $M_{ij}=(i+2j)\mathrm{mod}n$
magic square, $n$ odd	Siamese method: move up-right, drop down on collision
magic square, $n\equiv 0(\mathrm{mod}4)$	write $\mathrm{1..}{n}^2$ in order, complement ($v\to n^2+1-v$) the cells on the diagonals of every $4\times 4$ block
magic square, $n\equiv 2(\mathrm{mod}4)$	LUX method (Conway), from the odd square of size $n/2$
Hamiltonian path on a grid	snake (boustrophedon) order
domino tiling of a board with an even number of cells and no holes	pair along rows; colour arguments decide holes
matrix with given row and column sums (non-negative integers)	north-west corner rule: fill greedily $\min (r_i,c_j)$

Magic squares

vector<vector<int>> magicSquare(int n) {       // n odd (Siamese) or n % 4 == 0; values 1..n^2
    vector<vector<int>> a(n, vector<int>(n));
    if (n % 2 == 1) {
        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 {                                   // doubly even: complement the cells on the 4x4 diagonals
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            int v = i * n + j + 1;
            bool diag = (i % 4 == j % 4) || ((i % 4) + (j % 4) == 3);
            a[i][j] = diag ? n * n + 1 - v : v;
        }
    }
    return a;
}

Proof: both constructions are magic

Let $S=\frac{n(n^2+1)}{2}$ and write the 0-indexed value as $t=qn+r$ ($0\le q,r<n$), so the cell holds $t+1$.

Odd $n$ (Siamese). Let $c_0=\frac{n-1}{2}$. Within a run of $n$ consecutive values ($q$ fixed) the walk moves by $(-1,+1)$; after the run it moves by $(+1,0)$, so run $q$ starts at $(2q,c_0-q)$ and value $t$ sits at $(2q-r,c_0-q+r)\mathrm{mod}n$. This map $(q,r)\mapsto$ cell has determinant $2\cdot 1-1\cdot 1=1$, so it is a bijection of ${\mathbb{Z}}_n^2$: no cell is filled twice, and the up-right cell is occupied exactly at the end of a run (it is the run’s first cell), which is when the code steps down. In a fixed row $2q-r=R$, each $q$ appears once with $r=2q-R$, and $r$ also takes every value once ($2$ is invertible mod odd $n$); the same holds in a fixed column ($r=q+C-c_0$). Hence every row and column sums to ${\sum }_{q}qn+{\sum }_{r}r+n=n\frac{n(n-1)}{2}+\frac{n(n-1)}{2}+n=S$. Central symmetry: the cell of $(n-1-q,n-1-r)$ is the reflection $(-1-\text{row},-1-\text{col})$ of the cell of $(q,r)$ (using $2c_0=n-1$), so opposite cells hold $v$ and $n^2+1-v$. The anti-diagonal is the set $q=n-1-c_0$ (row + col $\equiv q+c_0$), which meets every $r$ once, so it sums to $S$; the main diagonal consists of the centre $\frac{n^2+1}{2}$ and $\frac{n-1}{2}$ opposite pairs, each summing to $n^2+1$, so it sums to $S$ too.

$n\equiv 0(\mathrm{mod}4)$. Let $v(i,j)=in+j+1$. A cell is marked iff $j\mathrm{mod}4\in \{i\mathrm{mod}4,3-i\mathrm{mod}4\}$; marked cells get $n^2+1-v(i,j)=v(n-1-i,n-1-j)$. Each row has exactly $n/2$ marked cells, and inside every block of 4 columns the marked offsets sum to $3$, the same as the unmarked ones, so the row sum is $\frac{n}{2}\cdot in+\frac{n}{2}(n-1-i)n+\frac{n}{2}(n-1)+n=S$. The pattern is symmetric in $i\leftrightarrow j$, so columns work the same way. Every diagonal cell is marked: the main diagonal holds $v(n-1-i,n-1-i)$, a permutation of the natural diagonal ${\sum }_i(i(n+1)+1)=S$, and the anti-diagonal similarly. Both constructions were checked for all valid $n\le 40$.

Related: Constructive Algorithms, Profile DP (counting tilings).