Latin Square
A mathematical structure where n symbols are arranged in an n x n grid such that each symbol appears exactly once in every row and column. The foundation of Sudoku.
A Latin Square is a combinatorial structure in which n symbols are arranged in an n x n grid so that each symbol appears exactly once in every row and column. It was studied by the 18th-century Swiss mathematician Euler. Sudoku can be viewed as a Latin Square with the additional constraint of 3x3 blocks.
Relationship to Sudoku
A Latin Square is defined by the row and column conditions alone; a 9x9 Sudoku must satisfy the 3x3 block condition in addition to them. A Latin Square that also satisfies the block constraint is a completed Sudoku grid. The total number of Latin Squares is far greater than the number of valid Sudoku grids, showing that the block constraint dramatically restricts the solution space. Mini Sudoku on 4x4 and 6x6 grids has the same relationship, differing only in the block shape (2x2 and 2x3). When solving, a cell whose candidates cannot be narrowed down by rows and columns alone is often fixed once the block constraint is added; this extra constraint is what distinguishes Sudoku from a plain Latin Square.
Applications
Latin Squares are applied in many fields of mathematics and engineering, including experimental design, cryptography, and error-correcting codes. The symbols need not be digits; letters or colors arranged the same way form the same structure. The simplest construction writes 1 to n in the first row and shifts each following row by one position, so a Latin Square exists for every n. Sudoku can be seen as a representative example of applying the structure of Latin Squares to a puzzle for a general audience.