Latin squares and the math behind Sudoku

Counting Sudoku grids turned out to be a serious computation: 6,670,903,752,021,072,936,960 valid grids exist, and 5,472,730,538 of them are essentially different once symmetries are taken into account. Those symmetries are the same moves this site uses to disguise a puzzle.

What is a Latin square?

A Latin square of order n is an n × n array of n different symbols in which every symbol occurs exactly once in every row and every column [1]. The symbols can be numbers, letters or colors, since nothing is calculated with them. A simple order-3 example uses the digits 1, 2 and 3 so that each row and each column holds all three. Latin squares turn up in several places: the Cayley table of a group is one, and statisticians use them to design experiments in which two sources of variation, such as soil and moisture in a field, must be balanced [2].

A Sudoku solution is a Latin square of order 9 that satisfies one further condition: each of the nine 3×3 boxes also contains every digit once [3][4]. That is the whole difference. It makes Sudoku grids much rarer than Latin squares, as the counts below show.

What was Euler’s part?

In 1782 Euler posed a puzzle about 36 officers: six regiments each supply six officers of six different ranks, and the question is whether they can be arranged in a 6×6 square so that every row and every column holds one officer of each regiment and one of each rank [1][5]. Euler used Latin letters for one property and Greek letters for the other, which is why a square that satisfies both conditions at once is called a Graeco-Latin square. Two Latin squares that combine in this way are called orthogonal. Euler could not find a solution to the 36 officers problem [1][5].

He suspected that such squares are impossible whenever the order has the form 4k + 2, which includes 6 [1]. For order 6 he was right: there is no pair of orthogonal Latin squares of that order. His wider conjecture, however, was later shown to be false for other orders of that form [5][6]. The 36 officers problem inspired Euler to a great deal of work on Latin and Graeco-Latin squares, including problems related to modern Sudoku [1].

A point on which the sources differ is where the name “Latin square” itself comes from. One textbook says the name comes from Euler’s terminology, since he used Latin letters [5]. Peter Cameron’s lecture slides on the history of Sudoku say the name was invented later by a statistician, as a shortened form of “Graeco-Latin square” [2]. This page does not settle the question, and it uses the name without crediting a coiner.

How many Sudoku grids are there?

In 2005 Bertram Felgenhauer and Frazer Jarvis counted the valid completed Sudoku grids by computer and found 6,670,903,752,021,072,936,960, about 6.67 × 10²¹ [3][8]. The number of Latin squares of order 9, reported in the same note as known, is 5,524,751,496,156,892,842,531,225,600, about 5.52 × 10²⁷ [7]. Dividing the second by the first shows that there are about 830,000 Latin squares of order 9 for every Sudoku grid. The box condition removes almost all of them.

A direct enumeration is out of reach, so Felgenhauer and Jarvis used symmetry to shrink the problem. Relabeling the digits multiplies the count by 9! = 362,880, so it is enough to fix the top-left box in a standard form and multiply at the end. They then used rearrangements that leave the number of completions unchanged to cut the possible top bands, the first three rows, from 36,288 to 416, and further steps left 174 to examine in full [8]. The note itself points out that Sudoku grids are special cases of Latin squares and that counting Latin squares is already a hard problem with no general formula [4].

What does “essentially different” mean?

Two grids are essentially the same if one can be turned into the other by a symmetry that keeps the puzzle’s rules intact. For classic Sudoku these symmetries are:

• relabeling the digits, which can be done in 9! ways;
• swapping the three bands of rows, and swapping the three stacks of columns;
• swapping rows within a band, and columns within a stack;
• transposing the grid, which exchanges rows and columns.

Counting the non-relabeling moves gives 6⁸ × 2 = 3,359,232 operations: 3! ways to order the bands and (3!)³ ways to order the rows inside them, the same for columns, and a factor of 2 for transposing. Together with relabeling, the group has 362,880 × 3,359,232 = 1,218,998,108,160 members, which is my own arithmetic from the figures above. Dividing the number of grids by this group order gives about 5,472,447,994, close to the exact figure. The exact count is 5,472,730,538, found by Ed Russell and Frazer Jarvis, and it is slightly larger because a few grids are unchanged by some of the moves, which a counting method known as Burnside’s lemma handles properly [3][9]. A rough division is only a consistency check, and the published figure is the one to cite.

