Why Does Every Symbol Appear Once in Each Row? A Grid With Rules

Take a grid of some size and fill it with that many different symbols, subject to one rule, namely that no symbol repeats within any row or within any column. A grid of three by three filled with three symbols, or of nine by nine filled with nine, is the standard case. The rule looks trivial and the consequences are not, since the number of ways to fill such a grid grows explosively with size, and counting them exactly has been achieved only up to grids of around eleven by eleven. Euler studied these arrangements in the eighteenth century and gave them the name, using Latin characters as the symbols to distinguish them from a related construction using Greek ones.

The same structure appears in several places that look unrelated:

• •Sudoku, which adds a further constraint on each three by three block
• •The multiplication table of any finite group, which always forms one
• •Round robin tournament schedules, where each competitor meets each other once
• •Error correcting codes, built from families of these grids
• •Agricultural field trials, which is where the modern application began
• •Scheduling problems where two kinds of resource must not clash

The application that matters most came from agriculture, where a field varies systematically in fertility, drainage and exposure, so comparing several crop varieties by planting each in one area confounds the variety with the ground it happened to occupy. Arranging the plots as such a grid places each variety once in every row and once in every column, which balances it across both directions of variation, so any systematic gradient affects all varieties equally and cancels out of the comparison. Ronald Fisher developed this into a standard method at Rothamsted in the 1920s, and the same design is now used wherever two sources of unwanted variation must be controlled at once, including clinical trials, industrial testing and psychology experiments where order of presentation matters.

The number of ways to fill such a grid grows faster than almost any quantity encountered in ordinary mathematics, and the growth defeats every approach tried. A grid of three by three has twelve arrangements. Five by five has over a hundred and sixty thousand. Nine by nine, the sudoku size, has a figure with twenty eight digits. Eleven by eleven was counted in 2005 after substantial computation and has fifty two digits. Twelve has never been counted and is not expected to be by any current method, since the work scales far worse than the size suggests. Good bounds exist, giving upper and lower limits that are themselves enormous, and exact enumeration has simply stopped being the interesting question.

Two such grids of the same size are called orthogonal if superimposing them puts every possible pair of symbols together exactly once, and constructing them is far harder than constructing one. Euler observed that they exist for odd sizes and for multiples of four, failed to find any of size six, and conjectured in 1782 that none exist for six, ten, fourteen and so on. The case of six was verified by exhaustive checking in 1901, confirming his conjecture there, and the rest of the conjecture was demolished in 1959 when a pair of size ten was constructed, followed by a proof that they exist for every size except two and six. It stood for nearly two centuries and turned out to be wrong everywhere except the case he had actually checked.

A grid where every symbol appears once per row and once per column is the structure behind sudoku, group multiplication tables and round robin schedules. Arranging experimental plots this way balances each treatment across two directions of variation at once, which is why Fisher made it standard for field trials. Euler's conjecture about superimposable pairs stood for nearly two centuries and proved wrong for every case but one.