Almost-locked set analysis can be extended to grids, where itĪnd also to what I am calling almost-locked ranges. What I'm calling 3D Medusa analysis, includingĪnalysis. 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.The Sudoku Assistant uses several techniques to solve a Sudoku puzzle: 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.Īt 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. 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.
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. They then used other similar tricks to look at similar grids. 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. 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:Įach of the three numbers in the resulting six rows can be put in any order. 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. 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. Then we can consider the second row of the middle block. That only leaves 4, 8, and 9 for the top row of the third block. Say we have a 5, 6, and 7 in any order in that middle top row. 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.īut, 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. They start by considering the very top row of squares. Once we've fixed the top right block, Felgenhauer and Jarvis move over to the rest of the top row of blocks. (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.) 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.
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. Even a computer checking a trillion candidates per second would end up taking some 6 x 10 57 years - a period of time almost incomprehensibly longer than the age of the observable universe - to solve our problem in this brute force approach. Since there are 9 possibilities for each of our 81 squares, we end up with 9 81 possible candidate grids to consider. 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. 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 9x9 Sudoku grid and seeing which combinations are valid solutions, with each digit showing up exactly once in each row, column, and block. Read more: Any Rubik's Cube can be solved in 20 moves, but it took over 30 years for anyone to figure that out
0 kommentar(er)