Why does this matter for puzzle generation?

Those same moves are how this site gives one stored puzzle many faces. When a classic puzzle is served, the game relabels the digits, swaps bands and stacks, swaps rows and columns within them, and sometimes transposes the grid. Each of these keeps the puzzle valid, keeps its single solution, keeps the number of clues and, as the unit tests confirm, keeps its difficulty grade. The pool therefore behaves like a larger one, as described in how puzzles are generated and verified unique. The variants allow fewer moves: boards with diagonals, windows or knight’s-move rules cannot swap rows freely, so they only relabel digits, and killer puzzles cannot relabel digits because their cage sums depend on them.

The disguise has a limit. A transformed puzzle is the same puzzle underneath, so it adds variety in appearance and not in logic. The size of the symmetry group is exactly why a pool of a thousand puzzles can look like far more.

Is solving Sudoku hard in general?

Solving ordinary 9×9 puzzles is fast for a computer. The general problem on larger boards, with n² × n² grids and n × n boxes, is known to be NP-complete, which means no efficient general method is known and the work can grow explosively with the board size [3]. A Sudoku can also be recast as a graph coloring problem, in which each cell is a vertex joined to every cell that sees it, and the aim is to complete a partial coloring with nine colors [3]. This is why the 16×16 board on this site relies on stored solutions and offline generation, and not on a search in the browser. The TypeScript solver tutorial shows the search method for the 9×9 case.

Where to go next

For the number of puzzles, as opposed to grids, and the proof that no puzzle has fewer than 17 clues, read how many Sudoku puzzles exist and the 17-clue result. For the story of the puzzle itself, see the history of Sudoku. The history hub lists all four pages, and the home page has the game.

Sources

1. “The 36 officers problem.” Plus Magazine, Millennium Mathematics Project, University of Cambridge. https://plus.maths.org/36-officers-problem. Accessed 22 October 2026.
2. Peter J. Cameron. “Sudoku – an alternative history.” Lecture slides, Queen Mary University of London, 2008 or later, date not shown. https://webspace.maths.qmul.ac.uk/p.j.cameron/slides/beamer/sudoku31.pdf. Accessed 22 October 2026.
3. “Sudoku.” Wikipedia. https://en.wikipedia.org/wiki/Sudoku. Accessed 22 October 2026. The article cites A. D. Keedwell, “Two remarks about Sudoku squares”, The Mathematical Gazette 90 (2006), for the Latin-square property, and the OEIS sequences A107739 and A109741 for the counts.
4. Bertram Felgenhauer and Frazer Jarvis. “Enumerating possible Sudoku grids.” 20 June 2005. Read through a copy at https://www.scribd.com/doc/94832755/sudoku. Accessed 22 October 2026.
5. “Mutually Orthogonal Latin Squares (MOLS).” In Combinatorics (Morris), LibreTexts. LibreTexts page. Accessed 22 October 2026.
6. Dominic Klyve and Lee Stemkoski. “Graeco-Latin Squares and a Mistaken Conjecture of Euler.” The College Mathematics Journal, 2006. https://www.math.uci.edu/~brusso/klyveStemkoskiCollMathJ2006.pdf. Accessed 22 October 2026.
7. “Improbable Research: 5524751496156892842531225600 on the road to Sudoku.” 7 September 2007. https://improbable.com/2007/09/07/5524751496156892842531225600-on-the-road-to-sudoku/. Accessed 22 October 2026. It quotes the Felgenhauer and Jarvis note.
8. “The Math Behind Sudoku.” Math Explorer’s Club, Cornell University, 2009. https://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html. Accessed 22 October 2026.
9. Ed Russell and Frazer Jarvis. “There are 5472730538 essentially different Sudoku grids.” Reported through source 3 and a French-language Q&A page quoting its group-averaging step. Not opened directly.