Unlocking Sudoku's Secrets

Summary

Sudoku has long captivated puzzle enthusiasts worldwide with its logical challenges and addictive nature. While it may seem like a simple game of numbers, beneath the surface lies a fascinating connection to the realm of mathematics. Graph theory and abstract algebra both play a crucial role in unravelling the intricacies of sudoku. Sudoku puzzles consist of a $9 \times 9$ grid, divided into nine $3 \times 3$ sub-grids called regions. The objective is to fill the grid with numbers from 1 to 9, ensuring that each row, column, and region contains every digit exactly once. A vertex colouring problem In graph theory, a graph is a mathematical structure that comprises a set of vertices, or nodes, connected by edges. An area rich in mathematical questions, graph theory has a long history of famous thought-provoking problems. One of the most well-known of these problems is the vertex colouring problem: Given an undirected graph $G = (V, E)$, where $V$ represents the set of vertices and $E$ represents the set of edges, can one find an assignment of colours to each vertex in $V$ satisfying the condition that no two adjacent vertices (connected by an edge) have the same colour? While sudoku may appear as a grid of numbers, we can view it through the lens of graph theory. Interestingly, we can represent a sudoku puzzle as a graph, where each of the $81$ cells in the sudoku grid corresponds to a vertex in the graph. We label the vertices with ordered pairs $(x, y),$ $x$ and $y$ being integers from $1$ to $9$. We then join two distinct vertices $(x, y)$ and $(x’, y’)$ by an edge if and only if any of these conditions apply: $x = x’$ (the two cells are in the same row), $y = y’$ (same column), or $\displaystyle\left\lceil \frac{x}{3} \right\rceil = \left\lceil \frac{x’}{3} \right\rceil$ and $\displaystyle\left\lceil \frac{y}{3} \right\rceil = \left\lceil \frac{y’}{3} \right\rceil$ (same $3\times3$ region). So the top-left region of the sudoku board would be connected like this: W...