The Mathematics of Sudoku
GVSU REU 2020
Shelly Smith, GVSU Department of Mathematics
Sudoku is the latest craze in puzzles, and is
played by entering digits from 1 to 9 to complete a partially filled 9x9
grid so that each digit appears exactly once in each row, column, and
3x3 subgrid. While no math is required to play the game, a branch of
mathematics called combinatorics is a useful tool for studying many
aspects of the game and its variations. Combinatorics is the study of
discrete patterns or combinatorial objects, often to count them or find
relationships between the objects.
![Sudoku X board](img/photos/AlgorithmIdentity.jpg)
A Sudoku game grid is a special case of a combinatorial object called a Latin square, an nxn grid where each digit from 1 to n appears exactly once in each row and each column. Latin squares have been studied extensively, but the mathematics of Sudoku is a relatively new area of combinatorial research, and as such has the advantage of many opportunities for exploration and original results. In fact, very few results about Sudoku have been published, and most conjectures are related to only the standard form of the Sudoku game.
![Rainbow Sudoku board](img/photos/RainbowSudoku.jpg)
There are numerous variations of the familiar Sukoku game that are also based on Latin squares, but have different additional requirements instead of the subgrids. These variations make Sudoku a particularly rich topic for a variety of investigations, including mathematical topics such as equivalence relations, inclusion-exclusion, and partially ordered sets.
![Greater Than Sudoku
board](img/photos/GreaterThanSudoku.jpg)
The article Taking Sudoku Seriously, written by Dr. Laura Taalman, was published in the September 2007 Math Horizons magazine. It has a very accessible introduction to some possible research questions and variations of Sudoku.
Desirable experience for applicants
Applicants should have a background in discrete mathematics, including counting techniques and equivalence relations, as well as experience writing formal proofs. While it is beneficial to enjoy playing Sudoku, that is incidental to the mathematical research that we will be conducting. Our primary focus will be to to look for patterns in how puzzles are constructed, and how to determine the minimum number of clues necessary to ensure a unique solution.