Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes

Solving a Sudoku puzzle involves putting the symbols 1,..., 9 into the cells of a 9 × 9 grid partitioned into 3 × 3 subsquares, in such a way that each symbol occurs just once in each row, column, or subsquare. Such a solution is a special case of a gerechte design, in which an n×n grid is partitioned into n regions with n squares in each, and each of the symbols 1,..., n occurs once in each row, column, or region. Gerechte designs originated in statistical design of agricultural experiments, where they ensure that treatments are fairly exposed to localised variations in the field containing the experimental plots. In this paper we consider several related topics. In the first section, we define gerechte designs and some generalizations, and explain a computational technique for finding and classifying them. The second section looks at the statistical background, explaining how such designs are used for designing agricultural experiments, and what additional properties statisticians would like them to have. In the third section, we focus on a special class of Sudoku solutions which we call “symmetric”. They turn out to be related to some important topics in finite geometry over the 3-element field, and to This research partially supported by NSF Grant Number DMS-0510625. 1 error-correcting codes. We explain all of these connections, and use them to classify the symmetric Sudoku solutions (there are just two, up to the appropriate notion of equivalence). In the final section, we construct some further Sudoku solutions with desirable statistical properties, and briefly consider some generalizations. 1 Gerechte designs 1.1