COD Summer Bridge Enrichment - 2011Sudoku
Definition:
A Sudoku is a 9 by 9 array of 9 symbols in which every row,
Typically, the symbols are the numbers 1,2,…,9, but any set of nine symbols will do.
Here’s a simple example with numerals can you describe the pattern here? Note that the two Sudokus below use the same pattern with different symbols:
An ennead is any group of nine things, which is all you need to make a Sudoku. The nine Egyptian deities of the Heliopolis, for example:
Here is a Sudoku using these 9 symbols:
To simplify matters, we can start by studying the mini-sudoku, which is an arrangement of 4 symbols in a 2 by 2 array of 2 by 2 arrays.
Are the two mini-Sudokus above equivalent, aside from the symbol sets? Why or why not?
How many entries can you remove and still have a unique solution?
How many mini-Sudokus are there?
To get started on answering this last question, note that we can create a new mini-Sudoku from an existing mini-Sudoku by · Swapping the first and second rows or swapping the third and fourth rows · Swapping the first and second columns or swapping the third and fourth columns · Reversing rows and columns (that’s called a transposition) · Relabeling entries
Let’s call these “the allowed operations.”
Examples of these are shown below, showing first the “original” miniSudoku and then new miniSudokus formed by swapping the first and second columns, the third and fourth columns, and so on: Can all min-Sudokus be produced this way? Given any mini-Sudoku, we can always relabel the entries to get a mini-Sudoku with the upper left square like so:
Then we can swap rows 3 and 4 and/or columns 3 and 4, as needed to produce a “4” in the 3rd row, 3rd column position: Now, whatever element goes in the 4th
row, 4th column position determines what all the other entries in
the mini-Sudoku must be: Try this with a few examples.
The above analysis shows that every miniSudoku can be transformed into one of three mini-Sudokus by the operations of swapping rows, swapping columns, transposing and relabeling (the allowed operations.) In this sense, every Sudoku is equivalent to one of three types.
But wait, there’s more! (…or less) … since the above
Transpose Relabel 2↔3
This shows that every mini-Sudoku can be transformed by “the allowed operations” to either or
Exercise: Fill each one in with its unique solution.
Michael Kreb, the CSLA math professor whose work this is based on, claims that these are not equivalent, in that, you can’t get from one to the other using “the allowed operations.”
Based on the above considerations, we can now count the number of mini-Sudokus. Start by noting there are 4321 = 24 ways to fill in the upper left square with the symbols 1,2,3,4. For each of these 24 possibilities, there are 43 ways to complete the diagonal and then only one way to fill in the remaining squares. Thus there are 24*12 = 288 mini-Sudokus in two equivalence classes. By contrast, Frazer Jarvis has shown there are 6,670,903,752,021,072,936,960 9 by 9 Sudokus of 5,472,730,538 essentially different Sudoku types. That ought to keep newspaper puzzle-maker stocked up for a while!
Given a particular mini-Sudoku, say, the one below, how can we tell which one it is equivalent to? That is, we seek an easy to compute property of the mini-Sudoku that is “invariant” for one type or the other. It turns out that the parity of the number of distinct entries along the main diagonal is such an invariant. Look at the elements along the main diagonal, as shaded below: There are three different entries (the 1 is repeated) so this has odd parity. By contrast, the two mini-Sudokus below have ever parity (2 and 4 distinct entries.) All mini-Sudokus with even parity are equivalent to one another and all mini-Sudokus with odd parity are equivalent to one another. Unfortunately, this method doesn’t work with regular 9 by 9 Sudokus.
Sudokus and Graph Coloring
Replace each of the sixteen squares of the mini-Sudoku with a dot, like so:
Dot’s nice! Now connect the dots if they’re part of the same row, column or block:
Now the dot for, say, first row, second column is connected with both dots to the right of it. To better see these overlapping lines segments, shift some of the dots and see the line segments like so: Now it looks kind of three-dimensional, huh? Krazy Kat’s kradle? Prof. Kreb then challenges you to color the dots with as few colors as possible so that no two dots with the same color are connected by a segment. Four colors are needed…which is obvious, if you think of these colors of just an alternate symbol set for the numbers, 1,2,3,4.
You can do a similar coloring for the regular 9 x 9 Sudoku I’m thinking that would require more crayolas.
Go to http://www.eddaardvark.co.uk/sudokusolver.html for a good introduction to
Sudoku solving strategies.
Sudoku Solving
Algorithm: 1. Start with the numerals 1,2,…,9
in each of the 81 squares: 2. Eliminate the symbols (numerals) in the same row, column and block to be consistent with the given numerals. For instance, you’re given that there is a one in the first row, fifth column so there can’t be any other 1’s in that row, column or block. After doing this for all the given numeral, you end up with this:
3. Search the rows, columns and
blocks for singletons: numbers
that appear only once in that row, column or block. Obviously, the given clues are singletons,
so we search for other singletons.
Count the number of times the number 2 appears in the first column: 4
times not a singleton. In fact, investigation shows that the first
three columns contain no singletons, other than the given clues. However, in the fourth column, 9 appears
only once, So the solution must contain a 9 in the fourth column, fifth row
(note that 9 is also a singleton for the middle block.) Thus we can eliminate all other 9’s from
the fifth row.
This has a domino effect of cascading consequences. Let (r,c) indicate the element in row r and column c. Then the consequences go like this: (8,2) = 7 so (6,2) = 8, which means (1,2) = 6 and (6,5) = 7. Now (1,2) = 6 means (1,1) = 2 and (5,2) = 4. In turn, (1,1) = 2 means (1,3) = 8 and we have this new, improved partial solution (new in blue):
4. Repeat the search for singletons and note the consequences for the rows, columns and blocks. For instance, (9,1) must be 4, since that’s a singleton for its row, its column and its block (so that’s without consequence) but (9,6) = 7 since it’s a singleton for that row and block and, as a consequence, (2,6) = 5 and so (7,2) = 1 and so on…everything falls into place pretty quickly at this point.
If a Sudoku is rated “easy” that likely means that no other logic is required than that of finding singletons and deducing the consequences for the rows, columns and blocks the singletons occupy. Here’s a more challenging Sudoku:\
Applying the second step of the algorithm for these givens yields (the given squares are blue):
We can immediately conclude that (6,7) = 1. The singletons are few, now. The entries (5,2) = 4 and (6,1) = 5 are singletons in their block. This causes the singleton (5,8) = 3 in the 5th row.
Also, (8,6) = 7 is a singleton in the 8th row making (9,6) = 3 a singleton in the 6th column.
Three more singletons: (4,6) = 5 in the 4th row, (6,4) = 6 in the 6th row, and (3,1) = 6 in row 3. But then the singletons dry up:
Let’s clean up the above array a bit so we can examine it carefully.
Using exclusive pairs
Look at column 2. In particular, cells (1,2) and (3,2), which contain, respectively, “379” and “279.” Since these are the only two cells in that column that contain either a 7 or a 9, one must be a 7 and the other must be a 9. We don’t know which is which, but we know neither is a 2 nor a 3. Let’s call such a pair an exclusive pair. Then (6,2) = (9,2) = “28” is another exclusive pair in the second column, which means that (8,2) = 3, since it can no longer be a 2. We update the partial solution like so:
There are no more
exclusive pairs at this point…though, in practice, this takes some close
inspection to ascertain (you need to look at 27 different groupings of 9
cells: 9 columns, 9 rows and 9 clocks.)
So we move onto step 6 in this algorithm: Guess and check with exclusive triples
The logical next phase would be the exclusive triple: three cells in particular group (row, column, block) that contain only three different numerals this would mean none of these three numerals could occur in another cell of that group. Column 6 has an exclusive triple, but it is of no immediate use, since none of the numerals 1, 2 or 4 appear in another cell of that column. By contrast, the first row has (1,1) (1,3) and (1,6) containing only 1,3 and/or 4, so we can update the partial solution like so:
This shows that
the upper right block has an exclusive triple: (1,8), (1,9) and (2,8)
containing “679”, so we can update again:
· Eliminating other 6,7,9 numerals in the upper right block means (3,7) = 4 · That means that (2,9) = 1, (2,7) = 3 and (9,7) = 7, so · (7,7) = 9 · After updating for these changes we see that there are a number of new exclusive triples, but none of much immediate consequence. In the first row, (1,2), (1,8) and (1,9) are an exclusive triple so we can eliminate 7 and 9 from the other cells in the first row. Also, in the 6th column, (3,6) and (5,6) are an exclusive double so (1,6) = 4 which means the top middle block has an exclusive triple and thus (2,4) = 7, causing (2,8) = 9 and we can solve the upper right block.
Updating the partial solution to reflect these values we have the following:
The consequences seem to come quickly and I arrive at this nearly finished solution here. Take a moment to finish it if you can.
Enlightened Guess and Check
If this method using singletons, exclusive doubles and triples don’t lead to a solution (I’d like to see an example of that), then the desperate phase (one hopes) enlightened guess and check. If you have an exclusive double, say, (1,4) = (1,5) = “ 58” above and assume that (1,4) = 5 so (1,5) = 8 and see if the consequences work out or if you arrive at a contradiction. The tricky part is keeping track of what you’ve tried and having some pencil/paper technique for writing it out.
Thanks to Cal State L.A. Mathematics Professor Mike Krebs http://www.calstatela.edu/faculty/gbrookf/pubs/minisudoku.pdf And etc.
|