A directed graph representation of a rank 3 sudoku

Sudoku is a single-player game where the player attempts to choose entries from {1,2,3,4,5,6,7,8,9} to complete a partial assignment on a 9 x 9 matrix (rows and columns like a chess board or checkerboard). None of those 9 numbers (digits) may appear twice in any row, column or any of the nine "blocks" (nine 3 x 3 submatrices on that 9 x 9 row x column board). It should be clear that each of the nine numbers must appear once in every row, column and box (since there are nine cells in each and no number may appear twice in any of those subsets).

The Sudoku board can be interpreted mathematically as a graph: The graph will have 81 vertices with each vertex corresponding to one of the 81 squares (or cells) on the Sudoku 9 x 9 grid. Solving the Sudoku puzzle then amounts to a graph coloring problem, where the term "color" has a general theoretical meaning in graph theory, but does originate in early work done with the practical motivation of determining the minimum number of colors required to distinguish the countries sharing a border on a map. The "colors" in the case of Sudoku amount to the 9 digits that have to be correctly assigned to the cells of the Sudoku board given a partial assignment with a minimum of 17 cells filled in (that is a complex mathematical theoretical problem, the MNC problem, i.e., proving that a minimum of 17 cells must be filled in if you are providing a Sudoku game problem with only a single solution rather than several that might work). If you have not played Sudoku (I find puzzles annoying but enjoy researching why they are annoying), here is what a game might look like:

This is a very difficult Sudoku puzzle, the Will Shortz Puzzle No. 301. Just to illustrate what I am talking about, here is the solution to that puzzle (spoiler alert if you were going to try to solve the puzzle first):

Returning to the graph discussion, each vertex is then one of the 81 cells in the 9 x 9 Sudoku. The connections between these vertices are called edges. The rules of the game I gave earlier are used to define the edge connections: (1) any vertices (cells) in the same column are connected with an edge (2) any of the vertices (cells) in the same row are connected with an edge and (3) any of the cells in one of the 9 three by three boxes (you can more or less see them above in the bold lines overlaying the lighter grid) are connected with an edge. There are 810 edges connecting the vertices (cells) by these rules. This is a regular graph, i.e.,the degree of every vertex is the same. That is, the  total number of edges connected to each vertex (cell) is the same and is in fact 20. There is a mathematical equation to give that number for similar graphs of various ranks (the rank of the 9 x 9 Sudoku is 3; the number of rows or columns is therefore n x n or 9): 3n(squared) - 2n - 1. So for n = 3, the degree of each vertex is 3 squared = 9 x 3 = 27 - 2 x 3 = 6 - 1 = 27 - 6 - 1 = 20 (pardon me for not using markup language to make the mathematical notation pretty; it is late as I write and I do not want to force a MathJax download on visitors anyway). Since each edge connects two vertices, the total number of edges is then (81 vertices / 2 ) x (20 edges per vertex) = 810. The coloring problem then becomes how to assign a digit from a selection of 1 - 9 to each vertex such that no two adjacent vertices (two vertices are adjacent if they share a connecting edge, the mathematical equivalent of two cells being in the same row, column or 3 x 3 box) have the same digit.

In any case, I finally reach the purpose of this discussion, which is to share my first computer generated drawing of the vertices and edge connections of an empty Sudoku (that is, none have been assigned digits since the labels would further clutter the already dense graph). The vertices are around the perimeter of the circular graph (they are colored red, in the human sense of color, and they are much too large, but this was my first plot) and they are connected by the spider web of edges as defined above (I hope you enjoy it as much as I apparently do). You can click on the picture below to see the full size picture of the graph: