What Is a Latin Square? Every Finished Sudoku Is One

Here are the digits 1, 2 and 3, placed so that each appears once in every row and once in every column.
1 2 3
2 3 1
3 1 2
A table like this is called a Latin square. The Wikipedia article Latin square defines it as an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. The table above is a Latin square of order 3.
A finished sudoku grid is a Latin square too. The same article says that any sudoku solution is a Latin square. I touched on this in Sudoku vs Nanpure and How Many Sudoku Grids Are There?. This post is about Latin squares themselves.
Where the name comes from
The name goes back to papers by the 18th-century mathematician Leonhard Euler, who used Latin letters as the symbols in his squares.
The symbols can be digits, letters or colours. Replace 1 with A, 2 with B and 3 with C in the first table, and you get this:
A B C
B C A
C A B
Each row and each column still has A, B and C once. It is the same Latin square.
How many small Latin squares there are
Of order 2, there are only two.
1 2 2 1
2 1 1 2
The number climbs quickly as the order grows. The Wikipedia article has a table of counts. Here are the first five orders.
| Order | All Latin squares | Reduced |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 12 | 1 |
| 4 | 576 | 4 |
| 5 | 161,280 | 56 |
A reduced Latin square is one whose first row and first column are in their natural order, 1, 2, 3 and so on. Of order 3, the first table in this post is the only reduced one.
The same table gives 5,524,751,496,156,892,842,531,225,600 Latin squares of order 9. There are 6,670,903,752,021,072,936,960 finished sudoku grids.
What sudoku adds
A Latin square only asks that no symbol repeats in a row or a column. Sudoku adds the 3×3 box rule.
A 4×4 grid makes the difference easy to see. A 4×4 sudoku uses 1 to 4, with no repeats in a row, a column or a 2×2 box.
1 2 | 3 4
2 1 | 4 3
3 4 | 1 2
4 3 | 2 1
Every row and every column has 1 to 4 once, so this is a Latin square. But the top-left box has two 1s and two 2s. It is not a sudoku solution.
Swap rows 2 and 3:
1 2 | 3 4
3 4 | 1 2
2 1 | 4 3
4 3 | 2 1
Now each of the four boxes has 1 to 4 once. This is a Latin square and a 4×4 sudoku solution.
There are 576 Latin squares of order 4. The number of completed 4×4 sudoku grids is 288, according to OEIS A107739. At order 4, exactly half of the Latin squares are sudoku solutions.
Choi Seok-jeong in 1700, and Euler
According to the Wikipedia article, the Korean mathematician Choi Seok-jeong was the first to publish an example of Latin squares of order nine, in 1700. That was 67 years before Euler.
Euler began the general theory. In 1782 he published a paper on a new type of magic square. The Euler Archive, E530 lists its details and translates the title as “Investigations on a new type of magic square”.
The 36 officers
That paper takes up what is known as the problem of the 36 officers. The Wikipedia article Mutually orthogonal Latin squares quotes Euler’s wording: 36 officers drawn from 6 different regiments are to be ranged in a square so that each line, horizontal and vertical, has 6 officers of different ranks and different regiments.
Put another way, the regiments form one Latin square and the ranks form another, and when the two are laid on top of each other, no regiment and rank pair appears twice. Two Latin squares that can be overlaid like this are called orthogonal.
Of order 3, it can be done:
1 2 3 A B C 1A 2B 3C
2 3 1 + C A B = 2C 3A 1B
3 1 2 B C A 3B 1C 2A
The right-hand table has all nine pairs of 1 to 3 and A to C, each once. Euler used Latin letters for one square and Greek letters for the other, which is why such a pair is also called a Graeco-Latin square.
The 36 officers problem asks for a Graeco-Latin square of order 6. Euler conjectured that none exists for any order that leaves a remainder of 2 when divided by 4, which includes 6. The Euler Archive notes that he gave many examples and argued this without a rigorous proof.
For order 6 he was right. Gaston Tarry confirmed in 1901, by a proof by exhaustion, that no such squares exist. For order 7 and above, the conjecture is false: Graeco-Latin squares exist for every order greater than 1 except 2 and 6.
Latin squares in experiments
Latin squares are used outside puzzles as well. The Latin square article says they are used in the design of agronomic research experiments to minimise experimental errors. Sets of mutually orthogonal Latin squares have also been used as error-correcting codes.
The third rule
Take the two rules of a Latin square, add a third rule for the boxes, and you have sudoku. At order 9 there are still more than 6.67×10²¹ finished grids. The rules themselves are in Sudoku Rules: What First-Timers Need to Know, and puzzles that add other rules are in Types of Sudoku.
About Sudoku365
Sudoku365 is a Sudoku app for iPhone, iPad and Android. It uses the classic 9×9 board. It has four difficulties, Easy, Medium, Hard and Expert, with 300 puzzles each, 1,200 in total. There is a Daily Challenge with one puzzle a day and a streak, and two people can play head to head or together over Bluetooth.
Turning notes on lets you write candidates in the cells. With “Remove numbers from notes” in the settings (on by default), placing a correct digit erases the same note from the related cells. Selecting a cell highlights its row, column and box, and every cell with the same digit.
The app is free with ads, and a one-time Remove Ads purchase turns them off. Ideas for keeping a daily habit on your own are in Sudoku365 Tips, and for your first puzzle, see Getting Started with Sudoku365.
Sudoku365Daily sudoku, alone or with twoSee the app →