The number of solutions you could fit into your weekend Sudoku is mind-boggling

greencolander/Shutterstock

Sudoku puzzles, in which a solver tries to fill in a grid with the numbers one through nine according to certain rules, are a fun diversion.
One question that might pop into your head while playing Sudoku is "how many puzzles are possible?"
In 2005, a computer scientist and a mathematician set out to answer that question.
Visit Business Insider’s homepage for more stories.

Sudoku can be a very chill and relaxing way to stretch your brain.

The incredibly popular logic puzzles are a great way to kill a few minutes of time on the subway, or make a nice accompaniment to a slow morning cup of coffee on a Saturday.

While playing through a Sudoku puzzle, the question of just how many of these puzzles are there may have popped into your head.

Fortunately, due to the power of math, you don’t need to wonder that any further: There are an eye-popping 6,670,903,752,021,072,936,960 possible solved Sudoku grids.

That is a ridiculously large number. Most numbers you’re likely to see in your day-to-day life don’t need seven commas to be written out.

Here’s how you get to that astronomical sum.

A Sudoku puzzle consists of a 9×9 grid of squares, broken up into a 3×3 grid of blocks made up of nine squares each. The goal of a puzzle is to fit the numbers 1 through 9 into each of the 81 squares of the grid so that each row, column, and block has exactly one of each number. The puzzle starts off with some of the squares already filled in with particular numbers, and it’s up to the solver to figure out how to fill in the rest of the squares to get to that end state.

Here’s what a solved Sudoku puzzle looks like. This one was taken from Sudoku.com:

Business Insider/Andy Kiersz, puzzle from Sudoku.com

Mathematicians love counting things. When confronted with a particular class of numerical or geometric object, like, say, Sudoku puzzles, a pretty basic question is "how many of these things are there?"

In a 2005 paper, computer scientist Bertram Felgenhauer and mathematician Frazer Jarvis set out to figure out how many possible valid, solved Sudoku puzzle grids, like the one above, exist.

As with many questions in combinatorics (the branch of math that concerns itself with counting objects that are put together following some set of rules — like Sudoku grids) the answer is an astonishingly large number: As mentioned above, there are over 6 sextillion possible Sudoku grids.

And also as with many questions in combinatorics, the process of getting that number is more complicated than one might first guess.

The absolute most basic approach to a problem like this would be a brute-force, trial-by-error strategy of just plugging in every possible combination of the numbers one through nine into every one of the 81 squares in our 9×9 Sudoku grid and seeing which combinations are valid solutions, with each digit showing up exactly once in each row, column, and block.

The obvious issue with this approach is that there are vastly too many possible combinations of this type to look at each and every one. Since there are 9 possibilities for each of our 81 squares, we end up with 9⁸¹ possible candidate grids to consider. Even a computer checking a trillion candidates per second would end up taking some 6 x 10⁵⁷ years — a period of time almost incomprehensibly longer than the age of the observable universe — to solve our problem in this brute force approach.

The key is to take advantage of the rules and properties of Sudoku to reduce the number of potential candidates we have to check to something actually attainable. Felgenhauer and Jarvis do this by looking at similarities and relationships between different Sudoku grids that let us quickly count entire families of grids at one time.

For example, if we have a valid Sudoku grid and simply relabel each number with one of the other numbers — say, take every 1 and replace it with a 5 and vice versa — we clearly end up with another valid Sudoku grid.

Felgenhauer and Jarvis flip this around and observe that we really only need to count Sudoku grids where the block in the top-left corner contains the numbers 1-9 in order:

Business Insider/Andy Kiersz

Any valid grid that works with that top-left block can be turned into a whole slew of other grids by just relabeling numbers, and conversely, any grid with a different top-left block can be turned into a grid like the one above with an appropriate relabeling.

So, for purposes of counting, we just need to concern ourselves with grids that have the ordered top-left corner above. Count all possible valid grids with this configuration, and then multiply by the number of ways we can permute the numbers one through nine and relabel our squares to get the total number of valid Sudoku grids.

(That number of ways to permute the top right block works out to 9!, read "9 factorial", or the product 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1, since we have 9 digits to choose from for the first square, leaving 8 choices for the second square, then removing those two leave 7 for the third square, and so on.)

Once we’ve fixed the top right block, Felgenhauer and Jarvis move over to the rest of the top row of blocks. They start by considering the very top row of squares. Since we have fixed the top row of the first block to be 1, 2, and 3, that leaves the other six numbers to be arranged.

But, once you choose which numbers make up the top row of the middle block, much of the rest of the top set of blocks falls into place. Say we have a 5, 6, and 7 in any order in that middle top row. That only leaves 4, 8, and 9 for the top row of the third block.

Then we can consider the second row of the middle block. There has to be an 8 and a 9 somewhere in that row, since they can’t be in the third row, since there is already an 8 and a 9 in the third row of the first block. Similarly, there has to be a 4 in the third row of the middle block, since there is already a 4 in the second row of the first block. The third block has some similar restraints on where the 5, 6, and 7 need to go, leaving 1, 2, and 3 to be put into place in the remaining blank squares:

Business Insider/Andy Kiersz

Each of the three numbers in the resulting six rows can be put in any order. By playing around with all the possible choices for the top row and following this kind of logic, Felgenhauer and Jarvis calculated that there are 2,612,736 possible ways to finish the top set of rows with our fixed upper left block.

They then used other similar tricks to look at similar grids. Swapping the middle block with the right block, for example, gives a very similar configuration, which means that we only have to consider half of our top row options.

Through several other permutations, like swapping columns within one of the blocks, they eventually managed to break the problem down into 306 classes of possible top block rows, with a good understanding of how many related top rows fall into each of those classes. The strategy then becomes to figure out how many valid grids are possible for each of those 306 classes, multiply by the size of the class, and add those up to get the total number of grids.

At that point, the number of remaining blank squares in the grid was small and constrained enough that a more brute-force approach to filling them in was viable on a computer. They ran such a program, and over the course of a few hours, were able to count up the total number of possible grids, getting the 6,670,903,752,021,072,936,960 total mentioned above.

Check out the full paper here»

NOW WATCH: 12 everyday phrases that you’re probably saying incorrectly