Sudoku is a well-known number-placement puzzle that challenges players to fill a
2
n
x
2
n
grid, with digits from 1 to
2
n
, ensuring that each column, each row, and each of the n x n blocks (also called subgrids) contain all the digits exactly once. By envisioning the
4
n
cells of the Sudoku grid as nodes in a graph and representing the connections between them (based on their shared row, column, or block) as edges, we can transform Sudoku into a vertex coloring problem. The idea behind this is to assign a unique color to each number from 1 to
2
n
, making sure that adjacent nodes (nodes connected by an edge) have different colors. Here, we will explore how to solve the Sudoku puzzle using graph coloring.

Introduction

Sudoku has captured the attention as a challenging and engaging number-placement puzzle. The objective is to fill a grid of size
2
n
x
2
n
with digits from 1 to
2
n
, ensuring that each column, each row, and each of the
n
x
n
blocks (also known as subgrids) contains all the digits exactly once. While Sudoku is traditionally approached through logical deduction and trial-and-error methods, an alternative perspective emerges when we apply graph theory to analyze the problem.
Graph theory provides a powerful framework for understanding and solving various real-world problems by representing them as graphs composed of nodes and edges. In the context of Sudoku, we can envision the
4
n
cells as nodes and establish connections between them based on their positions in the grid. These connections reflect the relationships between cells within the same row, column, or block. By adopting this graph-theoretic viewpoint, we can transform the Sudoku puzzle into a vertex coloring problem.
The essence of vertex coloring is to assign a unique color to each node in a graph, such that no two adjacent nodes (nodes connected by an edge) share the same color. In the case of Sudoku, the goal is to assign the numbers 1 to
2
n
as colors to the nodes (cells) in such a way that the constraints of the puzzle are satisfied. This approach shows the inherent structure of the Sudoku grid and applies the principles of graph theory to solve Sudoku puzzles, allowing us to gain valuable insights into the combinatorial aspects of the puzzle and provide a fresh approach to tackle Sudoku challenges.

Sudoku

In a traditional 3x3 game of Sudoku, the objective is to fill a 9x9 grid, divided into 3x3 boxes, with the numbers 1 to 9. Each row, column, and block must contain each digit exactly once. The game begins with a few digits already placed in the grid, and the player’s task is to deduce the missing digits.
Out[]=
4
3
8
2
5
6
1
9
4
9
4
7
6
8
1
2
3
8
2
5
5
3
4
9
7
1
Sudoku can also be generalized to larger grid sizes, such as
n
x
n
, where the puzzle consists of a grid of
4
n
cells, organized into
2
n
rows,
2
n
columns, and
2
n
blocks (
n
x
n
subgrids). The goal is to carefully place the numbers 1 to
2
n
into the empty cells so that each number appears exactly once in every row, column, and block.
To solve the Sudoku puzzle various techniques can be employed. The simplest approach involves eliminating candidates by checking if a number already appears in the same row, column, or block. By iteratively applying these eliminations, players can gradually fill in more digits. However, as the puzzle becomes more challenging, advanced techniques are necessary, involving multiple steps of candidate elimination and deduction.
Sudoku puzzles are known to be NP-complete, and the relatively small grid size of
n
x
n
allows for brute-forcing a solution in just a few seconds, but here we will see how by understanding the rules and employing graph coloring algorithms we can use graph theory to efficiently solve Sudoku puzzles.

Graph Coloring

A graph consist of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices. Let’s consider an example graph with the set of vertices {1, 2, 3, 4} and the set of edges {12, 13, 14, 24, 34}.
Out[]=
In the context of graph theory, graph coloring is a significant concept. It involves assigning different colors to the vertices of a graph in such a way that no two adjacent vertices share the same color. An important step of this is to determine the minimum number of colors required to color the graph’s vertices, which is known as the Chromatic Number. For this example the Chromatic Number is 3:
In[]:=
VertexChromaticNumber[g]
Out[]=
3

Intuition Behind Graph Coloring

