GRAPH THEORY: APPLICATION OF VERTEX COLORING IN SUDOKU
| Format: Ms Word | 1-5 Chapters | Table of Content|
INSTANT PROJECT MATERIAL DOWNLOAD
Study Level: BTech, BSc, BEng, BA, HND, ND or NCE
Amount: ₦4,000.00
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.. 1
INTRODUCTION.. 1
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.. 12
LITERATURE REVIEW… 12
2.0 Introduction. 12
CHAPTER THREE.. 15
CHROMATIC POLYNOMIAL OF SUDOKU.. 15
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.. 22
SUDOKU GAME SOLUTION USING VERTEX COLORING.. 22
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.. 30
SUMMARY, CONCLUSION AND RECOMMENDATIONS. 30
5.1Summary. 30
5.2 Conclusion. 30
5.3 Recommendations. 31
REFERENCES. 32
CHAPTER ONE
INTRODUCTION
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.
The aim of this project is to study the application of graph theory on Sudoku. This aim will be achieved through the following objectives:
- To study graph (vertex) coloring
- To convert Sudoku puzzles into a vertex coloring problem
- To compute the total number of solution to a Sudoku puzzle.
USE THIS MATERIALS AS A GUIDE FOR YOUR PERSONAL RESEARCH WORK (IF PROPERLY CITED)
PAY ₦4,000 HERE TO DOWNLOAD MATERIALS
Account Number: 0709546102
Access Bank: Savings
Account Name: Emmanuel Idorenyin Samuel.