# COD Summer Bridge Enrichment - 2011

## Sudoku

Definition: A Sudoku is a 9 by 9 array of 9 symbols in which every row,
every column, and every 3 by 3 box with thick borders contains each of the
nine symbols exactly once.

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.
Before looking at the algorithm below, try to solve this fairly easy Sudoku.  Then compare your thought processes with the algorithm presented afterwards:

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.

The fifth column (heh) has two singletons: The 2 in the second row and the 4 in the sixth row.  So far, discovering singletons in columns 4 and 5 has the partial solution looking like this (singletons in green, consequences in blue):

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):

 1 34 6 34  7 9 1 34 1   5 78 1  45  89 1  45 7 2 3  67 9 1 34 6  9 1234 5 8 12    7 12 4    9 6 1 34  7 9 3   7 9 1 34    9 12 4 6 2 4  7 9 12 4 3 12 4    9 12 4  7 1  4  7 9 8 5 23 1 23 4 7 2  5 6 23     9 23    89 9 234   8 6 12     8 12     8 12 5 23 7 2  5  8 2     8 7 12  56 8 3 9 1 4 12     8 7 6 12345 12  5 12 45 8 34    9 23 5   9 234    9 2345 234 2345 9 2 456 2345 7 8 1 234 6 12345  8 234   8 9 12  567 12 456 12345 7 34  7 23 567 234 6

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:

 1 34 3   7 9 1 34 1   5 78 1  45  89 1  4 2 67 9 1 34 6  9 1234 5 8 12    7 12 4    9 6 34  7 9 7 9 1 34    9 6 2    7 9 12 4 3 12 4    9 12 4 4  7 9 8 5 23    8 1 23 4 7 5 6 2      9 2     89 9 4 6 12     8 12     8 12 5 3 7 5 2     8 7 6 3 9 1 4 2     8 7 6 12345 12  5 12 45 8 34    9 2  5   9 234    9 234 23 2345 9 2 456 7 8 1 234 6 12 4   8 2     8 9 12  5 12 456 3 4  7 2  567 2 4 6

Let’s clean up the above array a bit so we can examine it carefully.

 134 379 134 1578 14589 14 2 679 13469 1234 5 8 127 1249 6 3479 79 1349 6 279 124 3 1249 124 479 8 5 238 1 23 4 7 5 6 29 289 9 4 6 128 128 12 5 3 7 5 28 7 6 3 9 1 4 28 7 6 12345 125 1245 8 349 259 2349 234 23 2345 9 2456 7 8 1 2346 1248 28 9 125 12456 3 47 2567 246

## 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:

 134 79 134 1578 14589 14 2 679 13469 1234 5 8 127 1249 6 3479 79 1349 6 79 124 3 1249 124 479 8 5 238 1 23 4 7 5 6 29 289 9 4 6 128 128 12 5 3 7 5 28 7 6 3 9 1 4 28 7 6 1245 125 1245 8 349 259 2349 24 3 245 9 2456 7 8 1 246 1248 28 9 125 12456 3 47 2567 246

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:

 134 79 134 578 589 14 2 679 69 1234 5 8 127 1249 6 3479 79 1349 6 79 124 3 1249 124 479 8 5 238 1 23 4 7 5 6 29 289 9 4 6 128 128 12 5 3 7 5 28 7 6 3 9 1 4 28 7 6 1245 125 1245 8 349 259 2349 24 3 245 9 2456 7 8 1 246 1248 28 9 125 12456 3 47 2567 246

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:

 134 79 134 578 589 14 2 679 69 24 5 8 27 249 6 3 79 1 6 79 12 3 129 12 4 8 5 238 1 23 4 7 5 6 29 289 9 4 6 128 128 12 5 3 7 5 28 7 6 3 9 1 4 28 7 6 1245 125 1245 8 9 25 234 24 3 245 9 2456 7 8 1 246 1248 28 9 125 12456 3 7 256 246

This is a big cascade of consequences which can be enumerated in order like so:

·          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:

 13 9 13 58 58 4 2 7 6 24 5 8 7 29 6 3 9 1 6 7 12 3 129 12 4 8 5 238 1 23 4 7 5 6 29 289 9 4 6 128 128 12 5 3 7 5 28 7 6 3 9 1 4 28 7 6 1245 125 1245 8 9 25 234 24 3 245 9 2456 7 8 1 24 1248 28 9 125 12456 3 7 256 24

The consequences seem to come quickly and I arrive at this nearly finished solution here.  Take a moment to finish it if you can.

 3 9 1 58 58 4 2 7 6 4 5 8 7 2 6 3 9 1 6 7 2 3 9 1 4 8 5 8 1 3 4 7 5 6 2 9 9 4 6 128 18 12 5 3 7 5 2 7 6 3 9 1 4 8 7 6 45 125 145 8 9 5 3 24 3 45 9 456 7 8 1 24 1 8 9 25 45 3 7 6 24

## 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.