An early crop of Sudoku

The invention of the puzzle we now call Sudoku is generally credited to Howard Garns, an architect from Indianapolis. His first puzzles, which were known then as Number Place, were published in 1979. But now a curious precedent has turned up. More than 20 years earlier, in the 1950s, W. U. Behrens of Hannover, Germany, discussed very similar grids filled with numbers—not as a game or a puzzle for the amusement of newspaper readers but as a design for agricultural experiments. The connection is pointed out in a new paper (PDF) by R. A. Bailey and Peter J. Cameron of the University of London and Robert Connelly of Cornell University.

Both Sudoku and the Behrens designs trace their heritage back to Latin squares, studied by the 18th-century mathematician Leonhard Euler. In an n-by-n Latin square, each of the numbers from 1 through n appears exactly once in each column and row. A standard Sudoku puzzle is a 9-by-9 Latin square with the additional constraint that each number from 1 through 9 also appears exactly once in each of nine 3-by-3 blocks, or regions, into which the grid is subdivided.

What could this possibly have to do with agriculture? Suppose you’re testing several new seed varieties to see which ones produce the best yield. When you lay out test plots in a field, you need to be careful to avoid biases, such as putting all the samples of one variety in the area that has the most water or the richest soil. A Latin-square arrangement is a good start on such a design. With n crop varieties, an n-by-n Latin square assures that each plant type is equally represented in every column and every row, compensating for many common patterns of variation, such as a field that gets steadily moister from one side to the other. But a Latin-square arrangement cannot guarantee fairness in the presence of other patterns, such as compact patches of better or worse soil. And so Behrens proposed choosing designs from a subclass of all Latin squares, namely those in which numbers are distributed evenly not only among the columns and rows but also in predefined blocks. This subclass of Latin squares he called gerechte designs, meaning fair or impartial.

The blocks in Behrens’s designs are not always squares (obviously, an n-by-n array can be subdivided into smaller squares only if n itself is a perfect square). Here is a pattern he proposed for the case of n = 5. I have erased some of the numbers, in order to turn the diagram into an easy mini-pseudo-Sudoku puzzle:

Behrens did go on to consider the case of a 9-by-9 grid with 3-by-3 blocks, and so the following figure may well represent the first published Sudoku solutions:

The figure is taken from: Behrens, W. U. 1956. Feldversuchsanordnungen mit verbessertem Ausgleich der Bodenunterscheide. Zeitschrift für Landwirtschaftliches Versuchsund Untersuchsungswesen 2:176–193. (Scanned copy courtesy of Robert Connelly.) For the case of 4-by-4 grids, Bailey, Cameron and Connelly note an even earlier precedent: Yates, F. 1939. The comparative advantages of systematic and randomized arrangements in the design of agricultural and biological experiments. Biometrika 30:440–466.

Apart from illuminating the prehistory of Sudoku, Bailey, Cameron and Connelly also investigate a number of variations where additional symmetry conditions are imposed. For example, can you create a puzzle (on the standard Sudoku grid) where no number appears in the same relative location within any two of the nine blocks? Connelly also gives further examples and discussion at his web site. Some similar variations have also appeared on Ed Pegg’s marvelous MathPuzzle site.