To understand the intuition behind graph coloring, let’s consider a simplified example. We have a graph and our goal is to assign colors to the nodes in such a way that no two adjacent nodes share the same color.
As previously seen, for this graph we have a Chromatic Number of 3, meaning we need three colors: Blue, Red, and Green. To assign colors to the vertices of the graph, we can employ a recursive function that traverses the graph and assigns colors to the nodes.
Let’s start with Node 1. We select a color from the color list, let’s take our first color: Blue, and attempt to assign it to Node 1. However, before assigning the color, we need to check if any of the adjacent nodes (nodes connected to Node 1) already have the same color.
Out[]=
If any adjacent node has the same color we cannot assign the color to the node because it would violate the rule of no two adjacent nodes having the same color. In such cases, we need to select a different color from the available color list and repeat the process.
In this example, none of the adjacent nodes to Node 1 have the color Blue, so we can assign Blue to Node 1.
Out[]=
We have colored Node 1 with the color Blue. Now we need to move on to the next node, we will move to Node 2. To color Node 2, we select a color from the color list, once again let’s take our first color: Blue.
Out[]=
However, since Node 2 is adjacent to Node 1, which already has the color Blue, we cannot assign Blue to Node 2. We need to explore alternative colors from the color list, and in this case, the next color is Red.
Out[]=
None of the adjacent nodes have the color Red, so we can assign Red to Node 2.
Now we have colored Node 1 and Node 2 with the colors Blue and Red, respectively. We need to move on to the next node: Node 3. To color Node 3, we select a color from the available color list, once again let's start with Blue.
Out[]=
However, Node 3 is adjacent to Node 1, which already has the color Blue. Therefore, we can not color Node 3 with Blue. We need to try the next color, which is Red.
Out[]=
None of the adjacent nodes have the color Red, so we can assign Red to Node 3.
Although Node 3 can also be colored with the next color in the list: Green, we are trying to minimize the number of colors used, so this is not a good option.
Continuing with Node 4, we select a color from the available color list, once again let’s start with Blue.
Out[]=
Since Node 1 is already colored with Blue, we cannot assign Blue to Node 4 as it is adjacent to Node 1. Hence, we proceed to the next available color, which is Red.
Out[]=
Since Node 2 and 3 are already colored with Red, we cannot assign Red to Node 4 as it is adjacent to Node 2 and 3. Hence, we proceed to the next available color, which is Green.
Now we check all the adjacent nodes again to verify if any of them are already colored with Green, this is not the case, so we can color Node 4 with Green.
In this case, we can see that the entire graph can be colored with 3 colors: Blue, Red, and Green. Thus, the chromatic number of this graph is indeed 3.
As we saw the recursive function traverse the graph, selecting a color for every vertex and checking its compatibility with the adjacent nodes at each step. If a color is found that satisfies the adjacency constraint for a particular node, it is assigned to that node. And this process continues until all nodes in the graph are assigned colors.
Luckily, Wolfram Language (WL) already has a function that finds the optimal vertex coloring. This function can be used to automate the process of assigning colors to the vertices of a graph, ensuring that no two adjacent nodes share the same color in the following way:

How Sudoku can be solved using Graph Coloring

Now we will explore how a Sudoku puzzle can be solved using graph coloring.

Sudoku Graph

Let’s consider a 3x3 Sudoku puzzle as an example. By representing the puzzle as a graph, the Sudoku graph will consists of 81 vertices, with each vertex representing a cell in the Sudoku grid.
​
To solve the Sudoku using graph coloring, we need to establish connections between these vertices. To establish these connections, we assign a unique position to each node, representing its location in the Sudoku grid, with this we can determine which nodes should be connected based on their row, column, and block.
First, we connect each node to every other node in the same row. For instance, let’s take vertex 14 as an example. We connect it to all other vertices in the same row.
This creates edges between nodes within the same row, resulting in a graph where nodes within a row share a connection.
This connection enables the nodes within the same row to interact and exchange information during the solving process.
Similarly, we connect each node to every other node in the same column. For example, node 14 is connected to all other vertices in the same column.
This connection allows nodes within the same column to interact and exchange information during the solving process.
Additionally, we establish connections between each node and every other node in the same block or 3x3 subgrid. For instance, vertex 14 will be connected to all neighboring vertices within the same block.
This connection enables nodes within the same block to interact and share information.
By establishing these connections based on rows, columns, and blocks, we create a connected graph where each node is connected in the following way:
The described graph can be created using the following resource function:
Remember that these graphs are simplified, and many edges are hidden. In reality, each vertex has an edge connecting it to every vertex in its column and row, but the images show these edges lying on top of each other for clarity.

