Home > Math > Sudoku as a coloured graph

## Sudoku as a coloured graph

Prereqs: Just the definition of a graph – vertices, edges and adjacent vertices.

2 years back I gave an exposition on counting the number of unique sudokus, which are not related to each other by the usual symmetry transformations like permuting cells, rows, etc. No more on that. You can read everything you want to know about this on http://www.afjarvis.staff.shef.ac.uk/sudoku/.  By the way, the number is 6670903752021072936960. Yes, it’s large enough to be comforted that you have enough unique sudokus to solve all your life. Unless you’re a computer.

Today I was thinking about how people can build a “well formed” sudoku (that is, one with a unique solution). People, mind you, not a sudoku-builder program that uses incremental or decremental generation to come up with a valid sudoku.

What is the minimum number of elements one needs to specify for the sudoku to have a unique solution?

This is not at all an easy question to answer. You may answer it with some work for a $4*4$ sudoku perhaps, but as you increase the size the question becomes way harder.  After thinking and searching for whatever literature I could find about this, I stumbled upon the most elegant solution I’ve seen in a while (Alright, I haven’t seen much. Granted. But this got me intrigued.) I shall discuss below the solution as proposed by Herzberg and Ram Murty in their paper.

Trivia: The minimum number is atmost 17. Nobody knows if a sudoku with 16 entries to start with can have a unique solution.

Basic graph theory in a nutshellI will not be writing about this but you can go to the hyperlink if you need a refresher.

_________________________________________

A sudoku as a coloured graph:

A coloured graph is a set of vertices and edges, with an addition variable called “colour” which each vertex is assigned. How do we view a sudoku as a coloured graph?

Consider the usual $9*9$ sudoku. Number all the cells from 1 through 81. These are your vertices. Now connect them as follows: each vertex is connected to all vertices in the same row, column and square ( by square I mean the $3*3$ squares that the sudoku is made up of.) Introduce 9 colours (Girls have the added advantage for visualization here as there are more complex colours on their palette – fuschia, turquoise and what not). Now assign each cell a colour out of these 9. To solve a sudoku, you need to assign these colours such that no two connected vertices have the same colour!

Let’s state this formally.

Proper colouring of a graph

A $\lambda-$ colouring of a graph G is a map f from the vertex set of G to {$1,2, \ldots, \lambda$} . This is called a proper colouring if f(x) $\neq$  f(y) whenever x and y are adjacent in G (Adjacent means that the two vertices of the graph are connected by an edge). So a sudoku puzzle is basically an incomplete colouring( called a partial colouring) which the solver needs to complete.

To quote the experts,

“A Sudoku puzzle corresponds to a partial coloring and the question is whether this partial coloring can be completed to a total proper coloring of the graph”

Does that make you

I hope it does, because otherwise it would imply I have a bad taste in exciting math problems. Anyway, back to work.

_______________________________

A regular graph is one in which the degree of each vertex ( i.e. the number of vertices it is connected to)  is the same. Any $n^2*n^2$ sudoku is a regular graph of degree $3n^2-2n-1$

Now for the punchline – the theorems which answer our question. I will simply state the 2 brilliant theorems here. You can read their equally brilliant proofs in the original paper.

Theorem 1: Let G be a finite graph with v vertices. Let C be a partial colouring of t vertices of G using $d_0$ colours. Let $p_{G,C}$($\lambda$) be the number of ways of completing this colouring by using $\lambda$ colours to obtain a proper colouring. Then $p_{G,C}$($\lambda$) is a monic polynomial in $\lambda$ with integer coefficients of degree v-t for $\lambda \geq d_0$

Implications: The number of ways of completing our $9*9$ sudoku is $p_{G,C}$(9). A unique solution is quaranteed if and only if $p_{G,C}$(9)=1.

____________________________________________

The minimal number of colours required to properly colour the vertices of a graph G is called the chromatic number of G and denoted $\chi(G)$

____________________________________________

Theorem 2: Let G b a graph with chromatic number $\chi(G)$ and C be a partial colouring of G using only $\chi(G)-2$ colours. If the partial coloring can be completed to a total proper coloring of G, then there are at least two ways of extending the colouring.

Implications: If C is a partial colouring of G that can be uniquely completed to a proper total colouring, then C must use at least $\chi(G)-1$ colours. So for our $9*9$ sudoku, at least 8 colours must be used in the given cells for the sudoku to be “well formed”

Note that with these theorems you can make statements about sudokus of all sizes!

____________________________________________

References:

Categories: Math Tags: , ,
1. February 28, 2012 at 2:23 am

interesting!

2. February 28, 2012 at 3:31 am

This might be stupid, but is theorem 2 true because if the partial coloring uses x(G)-2 colors then we can interchange the remaining two colors in the full coloring?

• February 28, 2012 at 5:48 am

@Saket: Yes, you are right. That’s how they prove it in the paper.

Tejal: Sorry Saket, I didn’t read your comment correctly. Yes you are right. It is not unique since the 2 colours can be interchanged.

3. February 28, 2012 at 5:50 am

On a different note, we know that the sudoku has 81 vertices, each of which is adjacent to 20 others. With just this much information, is it possible to deduce that its chromatic number is 9? In other words, can we say that any general graph of 81 vertices each of which is adjacent to 20 others has a chromatic number 9?

Tejal: The only “structure” that a graph has is the skeleton of vertices and edges and how they are connected. So the chromatic number has to be a function of these alone. I do not know the exact dependence but it doesn’t seem trivial at all. You can look at this

It is an NP-hard problem!

4. September 23, 2016 at 1:06 am

Perhaps you know about this already, but Gary McGuire et al. showed (using clever algorithms and heavy computations) that 17 is indeed the minimum number of entries required to ensure unique solution: https://arxiv.org/abs/1201.0749, http://www.math.ie/checker.html.

1. September 8, 2012 at 8:13 pm