GRAPH THEORY: APPLICATION OF VERTEX COLORING IN SUDOKU
ABSTRACT
In this project work, we study and contribute to a clear and rigorous understanding of mathematics behind the popular number placement puzzle - Sudoku. Sudoku puzzle consists of a 9 × 9 grid of 81 cells (or slots) with some cells already filled with digits from 1 to 9. The objective of the puzzle is to fill the rest of the grid with digits from 1 to 9 such that no digit repeats within any row, column and specified 3 × 3 blocks. For anyone trying to solve a Sudoku puzzle, several questions arise naturally. To cite a few: for a given puzzle, does a solution exist? If the solution exists, is it unique? If the solution is not unique, how many solutions are there? Moreover, is there a systematic way of determining all the solutions? How many puzzles are there with a unique solution? This project attempts to answer such interesting and intriguing questions. Since Sudoku is a special case of a general graph theoretic problem, concept and insights involving graph theory are emphasized using Frank Harary’s book on Graph Theory. In addition, some applications of these concept are demonstrated.
TABLE OF CONTENTS
TITLE PAGE………………………………………………………………………………i
DECLARATION ii
CERTIFICATION iii
DEDICATION iv
ACKNOWLEDGEMENT v
ABSTRACT vi
TABLE OF CONTENTS vii
CHAPTER ONE
INTRODUCTION
1.1 Background of the Study 1
1.2 Aim and Objectives of the Study 2
1.3 Scopes and Limitation of the Study 3
1.4 Definition of Basic Terms 3
CHAPTER TWO
LITERATURE REVIEW
2.0 Introduction 12
CHAPTER THREE
CHROMATIC POLYNOMIAL OF SUDOKU
3.0 Introduction 15
3.1 Chromatic Function 15
3.2 Chromatic Function is a Polynomial 16
3.3 Chromatic Polynomial of a Sudoku Puzzle 18
CHAPTER FOUR
SUDOKU GAME SOLUTION USING VERTEX COLORING
4.0 Introduction 22
4.1 Converting Sudoku to Coloring Problem 23
4.2 Vertex Coloring Technique 25
4.3 Counting Sudoku Solution 26
CHAPTER FIVE
SUMMARY, CONCLUSION AND RECOMMENDATIONS
5.1 Summary 30
5.2 Conclusion 30
5.3 Recommendations 31
REFERENCES 32
CHAPTER ONE
INTRODUCTION
1.1 Background of the Study
A graph G is a finite nonempty set V of objects called vertices (vertex) together with a set E of 2-element subsets of V called edges. Vertices are sometimes called points or nodes, while edges are sometimes referred to as lines or links. Each edge {u,v} of V is commonly denoted by uv or vu. If e = uv, then the edge e is said to join u and v. The number of vertices in a graph G is the order of G and the number of edges is the size of G. We often use n for the order of a graph and m for its size.
The first occurrence of graph in the Mathematical history is considered to be the classical “Konigsberg Bridge Problem”. The problem is stated - by the great mathematician L. Euler who lived in Konigsberg - as below: “Konigsberg is divided into four parts by river Pregel and connected by seven bridges. Is it possible to tour Konigsberg along a path that crosses every bridge once and only once and return to the starting point?” This question led to the emergence of graph theory.
Graph Theory is the study of graphs which are mathematical structures used to model pairwise relations between objects from a certain collection. Graphs are among the most ubiquitous models of both natural and human-made structures. Its study has had wide spread ramifications due to applications in many other fields of study like Physics, Chemistry, Computer Science (algorithm and computation), Social Science, Linguistics, Biology, Biochemistry, Cartography, Engineering, Operations Research (scheduling) etc. and within Mathematics as well.
Graph coloring is one of the oldest concepts in graph theory; it has preoccupied large number of people as a distraction puzzle during the 19th century and later in the framework of scientific research. Since this conception exhibits a significant interest from a theoretical and practical point of view, many applications are modeled and investigated with the use of graph coloring. Because of the technology evolution, new problems arise that can be expressed effectively by handling invariants that are the generalization of graph coloring.
Graphs can also be used to model many puzzle games like Sudoku. Sudoku is a puzzle game that has become very popular as many newspapers carry it as a daily feature. It is a number placement puzzle which involves completely filling a 9 × 9 grid with numbers from 1 to 9 satisfying certain conditions. In this chapter, mathematical model of the Sudoku Puzzle game is introduced using graphs.
For the reason of reliability of this project and from the fact that graph terminologies and notation is not yet nullified, we give in section 1.4 definitions of the terms used in subsequent pages.
1.2 Aim and Objectives of the Study
The aim of this project is to study the application of graph theory on Sudoku. This aim will be achieved through the following objectives:
i. To study graph (vertex) coloring
ii. To convert Sudoku puzzles into a vertex coloring problem
iii. To compute the total number of solution to a Sudoku puzzle.
1.3 Scopes and Limitation of the Study
There are many aspects of graph related to coloring and their applications in diverse fields of study. Some of which includes vertex coloring, edge coloring, map coloring, list coloring and so on. It will be difficult to cover everything under graph coloring. This project is concerned with the application of vertex coloring on a Sudoku puzzle.
1.4 Definition of Basic Terms
1.4.1 Graph
Definition 1.1
An ordered pair of a finite non-empty set V and a prescribed set E of unordered pairs of distinct elements of V is defined to be a graph. It is also a set of dot or point connected by lines. Mathematically, G = (V, E) is a graph if
|V| < ∞, V ≠ ø and E ⊆ {{u, v}|u, v ∈ V and u ≠ v} .
Definition 1.2
Let G = (V, E) be a graph. An element of V is called a vertex and an element of E is called an edge of the graph G. Vertices a and b are said to be adjacent, denoted as a adjv b, if {a, b} is an edge in E. Distinct edges x and y are said to be adjacent, denoted as x adje y, if they share a common vertex (that is x ∩ y 6= φ). A vertex a and an edge x of graph G are said to be incident to each other, denoted as a incG x (or x incG a), if a ∈ x. A graph with p number of vertices and q number of edges is called a (p, q) graph. So G = (V, E) is a (|V|, |E|) graph, where | | represents cardinality.
Remark 1.3
Graphs can be visualized with their diagrammatic representations. Let G = (V, E) be a graph. Represent the vertices in V by distinct geometric points in the plane. Label the points by the name of the vertex they represent. Draw a line segment (could be a curve) connecting two points labeled u and v if u adjV v. Label the line as {u, v}, thus representing the edge {u, v} ∈ E. This way we get a diagrammatic representation of G.
A (4, 5) graph G = ({a, b, c, d}, {{a, b}, {a, c}, {b, c}, {b, d}, {c, d}}).
Fig 1.1: Diagrammatic representation of (4,5) graph
Remark 1.4
Diagrammatic representation of graphs is just a means to visualize graphs. There cannot be multiple lines joining the same two points or a line starting and ending at the same point (no loops) in a graph.
1.4.2 Types of Graph
1 Simple Graph: A graph is simple if it has neither self-looped nor multiple edges.
2 Trivial Graph: A graph is trivial if it has one vertex and no edges.
3 Directed Graph (Digraph): This is a graph each of whose edge is an ordered pair. i.e. (uv ≠ vu)
4 Complete Graph: This is a graph of order n with each vertex v in V(G) is adjacent to every other vertex in V(G) and is often denoted by Kn.
5 Regular Graph: This is a graph whose vertices have equal degrees i.e. it is regular of same degree r. A r-regular graph (or regular of degree r) is a regular of order n and degree r if for all v in V(G), dG(v) = r
6 Connected Graph: A graph is connected if for every u,v in V(G), there is a path from u to v. Otherwise, it is disconnected.
7 Bipartite Graph: This is a graph whose vertex set can be partitioned into two parts X & Y (i.e. V(G) = X ∪ Y & X ∩ Y = ∅) such that the set is given by: E(G) = {xy | x ∈ X, y ∈ Y}.
1.4.3 Sudoku
Definition 1.5
A cell is a unit square in R^2 plane which can contain at most one integer in its interior. An integer that a cell contains is called the entry of that cell. If a cell contains an entry then it is called a filled cell, else it is called an empty cell.
Empty Cell Filled Cell
Fig 1.2: Types of cell in Sudoku
Definition 1.6
An m×n grid is an array of mn cells consisting m rows and n columns (m,n ∈ N). The cell in the ith row and jth column of a m×n grid G with i ∈ {0, 1, 2, ..., m−1} and j ∈ {0, 1, 2, ..., n−1} is denoted as (i, j)G or simply (i, j) if the grid being referred to is understood.
Note that we are starting the numbering of the rows and columns from 0 onwards. The ith row of m×n grid G, denoted as RG(i), is the set of cells {(i, j)G| j ∈ {0, 1, 2, ..., n−1}} and the jth column of G, denoted as CG(j) is the set of cells {(i, j)G| i ∈ {0, 1, 2, ..., m−1}}. Given a m×n grid G, the entry in the cell (i, j)G with i ∈ {0, 1, 2, ..., m−1} and j ∈ {0, 1, 2, ..., n−1} is denoted by E(i, j)G. If (i, j)G is a empty cell then define E(i, j)G = ∅.
Fig 1.3: A 3 x 7 grid G
Definition 1.7
A Sudoku puzzle G of rank n is said to be a Filled Sudoku of rank n if all its cells are filled with integers from 1 to n2 satisfying the conditions of no repetition of integers in same row, column and block. G is called an Empty Sudoku of rank n if all its cells are empty, i.e. it is just the n2 × n2 grid Xn with no entries.
Fig 1.4: Sudoku Puzzle of Rank 2
Fig 1.5: Filled Sudoku of Rank 2
Theorem 1.8
A Filled Sudoku of rank n exists for every n ∈ N. i.e. (i,j) = (i∗,j∗). Thus we get a Filled Sudoku of rank n, for arbitrary n ∈ N.
Definition 1.9
A Filled Sudoku of rank n, say FP, is said to be a solution of Sudoku puzzle P of rank n if entry of every filled cell (i, j)P of P is equal to the entry of the same cell (i, j)FP in FP. Mathematically, if
∀ i, j ∈ {0, 1, ..., n2 − 1}; E(i, j)P ≠ φ =⇒ E(i, j)P = E(i, j)FP
then filled Sudoku FP is called a solution of the Sudoku Puzzle P.
In other words, FP is a solution of P if it preserves the initial entries given in P. For instance, the Filled Sudoku of rank 2 shown in fig 1.5 is solution of the Sudoku puzzle of rank 2 in fig 1.4.
Definition 1.10
Latin Square of rank n is a n × n grid of filled cells consisting entries from {1, 2, ..., n} such that any two cells consisting same entry do not lie in the same column and row. Mathematically, let L be a n×n grid. If ∀ i, i∗, j, j∗ ∈ {0, 1, ..., n − 1} we get,
1. E(i, j)L ∈ {1, 2, ..., n}, i.e. all cells are filled and
2. E(i, j)L = E(i∗, j∗)L with (i, j) ≠ (i∗, j∗) =⇒ i ≠ i∗ , j ≠ j∗ (No repetition of digits in rows and columns).
Then, L is a Latin square.
Remark 1.11
1. Set of all Filled Sudoku of rank n ⊂ Set of all Sudoku puzzles of rank n.
2. Set of all Filled Sudoku of rank n ⊂ Set of all Latin Squares of rank n2.
Reason:
For (1). Filled Sudoku satisfy all conditions to be a Sudoku puzzle. Sudoku grid with each cell empty is also a Sudoku puzzle but it is not a Filled Sudoku, hence the proper subset in statement (1).
For (2). Filled Sudoku of rank n satisfies the conditions to be a Latin Square of rank n2. Consider a n2 × n2 grid G where E(i, j)G = Rem(i+j, n2), ∀ i, j ∈ {0, 1, ..., n2 − 1}. G is a Latin Square but not a Filled Sudoku. Thus we get the proper subset in statement (2).
1.4.4 Graph of Sudoku
Let Xn be a Sudoku grid of rank n. Graph of Xn, denoted as GXn, is (V, E) where V = {(i, j)Xn | i, j ∈ {0, 1, ..., n2−1}} is set of all cells of Xn and E = {{(i, j)Xn ,(i∗ , j∗ )Xn }|(i, j)Xn ≠ (i∗ , j∗)Xn and either i = i∗ or j = j∗ or ⌊i/n⌋ = ⌊i∗/n⌋, ⌊j/n⌋ = ⌊j∗/n⌋}. In other words, cells of Sudoku grid form the vertices of its graph and two cells are adjacent if they are either in the same row or column or block of Xn.
Theorem 1.12
Let GXn = (V, E) be graph of Sudoku grid Xn, then GXn is a regular (n4,3n6/2 − n5 − n4/2) graph of degree 3n2 − 2n − 1.
Proof.
V = {(i, j)Xn |i, j ∈ {0, 1, ..., n2 − 1}}. i and j can take n2 possible values each. By counting principle (Appendix 1), |V| = n2 × n2 = n4 . Consider an arbitrary vertex (io, jo)Xn ∈ V. It is adjacent to other cells (vertices) in the row RXn (io)\{(io, jo)Xn } = {(io, j)Xn |j ∈ {0, 1, ..., n2−1}\{jo}}, column CXn (jo)\{(io, jo)} = {(i, jo)Xn |i ∈ {0, 1, ..., n2−1}\{io}} and remaining vertices of the block BXn (⌊io/n⌋, ⌊jo/n⌋). We get n2 −1 adjacent vertices each from RXn (io) \ {(io, jo)Xn } and CXn (jo) \ {(io, jo)} and (n − 1)(n − 1) left out vertices in the block.
Therefore,
degGXn ((io, jo)) = n2 − 1 + n2 − 1 + ((n − 1)(n − 1)) = 3n2 − 2n − 1.
Since the vertex is arbitrary, therefore GXn is regular graph of degree 3n2 − 2n − 1.
By ∑v∈G degG(v) = 2q and regular graph of degree r having p vertices has pr/2 edges, we get the required result. Also, graph of Sudoku grid of rank 3 is a (81, 810) regular graph of degree 20.
1.4.5 Graph Coloring
Given a graph G = (V, E), a function f : V −→ {1, 2, ..., λ} is called a λ−colouring of G. If U is a non-empty subset of V (U ⊂ V and U ≠ ∅) then a function g : U → {1, 2, ..., β} is called a β−partial colouring of G. f(v) is called the colour of v in the colouring f of G. These functions, as the name suggest, indeed represent coloring (in literal sense) of the diagrammatic representation of a graph where vertices can be thought to be coloured or labelled by at most λ colours in a λ−coloring.
For the graph below, let f be a 3 − partial colouring such that
f(v1) = f(v2) = 1 (red colour),
f(v3) = f(v4) = 2 (blue colour),
f(v5) = 3 (green colour)
and v6 is uncoloured.
Fig 1.6: A 3-partial coloring
A λ−coloring (or partial coloring) f of a graph G = (V, E) is said to be proper if f(u) ≠ f(v) whenever u adjV v. In other word, adjacent vertices are not colored the same.
1.4.6 Chromatic Number
Let G = (V, E) be a graph. If there exists an integer λ such that there is a proper λ−colouring of G and there does not exist any proper n−colouring of G for all n < λ, then λ is called the Chromatic number of G denoted by χ(G). It is also the minimum number of different colors require for a proper vertex coloring of G. A graph G is (vertex) k-chromatic if χ(G) = k. The 3-coloring (blue, red and green) shows that the graph G is 3-colorable, which means that χ(G) = 3. However, if the graph G contains three manually adjacent vertices, then it is not 2-colorable. Thus, G is three chromatic.
Given a proper χ(G)−partial colouring of a graph G, finding its solution is a graph theoretic problem called colouring problem. A Sudoku puzzle P of rank n, graph theoretically, is identical to the pair (GXn, f) where GXn is graph of Sudoku grid and f defined in terms of entries of filled cells in Sudoku puzzle as f(i, j)GXn = E(i, j)P is the proper χ(GXn) = n2−partial colouring. Entries of P are the colours of f. Finding a solution of P is to find a Filled Sudoku FS that preserves the entries of P. Finding a solution of (GXn, f) is to find (GXn, g) where g is a proper n2−colouring that preserves the colouring of f where entries of FS are colours of g. Thus, Sudoku is a special case of Colouring Problem (of finding solutions to proper partial colourings of GXn graph only).
Let 1 = Red, 2 = Blue, 3 = Green and 4 = Yellow. Solving a Sudoku puzzle of rank 2 is same as solving the proper partial colouring of GX2 as shown below.
Fig 1.61: Vertex Colouring
Fig 1.62: Sudoku Board Representation
Click “DOWNLOAD NOW” below to get the complete Projects
FOR QUICK HELP CHAT WITH US NOW!
+(234) 0814 780 1594
Login To Comment