Sudoku Problem

Now let’s integrate the hints or given numbers into the Sudoku graph. As an example, let’s consider the following Sudoku puzzle.
We will take the 7’s as an example of how we will include the hints in the graph:
We know that we need to ensure that the number 7 is not present in the same row, column, or block where it already exists. Additionally, we want to enforce that the two vertices representing the number 7 in the Sudoku graph have the same color. To achieve this, we introduce additional connections between the two vertices with the number 7 in the Sudoku graph. This connection is established by connecting one of the vertices with a 7 with all the neighbors of the other vertex with a 7.
We also introduce additional connections between vertices with the number 7 and all the cells that have a number different from 7.
This connections will guarantee that the two vertices with 7’s will have the same color.
Integrating the hints or given numbers into the Sudoku graph involves adding these additional connections while maintaining the original connections based on rows, columns, and blocks. This process creates a more interconnected structure that captures the relationships between the given numbers and their constraints.
We can implement this integration of the hints with the following function:

Graph coloring

With the sudoku graph and the integrated hints let’s explore how the Sudoku puzzle can be approached as a graph coloring problem. In a graph coloring problem the objective is to assign colors to the vertices of the graph in such a way that adjacent vertices (vertices connected by an edge) do not have the same color.
In the context of a standard Sudoku puzzle, we need to assign a unique number from 1 to 9 to each cell. Since the numbers from 1 to 9 can be represented as colors, 9 distinct colors are required to solve the puzzle. This requirement aligns with the concept of the chromatic number in graph theory.
To find the solution to a Sudoku puzzle, we can use the following function designed for this purpose:
And it prints the solution as a matrix :
We can also visualize the solution with the following function:
It’s important to note that this approach can work for any valid Sudoku problem, regardless of the number of solutions. So, even if a Sudoku puzzle has multiple valid solutions or an infinite number of solutions, the graph coloring algorithm will still find a suitable correct solution ensuring that no adjacent cells have the same color:

Conclusion

We have explored how graph theory and graph coloring techniques can be applied to solve Sudoku puzzles. By representing the Sudoku grid as a graph and using graph coloring algorithms, we can assign colors (that represent numbers) to the cells of the puzzle maintaining the constraint that adjacent cells must have different colors. This way we can systematically find a valid solution for the Sudoku puzzle.
Graph theory and graph coloring have broad applications beyond Sudoku, and can be applied to other combinatorial problems and optimization challenges. These techniques offer valuable tools for solving puzzles and addressing real-world problems in a structured and systematic manner. Overall, with graph theory and graph coloring, we gain the ability to explore and tackle a wide range of problems that can be formulated as related graph-based problems.

References

◼
  • Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008. Retrieved from https://networkx.org/nx-guides/content/generators/sudoku.html
    • ◼
  • Ishaan Gupta (2020, June 15). Sudoku Solver — Graph Coloring [Blog post]. Retrieved from https://medium.com/code-science/sudoku-solver-graph-coloring-8f1b4df47072
    • ◼
  • Chytrý, V. Sudoku Game solution based on Graph Theory and suitable for school-mathematics. ACTA MATHEMATICA 17, p. 55.
    ​

    • CITE THIS NOTEBOOK

    Solving Sudoku puzzles with Graph Theory​
    by Alejandra Ortiz Duran​
    Wolfram Community, STAFF PICKS, August 5, 2023
    ​https://community.wolfram.com/groups/-/m/t/2983903