Sudoku for Mental Strength

by Ian Riensche, Tacoma Power, USA

What does a protection and control engineer like to do after working with pickups, levels and duties all day?  Go home and play with numbers of course. 

The object of my preoccupation is Sudoku, the number placement game that has become a standard fixture in newspapers around the world.

Sudoku is not just an addictive pastime of millions of people across the globe. 

It is also recommended by researchers as a tool to help stay mentally acute.  The Journal of the American Medical Association reported that in a study spanning several years, subjects given regular training in mental functions showed significantly higher cognitive performance years down the road compared to subjects given no training.

If you are unfamiliar with Sudoku, allow me to give you a -

Sudoku Primer

Classic Sudoku is a version of Latin Squares played on a 9×9 grid that has three constraints:  every row, column and 3×3 block must contain the integers 1 through 9, inclusively.  Latin Squares only have the row and column constraints, so it’s safe to say that every Sudoku puzzle is a Latin Square, but not every Latin Square is a Sudoku puzzle. 

A typical puzzle begins with anywhere from 26 to 36 given or seed numbers, and the object is to fill in the blank cells, using logic and reasoning, while obeying the three Sudoku constraints.  In Fig. 10 you will find a “diabolical” Sudoku puzzle, and it is easier said than done, as you may find out.  The solution presented in Fig. 9 has been turned upside down as a courtesy to those that want to attempt this puzzle.

The game as we know it first appeared in Dell Magazines in 1979 with the name “Number Place;” it was developed by retired architect Howard Garns.  Nikoli, the Japanese puzzle company, introduced Sudoku in 1984.  The name “Sudoku” is a portmanteau of “Suuji wa dokushin ni kagiru,” the original title of the Nikoli feature, which is a Japanese phrase that roughly translates, “the digits must be single.”

More Sudoku History

Sudoku grabbed my attention in 2005 when our local newspaper ran a front page article on the topic.  The article mentioned Wayne Gould, a retired judge from New Zealand who encountered the puzzle while traveling in Japan in 1997.  He happened to be a hobbyist computer programmer, so he set to work writing a PC application that could generate Sudoku puzzles.  Several years later he finished the program, and in 2004 convinced The Times of London to run Sudoku as a feature.  It was at this point that Sudoku began to spread like wildfire around the world.  Our local newspaper also began running Gould’s Sudoku puzzles.

Upon reading the Sudoku article, I was taken with it and immediately set out to dissect this compelling twist on the Latin Square. 

  • My first attempt was with MS Excel, and although someone has apparently figured it out, I wasn't expert enough to adapt Excel to solve a Sudoku puzzle

  • My next attempt was with linear algebra; again, my knowledge and experience of the discipline lacked sufficient depth
  • Finally, I landed on graph theory, which is perfectly suited to solving Sudoku; search algorithms such as Chain Exclusion, Pile Exclusion and "X-wing" lend themselves well to completing Sudoku puzzles in the moderate-to-difficult range

Armed with a new-found awareness of graph theory, I constructed a program, first in C++ and later in Javascript, that could generate and solve 9×9 and 6×6 Sudoku puzzles using three-dimensional arrays.  From there, I built a website (www.sudokupuzzler.com) and began work on a book.  Sudoku for Lunch was published in 2008 by Tate Publishing. 

In 2009, I sent a copy of my book to our local newspaper, The News Tribune of Tacoma.  The timing was perfect, as the managing editor was then searching for a new Sudoku vendor, because readers had complained that the weekend puzzles had been too easy.  Within a few months I became their supplier, and a few months later I also began supplying Sudoku puzzles to their sister newspaper, The Olympian.

There has been a lot of discussion about what makes a Sudoku puzzle difficult.  Many people believe it comes down to the quantity of seed integers, while others believe it is more than that.  The truth is, a puzzle’s difficulty is based primarily on the search algorithm(s) necessary to solve it; although, too many or too few seeds will ultimately influence its difficulty (a puzzle with five seeds would be impossible, a puzzle with 80 would be trivial). 

Some Sudoku Techniques

  • A common technique used to solve advanced Sudoku puzzles is to jot down possible answers, known as candidates, in the cells.
  • Chain Exclusion is an approach based on graph theory that recognizes identical pairs of integers that stand alone in a region (row, column or block).  When found, other occurrences can be eliminated.  For instance, in Fig. 3, the 4,9 pair appear alone in the second and third cells. Because no other integers are possible in those cells, we can safely eliminate every other 4 and 9 in the same row. 
    Figure 4 demonstrates the simplification that takes place after eliminating unnecessary 4s and 9s due to Chain Exclusion.
  • Pile Exclusion can be thought of as the inverse of Chain Exclusion.  It identifies identical pairs that are nested among other candidates in two cells in a given region; the only caveat is that there can't be any other occurrences of those integers in that region.  For instance, in Fig. 5, the 3 and 6 appear in the first and second cells, and only those cells.
    Because the solution must contain either a 3 or 6 in the first cell, and either a 3 or 6 in the second cell, we can eliminate the other candidates in those cells.  In Figure 6, you can see that we were able to eliminate the 1 and 4 in the first cell, and the 1, 4, 8 in the second cell, according to the rules of Pile Exclusion.
    The principles of Chain and Pile Exclusion logically extend beyond matching pairs to matching triples and greater.
  • X-wing doesn't refer to a spaceship from a science fiction movie, at least not in the context of Sudoku.  It refers to the proximity of candidate integers to each other in this particular search algorithm.  In Figure 7, notice the four 7s form a rectangle, each in a different block.  Because there aren't any other 7s in rows 1 and 8, exactly one of the diagonal pairs must be true, and we can safely eliminate other occurrences of 7 in the two intersecting columns.
    In the resulting simpler puzzle in Fig. 8, we are able to cross out extraneous 7s in columns 1 and 7, thanks to X-wing logic.
  • There are many more advanced Sudoku search techniques, with names like "Swordfish" and "Death Blossom," to name a couple. 

The more you play, the more familiar you will become with these advanced search algorithms.  But be warned, because it is also true that the more you play Sudoku, the more addicted you will likely become, and you may find yourself working with pickups, levels and duties all day, only to go home and continue playing with numbers.

If you have any questions or feedback, please feel free to e-mail: ian@sudokupuzzler.com. 

Good luck!

Ian Riensche - protection engineer and Sudoku editor

Tips:

  • Use logic and process of elimination to fill in the blank cells using numbers 1 through 9.
  • Each number can appear only once in each row, column and 3x3 block.

Sudoku is not just an addictive pastime of millions across the globe.  It is also recommended as a tool to help stay mentally acute.

Warning!

The addiction to Sudoku can bring unpleasant and unpredictable consequences to many.

In June 2008 after 105 witnesses and three months of evidence, an Australian drug trial costing $1 million was aborted when it was discovered that five of the twelve jurors had been playing Sudoku instead of listening to evidence.

Malcolm Knox, June 11, 2008. The Sydney Morning Herald

Let?s start with organization in protection testing