A first look at counting Sudokus

How many (complete!) 9x9 grids are there, i.e. in how many different ways can one fill an empty 9x9 Sudoku grid in while following the Sudoku rules?

Let's do a rough estimate. Suppose we have an empty grid and fill it in, making sure that each of the numbers from 1 to 9 appears exactly once in each row, column and 3x3 box with thick margins.

Each cell must contain a number between 1 and 9, i.e. there are up to 9 different possibilities. In most cases there will be significantly fewer possibilities, since it is not allowed to have two copies of the same number in any row, column, or 3x3 box with a thick rim. But let us ignore this detail and simply state that for each cell, there are no more than 9 ways of filling it in.

Now imagine filling the grid in, starting with the top left cell and then proceeding row by row, from left to right. Filling in just the first cell, we have 9 choices. Filling in the second choices, we have no more than 9 choices. So for each of the possibilities that we could choose when filling in the first cell, there were no more than 9 possibilities for filling in the second cell. In total, that gives us at most 9x9 different ways of filling in the first two cells. For the third cell, we again have no more than 9 different ways of filling it in. So for each of the 9x9 combinations we could choose for the first two cells, there are at most 9 ways of filling in the third cell. Therefore there are at most 9x9x9 ways of filling in the first three cells.

We can continue the argument for all other cells, observing that there are at most 981 ways of filling in the first n cells. There are 9x9 cells on our Sudoku grid, thus no more than 981 different complete Sudoku grids of size 9x9. A good calculator will tell you that 981  is approximately 2x1077, or, in words, two hundred quattuorvigintillion. That's not too far from the number of atoms in the universe (http://en.wikipedia.org/wiki/Observable_universe#Matter_content).

Let's put our result into context: we have only shown that there are no more than complete 981 Sudoku grids of size 9x9. In reality there could be many fewer. Mathematicians call an estimate like ours an “upper bound”: we have not computed the actual number of complete 9x9 Sudoku grids, but we have shown that there are no more than 981.

Improved Count

To understand the idea for completing activity 1 better, we could draw up a 9x9 table like the following one. Each entry of the table is no smaller than the number of of ways of filling in the corresponding cell on a Sudoku board if you fill in the board from left to right, top to bottom.

To estimate how many ways of filling in the board there can at most be, we multiply the maximal number of ways that there are of filling in each of the cells. It is now easy to see where the product (9x8x7x6x5x4x3x2x1)9 comes from.

Doing the previous activity, you were probably surprised to see that using the information that each row must contain each number from 1 to 9 exactly once improved our upper bound a lot. This was because once you have filled most of a row in, there is really very little choice left for completing the remaining cells in that row! For example, once you have completed the first 8 cells of the first row, there was only one number left that you are allowed to put into the 9th cell of the row. For that reason, there were exactly as many ways of filling in the first 8 cells of the top row as there were ways of filling in the entire top row. Your solution for activity 2 took this into account, while the original (very rough) estimate answering the question from the top of the page just used that the total number of possibilities could not increase by a factor larger than 9.

Clever Counting

We are now pretty comfortable using the rules of Sudoku to eliminate ways of filling in a Sudoku grid. Let’s compute one more upper bound, it will be significantly better than anything we have done so far. Below is a 9x9 table. The number in each cell is the number of ways in which I can fill in that cell while making sure that each number from 1 to 9 occurs at most once in each row. We again proceed row by row, from left to right, top to bottom. Once I have filled in a cell, I have one choice less in the next cell along the row!

Here is another 9x9 table. The number in each cell is the number of ways in which I can fill in that cell while making sure that each number occurs at most once in each column. If there are already some numbers in a given column, then I have a smaller choice for the next cell in that column to fill in!

Here is another 9x9 table. The number in each cell is the number of ways in which I can fill in that cell while making sure that each number occurs at most once in each 3x3 box with a thick margin.

For each cell in the 9x9 Sudoku grid, we now have the number of ways of filling it in if we observe the rule about rows (table 1), the rule about columns (table 2), and the rule about 3x3 boxes (table 3). So how many ways of filling a given cell in are there really? Well, however many there are, there can’t be more than the number in the corresponding box of table 1, nor more than the number in the corresponding box of table 2, nor more than the number in the corresponding box of table 3! Let’s draw another table. In each cell, we will put the smallest number of the numbers of the corresponding cells in tables 1, 2 and 3. Here is the table with the smallest numbers:

Looking at the table, there are no more than 9 ways of filling in the first cell in the top row, and no more than 8 ways of filling in the second cell. So for each possibility for the first cell, there are no more than 8 ways of filling in the second cell. There are therefore at most 9x8=72 ways of filling in the first two cells. According to the table, there are no more than 7 choices for the third cell, thus no more than 9x8x7 ways of filling in the first three cells. Proceeding this way row by row, we end up multiplying all 81 entries of table 4. The product is about 1.5x1031, quite a bit better than our previous upper bound!

Brute-force counting

In 2005, Bertram Felgenhauer and Frazer Jarvis used a computer to calculate that the actual number of complete Sudoku grids is 6,670,903,752,021,072,936,960, that’s about 6.7x10^21. Their method is too involved to describe here, but if you know the programming language C++, I encourage you to read their 5-page paper. It’s available at www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf.

You might wonder why even our best upper bound was much bigger than the actual number of complete Sudoku grids. The answer is that for each cell, we only used the restrictions imposed by the condition on the row, or on the column, or on the 3x3 box. To get an exact count of all complete Sudoku puzzles, rather than just an upper bound, we would have had to proceed much more carefully. This is explored in the next activity.