|
How many different Sudoku solutions are there? Lots! but perhaps fewer than you think. Consider a solved Sudoku puzzle:
But remember what I pointed out on the previous page: the integers used in Soduku are just arbitrary symbols. Hence, they can easily be interchanged! Thus, for instance I could turn every 3 into a 7, and every 7 into a 3. The result would still be a solved puzzle. After all, in a solved puzzle, every row, column, and box has in it exactly one 3 and one 7. After interchanging those symbols, every row, column, and box would still have in it exactly one 7 and one 3, and hence we would still have a valid solution. Note, though, that this would not be a solution to the same original puzzle - it would be a solution to the original puzzle with 3 and 7 interchanged. But obviously, we could carry this futher. We could do any number of interchanges of any number pairs, and we would still have a solution. In mathematical terms, we can permute the symbols, and still have a valid solution. This means that any Sudoku solution has an enormous number of essentially equivalent solutions that can be obtained by simply permuting the integers. And there are nine factorial possible permutations! "Nine factorial" is written "9!" in mathematical notation, and it has the value: So for any Sudoku solution, there are over a third of a million solutions that are essentially equivalent - the only difference is a permutation of the integers. Is there any way of determining if two Sudoku solutions are simply permutations of one another? One way is to "normalize" the two solutions, by transforming them so that they both have the numbers 1 through 9 across the top row, in order. If the result is the same in both cases, then the original two solutions are simply permutations of each other. Consider the example given above. List the top row of numbers, and then list the numbers 1 through 9 directly underneath them: 1 2 3 4 5 6 7 8 9 This specifies a particular permutation: convert each of the numbers to the one below it. That is, change every 3 to 1, every 7 to 2, and so on. Note that 4 happens to stay unchanged, and 2 and 7 are swapped, but the other changes are not simple exchanges. Now apply that permutation to the grid:
The result? A solution that is fundamentally equivalent to the original one, but with a top row that contains the integers 1 through 9 in sequential order. If you read on, I'll provide an Excel spreadsheet that will automatically normalize a Sudoku solution for you, based on ordering the first row, as shown above. But wait, there's more! A little thought will reveal that in addition to permuting the symbols, there are other transformations that can be applied to a solution which will generate another valid solution. For example, columns 1 through 3 can be permuted freely, yielding another solution that is essentially equivalent. There are only six possible permutations of three columns: if the first row reads 123, these are 123 (no change), 132, 213, 231, 312, and 321. Permuting sets of columns that don't cross box boundaries, a little thought will show, doesn't destroy the basic properties of a solution: exactly one of each number in each row, column, and box. Hence, you can permute columns 1 through 3, columns 4 through 6, and columns 7 through 9. But you can't permute sets of columns that cross box boundaries, such as columns 2 through 4. That operation would destroy the property of having exactly one of each number in each 3 X 3 box. Obviously, you can also permute sets of rows that don't cross box boundaries: rows 1 through 3, rows 4 through 6, and rows 7 through 9. Six permutations each, for each of the above sets of three rows and columns, applied in a fixed order, yield 6 X 6 X 6 X 6 X 6 X 6 = 46,656 different, but in some way equivalent, solutions! So by permuting the symbols, and then further permuting rows and columns, a single Sudoku solution can generate a total of 362,880 X 46,656 = 16,930,529,280 essentially equivalent solutions! It does seem clear to me that the row permutations and the column permutations don't interact. They can be said to be "orthogonal", just as the rows and columns themselves are orthogonal. That is, it doesn't matter what order you do them in - the results are the same. Permuting the columns of a box leaves the same set of numbers in each row - it just changes their order. And that row then retains its identity even if it is moved by a row permutation. It doesn't matter which is done first. But wait, there's more! Although we can't swap rows across box boundaries, we can swap triplets of rows. Thus, for example, we can swap (rows 1, 2, and 3 together) with (rows 4, 5, and 6 together). Clearly no rows and boxes are disturbed, and all that happens to the columns is that the order of the numbers is changed, but there is still exactly one of each number in each column. There are obviously six distinct permutations of these row triplets, just as there were six permutations of three numbers. And, of course, we can just as well permute the column triplets. So that makes another 6 X 6 = 36 transformations we can apply to a solution, for a total of 16,930,529,280 X 36 = 609,499,054,080 essentially equivalent solutions! But wait, there's more! We can rotate or flip the solution, and we'll still have a valid solution. We can rotate it clockwise zero times, once, twice, or three times (four times brings it back to the start, the same as zero times). Or we can rotate it around a vertical axis, a horizontal axis, or around each of the two diagonals. That's eight possibilities. This is the well-known "group of symmetries of the square", where "group" is used in its mathematical, linear-algebraic sense. So that seems to give us another 8 transformations we can apply to a solution, and for over four years, this page claimed that gave a total of 609,499,054,080 X 8 = 4,875,992,432,640 essentially equivalent solutions. However, on February 22, 2011, I received a correction via e-mail from Kaspar Richner, writing in German. He correctly noted that a 180 degree rotation, and the mirror-image "flips", can also be obtained by the row permutations considered earlier. That leaves only the 90 degree rotation that has not already been considered, and once it has been done, the 270 degree rotation can be gotten with a 90 degree rotation followed by a flip. Thus these symmetries of the square really only add a factor of 2 to the permutations we have already considered, for a total of 609,499,054,080 X 2 = 1,218,998,108,160 essentially equivalent solutions. Mr. Richner noted that, "This figure is slightly higher than the value that you get when you divide Jarvis and Felgenhauer's total number of valid grid solutions (6,670,903,752,021,072,936,960) by Jarvis' and Russell's number of essentially different grids (5,472,730,538). The difference between Jarvis's calculation and mine is probably due to the fact that there are other convergences between the permutations of rows and columns on the one hand and permutations of the numbers on the other hand." See further below on this page for a bit more discussion of the numbers he mentioned. My thanks to Mr. Richner for pointing out my earlier error (and it's good to know that somebody is actually reading this stuff). But wait, there's more! Order now, and I'll throw in a free set of Ginsu knives ... Oops, wrong web page. So unless you can think of some other transformations I've missed, a given Sudoku solution can be transformed into only 1,218,998,108,160 essentially equivalent solutions (still a pretty big number). One slight glitch: I can't prove those 1,218,998,108,160 solutions are in fact all different. It's possible that two different paths converge onto identical solutions. Here's an Excel spreadsheet into which you can enter a solved Sudoku puzzle. I wrote it to play with some of these transformations, but it doesn't apply all of them. It will "normalize" the solution for you by applying some of the transformations mentioned above, as follows: 1. It will interchange numbers such that the first row is in ascending order. 2. It then sorts the first column of rows 1-3, the first column of rows 4-6, and the first column of rows 7-9 in ascending order, by permuting the rows within these sets as needed. This is done in three steps: possibly swap the top two rows of each triplet, then possibly swap the last two, and then possibly swap the first two again. It doesn't permute the columns, because that would destroy the ordering of the top row. 3. Finally, it will swap the middle three rows with the bottom three rows, if needed, to make the leftmost entry of row 4 less than the leftmost entry of row 7. To download this spreadsheet in most Windows systems, right-click on the link just below, and select “Save target as ...”. When I first played with normalization, I wondered if there might be, in some sense, only ONE Sudoku solution, with all other solutions obtainable from it via permutations of the symbols, and permutations of the rows and columns in some order. I gradually came to conjecture that to NOT be the case, and this is supported by the Wikipedia entry for Sudoku, Mathematics of Sudoku section, which says (as of 9/1/05), “... the number of valid Sudoku solution grids for the standard 9X9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960. This number is equal to 9! X 722 X 27 X 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions.” I don't know exactly what “symmetries” were taken into account. Here's a very orderly solution I generated by starting with the numbers in order in the upper-left box, and then permuting the row triplets going across, and the column triplets going down:
|