Remerciez-le!

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

An Exhaustive Study on different Sudoku Solving Techniques Abstract ‘Sudoku’ is

An Exhaustive Study on different Sudoku Solving Techniques 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 finds numerous applications in practice. In this paper, an exhaustive study has been made on different techniques for solving a Sudoku puzzle. Keywords: Sudoku puzzle, Cell, Minigrid, Elimination, Backtracking. 1. Introduction A Sudoku is usually a 9×9 grid based puzzle problem which is subdivided into nine 3×3 minigrids, wherein some clues are given and the objective is to fill it up for the remaining blank positions. Furthermore, the objective of this problem is to compute a solution where the numbers 1 through 9 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 1(a) and its solution is shown in Figure 1(b). Figure 1. (a) An instance of the Sudoku problem. (b) A solution of this Sudoku instance (shown in Figure 1(a)). Solving an instance of Sudoku problem is NP-complete [4]. 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 [2, 3]. TABLE I. Number of clues given in a Sudoku puzzle in defining the level of difficulty of a Sudoku instance. Difficulty Level Number of Clues 1 (Extremely Easy) More than 46 2 (Easy) 36-46 3 (Medium) 32-35 4 (Difficult) 28-31 5 (Evil) 17-27 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 difficulty. Difficulty Level Lower Bound on the Number of Clues in Each Row and Column 1 (Extremely Easy) 05 2 (Easy) 04 3 (Medium) 03 4 (Difficult) 02 5 (Evil) 00 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 difficulty 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 difficulty based upon the number of empty cells in the puzzle and how much effort is needed to solve each of 5 1 4 6 8 7 9 4 4 9 8 1 4 3 5 1 3 6 8 3 1 8 5 2 7 4 1 4 9 3 7 5 2 6 8 3 8 7 6 9 2 5 1 4 2 6 5 1 4 8 7 9 3 5 1 2 8 9 6 7 3 4 6 8 4 3 7 1 9 5 2 9 7 3 4 2 5 1 6 8 7 4 1 2 3 6 8 5 9 9 5 3 4 8 7 6 2 1 8 2 6 5 1 9 4 3 7 4Department of Computer Science and Engineering,University of Calcutta, Kolkata, West Bengal 700 009, India Arnab Kumar Maji1, Sunanda Jana2, Sudipta Roy3, and Rajat Kumar Pal4 1Department of Information Technology, North Eastern Hill University, Shillong, Meghalaya 793 022, India 2Department of Computer Science and Engineering ,Haldia Institute of Technology, Haldia, West Bengal 721 657, India 3Department of Information Technology, Assam University, Silchar, Assam 788 011, India IJCSI International Journal of Computer Science Issues, Vol. 11, Issue 2, No 1, March 2014 ISSN (Print): 1694-0814 | ISSN (Online): 1694-0784 www.IJCSI.org 247 Copyright (c) 2014 International Journal of Computer Science Issues. All Rights Reserved. them. Table I shows a comparison chart of the number of clues for different difficulty levels [3]. However, position of each of the empty cells also affects the level of difficulty. If two puzzles have the same number of clues at the beginning of a Sudoku game, the puzzle with the givens (or clues) in clusters is graded in higher level than that with the givens scattered over the space. Based on the row and column constraints, the lower bound on the number of clues are regulated in each row and column for each difficulty level [3] as shown in Table II. In this paper, an attempt has been made to make an exhaustive study on the basic backtracking approach and other elimination based approaches for solving Sudoku puzzle. 2.Study on different Sudoku Solving Techniques A 9×9 Sudoku puzzle can be divided into nine 3×3 minigrids. We have labelled each minigrid from 1 to 9, with minigrid 1 at the top-left corner and minigrid 9 at the bottom-right corner; minigrid numbers are shown in faded larger font size in Figure 2. Also we refer to each cell in the grid by its row number followed by its column number, as shown in the same figure. Figure 2. The structure of a 99 Sudoku puzzle (problem) with its nine minigrids of size 33 each as numbered (in grey outsized font) 1 through 9. Representation of each cell of a Sudoku puzzle and some example givens (or clues coloured by red) in the remaining cells. So, the cells are [1,1] through [9,9], and the distinct cells may have some clues as well. Minigrid numbered 1 consists of the cell locations [1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], and [3,3], minigrid numbered 2 consists of the cell locations [1,4], [1,5], [1,6], [2,4], [2,5], [2,6], [3,4], [3,5], and [3,6], and so on. Now we review on the backtracking technique that has been adopted for solving Sudoku puzzles [3]. 2.1 Backtracking The basic backtracking algorithm works as follows. The program places number 1 in the first empty cell. If the choice is compatible with the existing clues, it continues to the second empty cell, where it places a 1 (in some other row, column, and minigrid). When it encounters a conflict (which can happen very quickly), it erases the 1 just placed and inserts 2 or, if that is invalid, 3 or the next legal number. After placing the first legal number possible, it moves to the next cell and starts again with a 1 (or a minimum possible acceptable value). If the number that has to be altered is a 9, which cannot be raised by one in a standard 99 Sudoku grid, the process backtracks and increases the number in the previous cell (or the next to the last number placed) by one. Then it moves forward until it hits a new conflict. In this way, the process may sometimes backtrack several times before advancing. It is guaranteed to find a solution if there is one, simply because it eventually tries every possible number in every possible location. This algorithm is very effective for size two puzzles. Unfortunately, for size three puzzles, there are nine possibilities for each cell. This means that there are roughly 981−n possible states that might need to be searched, where n×n is the size of a given puzzle. Obviously this version of backtracking search does not work for size 3 puzzles. Fortunately, there are several means by which this algorithm can be improved: constraint propagation, forward checking, and choosing most constrained value first [2] are some of them. Some other techniques include elimination based approach [3] and soft computing based approach [2]. Let us now focus to review the elimination based approach. In this approach, based on the given clues a list of possible values for every blank cell is first obtained. Then using the following different methods such as naked single, hidden single, lone ranger, locked candidate, twin, triplet, quad, X-wing, XY- wing, swordfish, coloring, we eliminate the multiple possibilities of each and every blank cell, satisfying the constraints that each row, column, and minigrid should have the numbers 1 through 9 exactly once. An instance of a Sudoku puzzle and its possible values of each blank cell are shown in Figures 3(a) and 3(b), respectively. 2.2 Naked single If there is only one possible value existing in a blank cell, then that value is known as a naked single [2]. After assigning the probable values for each blank cell, as shown in Figure 3(b), we obtain the naked singles 3, 9, and 3 at locations [5,2], [5,8], and [8,3], respectively. So, we can directly assign these values to these cells. Then we eliminate these digits (or naked singles) from each of the corresponding row, column, and minigrid. Hence, after elimination of these numbers, as stated above, we obtain a modified (reduced) status of each blank cell as shown in Figure 3(c), wherein several other naked singles could be found (and this process is recursive until no naked singles are found). 2.3 Hidden single Sometimes there uploads/Science et Technologie/ suduko-guide.pdf