How Many Sudoku Grids Are There?

In my last post, Every Sudoku Has One Answer, I wrote about the 2012 result that a sudoku needs at least 17 clues. Along the way I mentioned two numbers without explaining them: there are about 6.67×10²¹ completed grids, and about 5.47 billion essentially different ones.
In this post I look at those two numbers more closely. How were they counted, and what does “essentially different” mean?
What is being counted
What we count here is not puzzles but answer grids, grids where every cell is filled. The question is how many grids have the digits 1 to 9 exactly once in every row, every column and every 3×3 box.
There are far more puzzles than answer grids, because from one answer grid you can make many puzzles with a unique solution by leaving different clues. Puzzles are much harder to count, and I leave them aside here.
Start with a small sudoku
Jumping straight to 9×9 is overwhelming, so let us start with a 4×4 sudoku. It uses the digits 1 to 4, and no row, column or 2×2 box may repeat a digit.
A 4×4 sudoku has only 288 completed grids. The number is listed in OEIS A107739, the online encyclopedia of integer sequences. With 288, you could write them all out with paper and pencil if you were patient.
9×9: about 6.67×10²¹
At 9×9 everything changes. The number of completed grids is
6,670,903,752,021,072,936,960
That is about 6.67 sextillion. Bertram Felgenhauer and Frazer Jarvis, a mathematician at the University of Sheffield, calculated it and published it in 2005. The English Wikipedia article Mathematics of Sudoku gives the same number.
They did not build every grid and count them one by one. The outline of the idea goes like this.
The top-left box can hold the nine digits in 9×8×7×…×1 = 362,880 orders. But whichever order it holds, the number of ways to fill the rest is the same, because you can rename the digits to turn any order into 1 2 3 / 4 5 6 / 7 8 9. So you can fix the top-left box as 1 2 3 / 4 5 6 / 7 8 9, count the ways to fill the rest, and multiply by 362,880 at the end.
With the top-left box fixed, there are 18,383,222,420,692,992 ways to fill the grid. Felgenhauer and Jarvis grouped the possible top three rows, the band that contains the top-left box, into 44 classes whose remaining fillings count the same, and then had a computer count the fillings for each class. It is not something you can check by hand, but it is a carefully built case analysis that avoids missing or double counting any grid.
How big is that?
6.67×10²¹ is too large to feel.
Suppose you looked at one completed grid every second, without sleeping. Seeing them all would take about 211 trillion years. The universe is said to be about 13.8 billion years old, so that is roughly 15,000 times its age.
What “essentially different” means
Many of these grids are close relatives. If you take a completed grid and do any of the following, it still follows the rules.
- Relabel the digits. For example, change every 1 into a 5 and every 5 into a 1. There are 362,880 ways to relabel nine digits.
- Swap rows within a band. Reordering the top three rows does not change what each box contains, so the rules still hold.
- Swap whole bands. Exchange the top three rows with the bottom three rows as a block.
- Do the same with columns: swap columns within a vertical stack, or swap whole stacks.
- Reflect across the diagonal. Use the line from top left to bottom right as a mirror, so rows become columns.
Rotations and mirror images can be made by combining these. A 90 degree rotation, for example, is a reflection across the diagonal followed by reversing the order of the columns.
Combining the row and column swaps with the reflection, one grid can turn into as many as 3,359,232 grids. Adding relabelling, the total is about 1.22 trillion.
Counting grids that can be turned into each other by these moves as the same grid gives the number of essentially different grids. If two grids differ only in the names of the digits or the order of some rows, they share the same skeleton as a puzzle.
About 5.5 billion essentially different grids
The number of essentially different grids is
5,472,730,538
Ed Russell and Frazer Jarvis calculated it in 2005 and 2006.
You might expect to get this by dividing 6.67×10²¹ by 1.22 trillion. If you do, you get about 5,472,448,000, a little less than the true value. The gap exists because a small number of grids are symmetric: some move brings them back to exactly the same grid, so they do not spread out into 1.22 trillion different grids. Russell and Jarvis corrected for this with a theorem known as Burnside’s lemma to get the exact count.
At one grid per second, 5.5 billion grids would take about 173 years to see. Compared with 15,000 times the age of the universe, that is almost within human reach. The proof in my last post, that no 16-clue sudoku exists, works by checking these 5.5 billion grids one at a time. With all 6.67×10²¹, even a computer could not have finished.
How this differs from Latin squares
As I wrote in Sudoku vs Nanpure, a completed sudoku grid is a kind of Latin square. A Latin square only asks that no digit repeats in a row or column. Sudoku adds the 3×3 box rule, so sudoku grids are the Latin squares that also pass that extra test. Even so, 6.67×10²¹ of them remain.
1,200 puzzles and 6.67×10²¹ grids
Sudoku365 has 1,200 puzzles, 300 in each of four difficulties. At one a day, that is about three years and three months.
Next to the number of answer grids, though, 1,200 is too small to compare. Nobody needs to worry about sudoku running out any time soon.
The app also has a Daily Challenge, the same puzzle for everyone in the world each day. If you want to start with techniques, see the first techniques beginners learn. If you are curious about what makes one puzzle harder than another, see What Makes a Sudoku Easy or Hard?
The app is free with ads, and a one-time Remove Ads purchase turns them off. For your first puzzle, see Getting Started with Sudoku365.
Sudoku365Daily sudoku, alone or with twoSee the app →