Sudoku and Graph Theory
Mathematicians find new clues to the popular puzzle
When you get stuck on a fiendishly difficult sudoku, it’s hard not to wonder if the puzzle really has a solution. At another moment, aglow in the triumph of a clever deduction, you might have a sneaking suspicion that there may be a simpler, more systematic way of finding the answer. Further questions may come to mind: How many different sudoku puzzles are possible in the standard 9-by-9 format? Can a puzzle with few initial entries be easier to solve than one with more entries? What’s the smallest number of initial entries necessary to guarantee that there’s one, and only one, solution?
Although the puzzles are often billed as requiring no math to solve, some of the questions they raise call for mathematical analysis. Researchers are now taking up the task. An article in the June Notices of the American Mathematical Society lays a mathematical framework for addressing some basic questions about sudokus.