What Is The Arithmetic Behind The Sudoku Blank Grid?

Question

Last Updated on December 2, 2020 by Ephraim Iyodo

Sudoku Blank Grid is used in the Symmetry of Sudoku,it entails row and columns of  4×4,16×16 and more with small and variant grids.

Sudoku puzzles can be studied mathematically to answer questions such as “How many full Sudoku grids?”, “What is the minimum number of hints in a real puzzle?” and “How can Sudoku grids be symmetric?” by using combinatorial and group theories.

The main results are that for classic Sudoku, the number of completed grids is 6,670,903,752,021,072,936,960 (6.67×1021), which, while retaining the validity of the transformation reduces to 5,472,730,538 significantly different groups.

There are 26 types of symmetry, but they can be found only in about 0.005% of all filled grids.

A puzzle with a unique solution must have at least 17 solutions, and for each solved lattice there are no more than 21 solutions. The biggest minimum found puzzle has 40 clues.

Similar results are known for variants and smaller grids. Accurate results are not known for Sudokus more than the classical 9×9 grid, although there are estimates that are considered to be fairly accurate.

Calculation Solutions To Sudoku

An interesting question is, how many ways can a 9 by 9 Sudoku grid be filled to satisfy the Single Rule?

In other words, how many different Sudoku solutions exist? We describe the method used by Bertram Felgenhauer and Fraser Jarvis in early 2006 to calculate this number.

To maintain the standard of our language, we call three rows of blocks strips of a grid and three columns of blocks stacks. A cell in this row and the j-column is considered to be at (i,j).

We call the number of individual grids Sudoku N. First, we call the grid blocks as follows:

How many ways are there to fill B1 in a valid way? Since there are 9 characters that can fill B1, one in each cell, that is 9 options for the first cell.

For each of these 9 options, there are 8 options for the second cell. For each of these 8 options, there are 7 left for the third cell.

Basically, we calculate the number of permutations of 9 characters: how many ways we can place 9 characters in 9 places, or how many ways we can order 9 things.

There are 9 ways to fill in B1. Starting with a valid B1 block, we can get any other valid B1 block by re-marking or rearranging numbers.

So, the first simplifying assumption we can make is that B1 is filled with numbers 1, 2, 3, …, 9 in order, as shown below.

Now we can calculate how many actual grid endings this particular B1 has: let us call it N1. The total number of actual Sudoku grids is N1×9!, so N1=N/9!…

Let’s consider the ways to fill the first rows in B2 and B3. Since 1, 2 and 3 occur in the first row in B1, these numbers can not occur in the other rows.

Therefore, only the numbers 4, 5, 6, 7, 8 and 9 from the second and third rows of B1 can meet in the first row in B2 and B3.

List all possible ways to fill the first rows in B2 and B3, up to rearranging the numbers in each block. Tip: There are ten ways to do this so that the exchange of B2 and B3 these ten ways gave you ten more ways, a total of twenty.

We call two of these possibilities pure top lines: when numbers {4,5,6}, as in the second row of B1, are stored together in B2, and numbers {7,8,9}, as in the third row of B1, are stored together in B3, and a changed version of this.

The other possibilities are mixed top lines, as they mix the sets {4,5,6} and {7,8,9} when used to fill the first lines of B2 and B3.

Given these twenty possibilities for the first line of the grid (up to rearranging the numbers in each block), we can figure out how to fill the first line.

Think about how you can complete the first band starting with the pure top row 1,2,3;{4,5,6};{7,8,9}.

(Note: We are writing a,b,c to denote an ordered triple of numbers and {a,b,c} to denote them in any order.)

How many total possibilities are there, counting different number orderings within each row in B2 and B3? Is this number the same as for the other pure top row, 1,2,3;{7,8,9};{4,5,6}?

Remember, we want to keep B1 fixed because we’ve already accounted for the number of grids that can be obtained by relabeling the nine digits in it.

It turns out there are (3!)6 ways to complete the first band staring with the pure top row 1,2,3;{4,5,6};{7,8,9}.

This is because we are forced to put {7,8,9};{1,2,3} in the second row in B2 and B3 and {1,2,3};{4,5,6} in the third row, and then we may reorder the three digits in each of the six rows of B2 and B3 to get all the configurations.

The answer is the same for the other pure top row, since in this case all we’ve done is swapped B2 with B3.

The cases of the mixed top rows are more complicated. Let’s consider the top row 1,2,3;{4,6,8};{5,7,9}. This can be completed to the first band as in the following picture, where a, b, and c are the numbers 1, 2, 3 in any order.

After selecting a, b and c are the two remaining numbers in any order, as they are in the same row.

Since there are three options for a, and three digits in each of the six sets in B2 and B3 can be skipped to get different valid front pages, the total number of configurations in this case is 3×(3!)6.

