Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Suduko guide IJCSI International Journal of Computer Science Issues Vol Issue No March ISSN Print - ISSN Online - www IJCSI org An Exhaustive Study on di ?erent Sudoku Solving Techniques Arnab Kumar Maji Sunanda Jana Sudipta Roy and Rajat Kumar Pal Depart

IJCSI International Journal of Computer Science Issues Vol Issue No March ISSN Print - ISSN Online - www IJCSI org An Exhaustive Study on di ?erent Sudoku Solving Techniques Arnab Kumar Maji Sunanda Jana Sudipta Roy and Rajat Kumar Pal Department of Information Technology North Eastern Hill University Shillong Meghalaya India Department of Computer Science and Engineering Haldia Institute of Technology Haldia West Bengal India Department of Information Technology Assam University Silchar Assam India Department of Computer Science and Engineering University of Calcutta Kolkata West Bengal India Abstract ? Sudoku ? is the Japanese abbreviation of a longer phrase ? Suuji wa dokushin ni kagiru ? meaning ? the digits must remain single ? It is a very popular puzzle that trains our logical mind There are several approaches to solve this well-liked puzzle In any case the problem of solving a given Sudoku puzzle ?nds numerous applications in practice In this paper an exhaustive study has been made on di ?erent techniques for solving a Sudoku puzzle Keywords Sudoku puzzle Cell Minigrid Elimination Backtracking Introduction A Sudoku is usually a ? grid based puzzle problem which is subdivided into nine ? minigrids wherein some clues are given and the objective is to ?ll it up for the remaining blank positions Furthermore the objective of this problem is to compute a solution where the numbers through will occur exactly once in each row exactly once in each column and exactly once in each minigrid independently obeying the given clues One such problem instance is shown in Figure a and its solution is shown in Figure b Figure a An instance of the Sudoku problem b A solution of this Sudoku instance shown in Figure a Solving an instance of Sudoku problem is NP-complete So it is unlikely to develop a deterministic polynomial time algorithm for solving a Sudoku instance of size n? n where n is any large number such that the square root of n is an integer But incidentally when the value of n is bounded by some constant solutions may be obtained in reasonable amount of time TABLE I Number of clues given in a Sudoku puzzle in de ?ning the level of di ?culty of a Sudoku instance Di ?culty Level Number of Clues Extremely Easy More than Easy - Medium - Di ?cult - Evil - TABLE II The lower bound on the number of clues given in each row and column of a Sudoku instance for each corresponding level of di ?culty Di ?culty Level Lower Bound on the Number of Clues in Each Row and Column Extremely Easy Easy Medium Di ?cult Evil There are quite a few logic techniques that researchers use to solve this problem Some are basic simple logic some are more advanced Depending on the di ?culty of the puzzle a blend of techniques may be needed in order to solve a puzzle In fact most computer generated Sudoku puzzles rank the di ?culty based upon the number of