Sudoku
Sudoku is a number puzzle that challenges players to fill a grid with digits in such a way that each number from one to nine appears only once in each row, column, and designated subgrid. This intriguing game is rooted in the mathematical concept of Latin squares, which were explored by mathematician Leonhard Euler in the 18th century. Originally published in the 1970s, Sudoku gained massive popularity in Japan during the late 1980s and experienced a revival in Europe and America in the mid-1990s. Various sizes of Sudoku puzzles exist, including 4x4, 16x16, and 25x25 grids, with the standard format being 9x9.
Mathematically, Sudoku puzzles have been analyzed through the lens of graph theory, revealing connections to graph coloring problems. Researchers have found that a standard Sudoku puzzle can be represented as a graph, where each cell corresponds to a vertex, and the objective is to color the graph using nine colors while adhering to the puzzle's constraints. While the conditions for a unique solution in Sudoku puzzles are still under investigation, studies have indicated that having at least eight digits filled in at the start is necessary for uniqueness.
Moreover, engaging in Sudoku has been linked to potential cognitive benefits, such as improved working memory and decision-making skills. However, these effects tend to be temporary rather than indicative of long-term benefits. Sudoku continues to captivate enthusiasts, who employ various strategies and algorithms to tackle increasingly complex puzzles.
On this Page
Subject Terms
Sudoku
SUMMARY: The game of Sudoku is explained by and informs graph theory and randomness.
Sudoku is a number puzzle based on the mathematical concept of a “Latin square.” Latin squares are arrays of numbers in which each number is listed only once in any row or column. Leonhard Euler originated the term, calling them “Latin squares” because he used Latin letters rather than numbers in his investigations. Completed Sudoku grids are Latin squares that are further subdivided into subgrids in which the numbers also appear only once in the subgrid. The graphic below shows a completed nine-by-nine Sudoku puzzle.
Originally published in the 1970s in Europe and the United States, Sudoku surged to popularity in Japan in the late 1980s and reappeared in Europe and America in the mid-1990s, becoming popular among puzzlers. The popularity of the puzzle continued to grow in the twenty-first century, leading the puzzle to become the subject of mathematical scrutiny.
Sudoku is usually based on a Latin square with nine rows and columns, although puzzles of other sizes such as four-by-four, 16-by-16, and 25-by-25 are also possible. Some of the numbers are filled in to start. The goal is to quickly and accurately complete the puzzle, with the digits one through nine placed once in each row, column, and subgrid. Below is an unsolved Sudoku puzzle:
Graph Theory
There are a number of interesting mathematical questions associated with Sudoku puzzles, in particular, the conditions under which they have one solution. In 2007, Agnes Herzberg and M. Ram Murty showed that Sudoku puzzles can be recast as graph coloring problems, allowing the broad, well-developed theory of graphs to be applied to the solution question. In particular, they showed that a standard Sudoku puzzle can be thought of as a graph where each cell in the puzzle is represented by a vertex with 20 edges, each edge connecting the cell to another cell in the row, column, or sub-grid. Graphs for which all vertices have the same number of edges are called “regular,” so Sudoku graphs made in this way are “20 regular” graphs.
Since each digit can appear only once in each row, column, and subgrid, putting the nine digits into the cells is equivalent to coloring the vertices of the graph with nine different colors such that no vertices connected by an edge are the same color—or in graph theory terminology, finding a “proper 9-coloring” of the graph. The number of ways to color a regular graph with n colors is a well-known formula that is a function of the number of colors and the number of vertices. Using this and other ideas about coloring graphs, Herzberg and Murty proved that nine-by-nine puzzles must have at least eight different digits shown in the starting configuration to have a unique solution.
There are still many unanswered questions about when Sudoku puzzles have one solution. Assuming that eight different digits are used in the starting configuration, how many numbers total must be shown in the starting configuration to ensure a unique solution? The answer is not known; a small number of distinct puzzles with 17 entries in the starting configuration are known to have a unique solution. There are no known puzzles with 16 or fewer entries that have unique solutions. Does one exist? Would the answer be different if all nine digits were used in the starting configuration? Mathematicians and puzzlers are investigating these and other interesting questions. For example, in 2010, mathematicians Paul Newton and Stephen DeSalvo demonstrated that the arrangement of numbers in Sudoku puzzles is more random (by some definitions of randomness) than nine-by-nine matrices produced by random generators since Sudoku rules exclude some of the possible arrangements that have innate symmetry.
Sudoku enthusiasts have an array of methods for solving complex Sudoku puzzles. Some individuals have developed backtracking algorithms—computer programs that explore and solve Sudoku puzzles. Other strategies include creating symmetries, nishio, X-wing, and the 45-rule.
Sudoku’s boom in popularity led to research on the puzzles’ potential benefits for the human brain. Some research indicates that Sudoku puzzles can improve brain functions by stimulating portions of working memory and decision-making. Additionally, working on Sudoku before bed may improve sleep. However, these impacts are short-lived boosts for the brain rather than long-term cognitive enhancements observed when the brain learns a new skill or has a new experience.
Bibliography
Ashlesh, Patil, et al. “Role of Prefrontal Cortex during Sudoku Task: fNIRS Study.” Translational Neuroscience, vol. 11, no. 1, 2020, pp. 419–27, doi.org/10.1515/tnsci-2020-0147.
Herzberg, Agnes, and Ram M. Murty. “Sudoku Squares and Chromatic Polynomials.” Notices of the American Mathematical Society, 54, no. 6. 2007.
Kalia, Vrinda, et al. “Perseverance in Solving Sudoku: Role of Grit and Cognitive Flexibility in Problem Solving.” Journal of Cognitive Psychology, vol. 31, no. 3, 2019, pp. 370–78, doi.org/10.1080/20445911.2019.1604527. Accessed 11 Oct. 2024.
"The History of Sudoku." Easybrain, https://sudoku.com/how-to-play/the-history-of-sudoku/#:~:text=The%20history%20of%20Sudoku%20dates,published%20in%20France%20in%201895. Accessed 3 Nov. 2024.
Zyga, Lisa. "Discovery Could Lead to More Difficult Sudoku Puzzles." Phys.org, 13 Feb. 2010, phys.org/news/2010-02-discovery-difficult-sudoku-puzzles.html. Accessed 1 Oct. 2024.