You can similarly work through each of the remaining seventeen front row cases to get the same number.

Now we have the number of possible front pages defined by B1: this is 2×(3!)6+18×3×(3!)6=2612736, where the first part of the sum is the number of first page completions from the net top rows and the second is the number of first page completions from the mixed top rows.

Instead of calculating how many front page completions of each of these 2612736 features, Felgenhauer and Jarvis determined which front pages have the same number of first page completions from the top blank.

This analysis reduces the number of front pages to be taken into account when calculating.

Here are some operations that leave the number of endings of the first range grid unchanged: remarking the numbers, listening to any of the blocks in the first range, listening to the columns in any block and listening to the three rows of the range. With any of these B1 changes, we can re-mark the numbers to restore its standard form.

Arranging B1, B2 and B3 keeps the number of grid endings, because if we start with any actual Sudoku grid, the only way to keep it real is to mark B4, B5, B6 and B7, B8, B9 respectively so that the stacks remain the same.

In other words, each actual front-page grid termination gives exactly one actual front-page grid termination, i.e. any B1, B2, B3 permutation.
Make sure that when you change B2 to B3 in the next Sudoko grid, the only way to keep the grid valid is to change B5 to B6 and B7 to B8. This will keep the stacks the same, although their location has changed.

If you have a valid Sudoku grid and you are skipping columns in any of B1, B2 and B3, what would you have to do with the columns of the rest of the Sudoku grid to keep it valid? For example, if you changed columns 1 and 2 of B2 on the above grid, how would you fix the resulting grid so that it satisfies the One Rule?

The last exercise tells us that each filling of the front row grid gives a unique filling of the front row grid with columns skipped inside the blocks.

Such considerations allow us to reduce the number of specific front pages to be taken into account when counting.

Following Felgenhauer and Jarvis, we scroll through the B2 and B3 columns so that the top row entries of each column are in ascending order, and then swap B2 and B3 if necessary so that the first B2 entry is smaller than the B3 entry.

This is called lexicographical abbreviation.

Since each of the two blocks has 6 rearrangements of columns and two ways of rearranging blocks, the lexicographical shorthand tells us that, given the first page, there are 62×2=72 other front pages with the same number of grid endings.

So now we only have 2612736/72=36288 front pages to consider.

For each of these possibilities let’s look at the rearrangements of all three top blocks: there are 6. For each of them there are 63 rearrangements of columns within each block.

After performing these operations, we re-mark to return B1 to its standard form.

Similarly, we can override the top three lines of the group and re-mark to return B1 to a standard form. These operations save the number of front row grid completions.

Felgenhauer and Jarvis used a computer program to determine that these operations reduce the number of front pages to be considered from 36288 to only 416.

Let’s consider this first group.

Perform various operations on it that save its number of grid endings. You can start with the following: Exchange the first and second row. Re-mark it so that B1 is in its standard form. Lexicographically reduce this grid.

The main thing is that the group you started with and the other group you finished with have the same number of completions up to the full Sudoku grid.

Thus, instead of calculating the number of endings of the grid for each of these groups, we can only calculate it for one of them.

There are more steps that reduce the number of grids to consider. If we have a pair of digits {a,b} in one column with a in a ith row and b in a jth row, and the same pair in another column with b in a ith row and a in a jth row, each pair will have a band with the same number of grid endings as the original.

This is because each pair lies in the same column, and when both are changed at the same time, a single rule is saved, which also satisfies the rows involved.

As an example, look at numbers 8 and 9 in the sixth and ninth columns of the above example. Consider all possible cases of this left Felgenhauer and Jarvis with 174 of the first 416 groups to continue with.

They have also considered other configurations of the same set of numbers lying in two different columns or rows, which can be omitted inside their columns or rows, leaving the number of grid endings invariant.

This reduced the number of front pages to 71, and the search for each of these 71 cases made it clear to them that there are actually only 44 front pages whose number of grid completions to be found.

Each of these 44 bands has the same number of endings to the full grid.

Let C denote one of these 44 stripes. Then you can calculate the number of ways that C can complete to the full Sudoku grid: call it nc.

We also need the number of mC front pages that share this number of nC endings of the grid. Then, the total number of Sudoku grids is just N=ΣCmCnC, or the sum of mCnC for all 44 stripes.

Felgenhauer and Jarvis wrote a computer program to do the final calculations.

They calculated the number of N1 valid completions with B1 in a standard form, starting with 44 lanes. Then they multiplied this number by 9! to get an answer.

They found that the number of possible 9 by 9 Sudoku grids is N=6670903752021072936960, which is about 6.671×1021.

 

Article And Image Credit:

http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html

 

 

0
Ephraim Iyodo 11 months 0 Answers 1575 views 0

Leave an answer

Brilliantly Safe & Student-Centered Learning Platform 2021