SummerBridgeLogo.jpgCOD 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: 

 

00atum.png01Shu.png02Tefnut.png10Geb.png11Osiris.png12Isis.png20Nut.png21Set.png22Nepthia.png

 

 

 

 

Here is a Sudoku using these 9 symbols:

 

Heliopolisudoku.png

 

 

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.

miniSudokuBeatles01.png

 

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:

miniSudokuOps.png

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? 

miniSud01.png

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:

miniSud02.png

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.

miniSudoku4color.png

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:

SudokuEZ01.png

 

Sudoku Solving Algorithm:

1.      Start with the numerals 1,2,…,9 in each of the 81 squares:
SudokuAlgorithm01.png

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:

SudokuAlgorithm02.png

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

SudokuAlgorithm03.png

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

SudokuAlgorithm04.png

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

Sudoku02.png

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.