In the

mathematics of Sudoku The mathematics of Sudoku refers to the use of mathematics to study Sudoku puzzles to answer questions such as ''"How many filled Sudoku grids are there?"'', "''What is the minimal number of clues in a valid puzzle?''" and ''"In what ways can S ...

, the Sudoku graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

whose vertices represent the cells of a (blank) Sudoku puzzle and whose edges represent pairs of cells that belong to the same row, column, or block of the puzzle. The problem of solving a Sudoku puzzle can be represented as precoloring extension on this graph. It is an

integral In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented i ...

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

Basic properties and examples

9x9 Sudoku graph neighbors (really fixed)

On a Sudoku board of size

n^2\times n^2

, the Sudoku graph has

n^4

vertices, each with exactly

3n^2-2n-1

neighbors. Therefore, it is a

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

. The total number of edges is

n^4(3n^2-2n-1)/2

. For instance, the graph shown in the figure above, for a

4\times 4

board, has 16 vertices and 56 edges, and is 7-regular. For the most common form of Sudoku, on a

9\times 9

board, the Sudoku graph is a 20-regular graph with 81 vertices and 810 edges. The second figure shows how to count the neighbors of each cell in a

9\times 9

board.

Puzzle solutions and graph coloring

Each row, column, or block of the Sudoku puzzle forms a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

in the Sudoku graph, whose size equals the number of symbols used to solve the puzzle. A

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the Sudoku graph using this number of colors (the minimum possible number of colors for this graph) can be interpreted as a solution to the puzzle. The usual form of a Sudoku puzzle, in which some cells are filled in with symbols and the rest must be filled in by the person solving the puzzle, corresponds to the precoloring extension problem on this graph.

Algebraic properties

For any

n

, the Sudoku graph of an

n^2\times n^2

Sudoku board is an

integral graph In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjace ...

, meaning that the

spectrum A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of colors i ...

of its

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

consists only of integers. More precisely, its spectrum consists of the

eigenvalue In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

s *

3n^2-2n-1

, with multiplicity

1

, *

2n^2-2n-1

, with multiplicity

2(n-1)

, *

n^2-n-1

, with multiplicity

2n(n-1)

, *

n^2-2n-1

, with multiplicity

(n-1)^2

, *

-1

, with multiplicity

n^2(n-1)^2

, and *

-n-1

, with multiplicity

2n(n-1)^2

. It can be represented as a

of the

abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commut ...

Z_n^4

Related graphs

The Sudoku graph contains as a subgraph the

rook's graph In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

, which is defined in the same way using only the rows and columns (but not the blocks) of the Sudoku board. The 20-regular 81-vertex Sudoku graph should be distinguished from a different 20-regular graph on 81 vertices, the

Brouwer–Haemers graph In the mathematical field of graph theory, the Brouwer–Haemers graph is a 20- regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construct ...

, which has smaller cliques (of size 3) and requires fewer colors (7 instead of 9).

References

{{reflist, refs= {{citation , last1 = Gago-Vargas , first1 = Jesús , last2 = Hartillo-Hermoso , first2 = Maria Isabel , last3 = Martín-Morales , first3 = Jorge , last4 = Ucha-Enríquez , first4 = Jose Maria , editor1-last = Ganzha , editor1-first = Victor G. , editor2-last = Mayr , editor2-first = Ernst W. , editor3-last = Vorozhtsov , editor3-first = Evgenii V. , contribution = Sudokus and Gröbner bases: Not only a ''divertimento'' , doi = 10.1007/11870814_13 , pages = 155–165 , publisher = Springer , series = Lecture Notes in Computer Science , title = Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11–15, 2006, Proceedings , volume = 4194 , year = 2006, hdl = 11441/23605 {{citation , last1 = Herzberg , first1 = Agnes M. , author1-link = Agnes M. Herzberg , last2 = Murty , first2 = M. Ram , author2-link = M. Ram Murty , issue = 6 , journal =

Notices of the American Mathematical Society ''Notices of the American Mathematical Society'' is the membership journal of the American Mathematical Society (AMS), published monthly except for the combined June/July issue. The first volume appeared in 1953. Each issue of the magazine since ...

, mr = 2327972 , pages = 708–717 , title = Sudoku squares and chromatic polynomials , url = https://www.ams.org/notices/200706/tx070600708p.pdf , volume = 54 , year = 2007 {{citation , last1 = Klotz , first1 = Walter , last2 = Sander , first2 = Torsten , issue = 1 , journal = Electronic Journal of Combinatorics , mr = 2651734 , page = Research Paper 81, 13pp , title = Integral Cayley graphs over abelian groups , url = https://www.combinatorics.org/Volume_17/Abstracts/v17i1r81.html , volume = 17 , year = 2010, doi = 10.37236/353 , doi-access = free {{mathworld, title=Brouwer–Haemers Graph, id=Brouwer-HaemersGraph, mode=cs2 {{citation , last1 = Rosenhouse , first1 = Jason , author1-link = Jason Rosenhouse , last2 = Taalman , first2 = Laura , author2-link = Laura Taalman , pages = 128–130 , publisher = Oxford University Press , title = Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle , title-link = Taking Sudoku Seriously , year = 2011 {{citation , last = Sander , first = Torsten , issue = 1 , journal = Electronic Journal of Combinatorics , mr = 2529816 , page = Note 25, 7pp , title = Sudoku graphs are integral , url = https://www.combinatorics.org/Volume_16/Abstracts/v16i1n25.html , volume = 16 , year = 2009, doi = 10.37236/263 , doi-access = free Application-specific graphs Parametric families of graphs Regular graphs Sudoku