Please use this identifier to cite or link to this item:
Title: Design and Analysis of an Efficient Guessed Free Sudoku Solver
Researcher: Arnab Kumar Maji
Guide(s): Rajat Kumar Pal and Sudipto Roy
Keywords: Sudoku, Puzzle, Cell, Minigrid, Difficulty Level, Permutation, Algorithm, Graph Theory, Application, Instance, Steganography, Biometric, Template
University: Assam University
Completed Date: 
Abstract:  Sudoku is the Japanese abbreviation of a longer phrase, Suuji wa dokushin ni kagiru , newlinemeaning the digits must remain single . It is a fascinating numeric enigma that trains our newlinerational mind. Solving a Sudoku puzzle requires no mathematics. On the contrary, the game newlineinitiates a number of stimulating mathematical problems. Applications of solving a Sudoku newlineinstance are found in the various fields of Steganography, Secret image sharing with necessary reversibility, Encrypting SMS, Digital watermarking, Image authentication, Image Encryption, Enhancement of genome sequence in DNA, Track maintenance through cooperating agents, and so on and so forth. newlineAll the earlier existing Sudoku solvers that are available in literature (including Internet) are newlineeither entirely guess based heuristics or computation intensive soft computing methodologies, newlineand hence, extremely time consuming. In addition, each of these existing solvers solves an newlineinstance of the problem considering the clues one-by-one for each of the blank locations. Often guessing may not be guided by selecting a desired path of computing a solution, and hence, exhaustive redundant computations are involved over there. newlineUsually Sudoku instances are available in literature based on their classification of different newlinelevels of difficulty like easy, moderate, diabolical, evil, etc. These classifications are based on the algorithmic approaches developed and executed in solving different Sudoku instances. newlineSometimes, it is told that the instances are easier or harder based on the number of clues given along with their relative locations in a given instance but there is no concrete proof to support such claims. newlineOften a Sudoku instance is defined that it has one and only one valid solution. But, in general, a Sudoku instance might have two or more solutions as well though each of the existing solvers computes only one of them. There is no assessment in the existing techniques in literature to make sure whether an instance is, in fact, having a valid solution or there exist two or more solutions of the given Sudoku puzzle. Also, none of the existing Sudoku solvers used graph theory as a tool to compute all valid solutions of a given Sudoku instance, or declare if there is no solution (or the given instance is not valid). newlineIn this thesis, we have developed a minigrid based guessed free Sudoku solver which is a more deterministic algorithmic approach in the sense that redundancy is drastically reduced in this process of computations involved and that it always guarantees a solution, if it exists in a reasonable amount of time. The Sudoku solver developed in this thesis does not differentiate the instances in terms of any level of difficulty, and each of the instances is equally easy or hard to solve using our approach, if a reasonable number of clues are given. It computes solution(s) if it exists without guessing a possible value in a blank location and primarily minigrid based irredundant deterministic computations are involved over there. newlineLater on, inter-minigrid valid combinations are computed in some fashion, either following newlinespiral, or zigzag, or semi-spiral sequence of considering all the minigrids to compute a desired solution. At the end, in developing the algorithm, we have generalized the approach based on a graph theoretic formulation wherein we have proved that the modified comprehensive innovation is able to generate all valid solutions of a given Sudoku instance, if there be one or more such solutions. Even the algorithm is capable to detect Sudoku puzzles that are not valid. We have also explored several domains of application of our devised solver and developed algorithms for preventing unauthorized modifications in the field of Steganography and Biometric template encryption. Algorithms for generating a large number of Sudoku instances have also been designed in this thesis. newline
Appears in Departments:Department of Information Technology

Files in This Item:
File Description SizeFormat 
th-1811_appendix.pdfAttached File5.04 MBAdobe PDFView/Open
th-1811bib.pdf171.96 kBAdobe PDFView/Open
th-1811ch1.pdf776.95 kBAdobe PDFView/Open
th-1811ch2.pdf1.31 MBAdobe PDFView/Open
th-1811ch3.pdf620.09 kBAdobe PDFView/Open
th-1811ch4.pdf297.53 kBAdobe PDFView/Open
th-1811ch5.pdf817.83 kBAdobe PDFView/Open
th-1811ch6.pdf828.39 kBAdobe PDFView/Open
th-1811ch7.pdf137.09 kBAdobe PDFView/Open
th-1811_content.pdf666.71 kBAdobe PDFView/Open

Items in Shodhganga are protected by copyright, with all rights reserved, unless otherwise indicated.