![]() ![]() Considering all possible cases of this left Felgenhauer and Jarvis with 174 out of the 416 first bands with which to proceed. As an example, look at the numbers 8 and 9 in the sixth and ninth columns of the above example. This is because each pair lies in the same column, and swapping both at once keeps the One Rule satisfied for the rows involved as well. We call two of these possibilities the pure top rows: when the numbers in one column with a in the i th row and b in the j th row, and the same pair in a different column with b in the i th row and a in the j th row, then swapping the places of a and b in each pair will result in a band that has the same number of grid completions as the original. Hint: There are ten ways of doing this so that swapping B2 and B3 in these ten ways give you ten more ways, for a total of twenty. So only the numbers 4, 5, 6, 7, 8, and 9 from the second and third rows of B1 can be used in the first row in B2 and B3.Įxercise: List all the possible ways of filling in the first rows in B2 and B3, up to reordering of the digits in each block. Since 1, 2, and 3 occur in the first row in B1, these numbers cannot occur in the rest of the row. We consider the ways to fill in the first rows in B2 and B3. The total number of valid Sudoku grids will be N 1×9!, so N 1=N/9!. Now we can calculate how many valid grid completions this particular B1 has: call it N 1. So the first simplifying assumption we can make is that B1 is filled in with the numbers 1, 2, 3. Starting with a valid B1 block, we can obtain any other valid B1 block by re-labeling, or permuting, the numbers. We are essentially computing the number of permutations of 9 symbols: how many ways we can arrange 9 symbols into 9 places, or how many ways we can order 9 things. For each of these 8 options, there are 7 left for the third cell. For each of these 9 options there are 8 options remaining for second cell. How many ways are there to fill B1 in a valid way? Since there are 9 symbols that can fill up B1, one in each cell, there are 9 options for the first cell. First we label the blocks of the grid as follows: We call the number of distinct Sudoku grids N. A cell in the i th row and j th column is said to be in (i,j) position. To keep our language standard, we call the three rows of blocks the bands of the grid and the three columns of blocks the stacks. ![]() The Math Behind Sudoku Counting SolutionsĪn interesting question to ask is how many ways can a 9 by 9 Sudoku grid be filled so that it satisfies the One Rule? In other words, how many distinct Sudoku solutions are there? We describe the method used to calculate this number by Bertram Felgenhauer and Frazer Jarvis in early 2006.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |