Various symmetry arguments prove that many of these grids are equivalent. This reduces the number that need to be checked to a mere 5, , , So McGuire and co wrote a program called Checker to check each one of these grids for a clue solution.
But the process of checking a single grid is itself tricky. One way to do it is to examine every possible subset of 16 clues to see if any of them lead to a unique solution. Once again, a little mathematics come in handy. McGuire and co used some clever reasoning to show that certain subsets are equivalent to many others and this dramatically reduces the number of subsets that need to be checked. Nevertheless, the resulting calculation is still a monster.
The Dublin team say it took 7. They started in January and finished in December. The whole exercise may sound like a bit of mathematical fun but this kind of problem solving has many important applications. McGuire and co say the problem of Sudoku grid checking is formally equivalent to problems in gene expression analysis and in computer network and software testing. Ref: arxiv. So if there are no uniquely solvable clue grids, there cannot be any grids with fewer clues that are uniquely solvable.
These operations preserve the number of grid completions of a first band. Felgenhauer and Jarvis used a computer program to determine that these operations reduce the number of first bands to be considered from to just Exercise: Consider the given first band.
Perform various operations on it that preserve its number of grid completions. You can start with the following: Exchange the first and second row. Relabel so that B1 is in standard form. Lexicographically reduce this grid. The main point is that the band you started with and the different band you ended with have the same number of completions to a full Sudoku grid.
So instead of calculating the number of grid completions for each of these bands, we can count it for just one of them. There are more steps that reduce the number of grids to be considered. 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.
As an example, look at the numbers 8 and 9 in the sixth and ninth columns of the above example. Considering all possible cases of this left Felgenhauer and Jarvis with out of the first bands with which to proceed.
They also considered other configurations of the same set of digits lying in two different columns or rows, which can be permuted within their columns or rows leaving the number of grid completions invariant. This reduced the number of first bands to consider to 71, and searching through each of these 71 cases let them know that there are actually only 44 first bands whose number of grid completions need to be found.
Each of these 44 bands has the same number of completions to a full grid. Let C stand for one of these 44 bands. Then the number of ways that C can be completed to a full Sudoku grid can be calculated: call it n c.
We also need the number m C of first bands that share this number n C of grid completions. Felgenhauer and Jarvis wrote a computer program to carry out the final calculations. They computed the number N 1 of valid completions with B1 in standard form, starting with the 44 bands.
Then they multiplied this number by 9! Contents Home 1. Introduction to Sudoku 2. Solving Strategy 3. Counting Solutions 4. The answer to this problem is While a concrete mathematical proof has not been found, mathematicians have analyzed every possible Sudoku puzzle with 16 clues through brute force and found that none have a unique solution. For example, if every 1, 2, and 3 digits in a grid was given, which would mean there are 27 clues to start with, the other digits could still be used interchangeably.
This would give rise to multiple solutions. Variants like Thermo Sudoku where there are different types of clues or Chess Sudoku where there are different types of constraints complicate matters significantly.
0コメント