Sudoku graph

In the mathematics of Sudoku, the Sudoku graph is an undirected graph 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 Cayley graph.

Basic properties and examples

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. 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 in the Sudoku graph, whose size equals the number of symbols used to solve the puzzle. A graph coloring 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, meaning that the spectrum of its adjacency matrix consists only of integers. More precisely, its spectrum consists of the eigenvalues
*$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 Cayley graph of the abelian group $Z_n^4$.

Related graphs

The Sudoku graph contains as a subgraph the rook's graph, 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, 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
, hdl-access = free

{{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
, 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