For years, many of you have seen me solving Sudoku and other abstract
logic puzzles in the math department, and you have probably wondered
if I ever get any work done. Well, the time has come for me to justify
my hobby by giving a survey of some of the mathematics associated with
Sudoku, most of which I've taken from an excellent AMS Notices article
by Agnes Herzberg and Ram Murty. (Not to be confused with the less
impressive article in this month's issue.)
I'll start by briefly discussing proper graph colorings and why Sudoku
is an example of this type of problem. Then I'll get into some methods
of counting the number of valid "Sudoku squares" that exist. Finally,
I'll talk a little about the minimal number of givens that can determine
a unique solution, including some speculation about jigsaw variants.