Archive

Posts Tagged ‘Graph theory’

Sudoku as a coloured graph

February 28, 2012 6 comments

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:

Advertisements
Categories: Math Tags: , ,