Sudoku is the name given to a type of logic puzzle similar in concept to a crossword puzzle. It is based on a 9×9 grid composed of nine 3×3 subgrids, where each grid box can contain a single digit from 1 to 9. Initially, most of the grid is blank, with a dozen or so boxes already filled in. The object is to complete the entire grid in such a way that each 9-box column, each 9-box row, and each 9-box subgrid contains each digit 1 through 9 exactly once. The definition of the puzzle is deceptively simple, allowing for the construction of puzzles of a wide range of difficulty.
If you’ve solved some Sudoku puzzles, you know the kind of thinking that is involved in arriving at the (usually unique) solution. Applying logic at each stage can solve some puzzles completely methodically. Others have “branch points” where a digit choice must be made that is not determined logically, but is instead selected at random from the remaining possibilities. The simplest method of solving Sudoku is to mark all the possible values (1- 9) a square can have. Then on the basis of ‘principle of uniqueness’ discard the numbers that cannot be filled in that square.
When a square is remained with only one number or a number is such that it cannot be in other squares of the row or column or box corresponding to the square, fill the number and remove the possibility of the number from squares of the row, column and box belonging to the recently filled square. Preceding in this manner a unique number can be found for all squares. Objective: The objective of the project is to create a Sudoku puzzle and let the user to insert logic integers (1-9) and try to solve the puzzle. The solution would be shown at the end.
User Requirements Specification: To create a Sudoku puzzle, the user is required to enter logic integers in some of the cells in the grid. Each cell can only have one specific value. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes contain the digits from 1 to 9. Depending on the difficulty, there are different strategies to solve the puzzle. Once the user has filled the suitable cells in the grid, the program should be able to fill each of the other cells in the grid with the appropriate logic integer to solve the puzzle.
The program should be able to use techniques of reducing possibilities to recognize where digits should be placed. Strategies to solve the puzzle: The strategy for solving a puzzle may be regarded as comprising a combination of three processes: scanning, marking up, and analyzing. Scanning: Scanning is performed at the outset and throughout the solution. Scans need to be performed only once in between analyses. Scanning consists of two techniques as follows:
Cross-hatching: the scanning of rows to identify which line in a region may contain a certain numeral by a process of elimination. The process is repeated with the columns. For fastest results, the numerals are scanned in order of their frequency, in sequential order. It is important to perform this process systematically, checking all of the digits 1–9. Counting 1–9 in regions, rows, and columns to identify missing numerals: Counting based upon the last numeral discovered may speed up the search.
It also can be the case, particularly in tougher puzzles, that the best way to ascertain the value of a cell is to count in reverse that is, by scanning the cell’s region, row, and column for values it cannot be, in order to see what remains. Marking up: Scanning stops when no further numerals can be discovered, making it necessary to engage in logical analysis. One method to guide the analysis is to mark candidate numerals in the blank cells. There are two popular notations: subscripts and dots.
Subscripts : In the subscript notation the candidate numerals are written in subscript in the cells. Because puzzles printed in a newspaper are too small to accommodate more than a few subscript digits of normal handwriting, solvers may create a larger copy of the puzzle. Dots: The second notation uses a pattern of dots in each square, where the dot position indicates a number from 1 to 9. The dot notation can be used on the original puzzle. Dexterity is required in placing the dots, since misplaced dots or inadvertent marks inevitably lead to confusion and may not be easily erased.
Analysis: The two main approaches to analysis are “candidate elimination” and “what-if”. Candidate elimination: In candidate elimination, progress is made by successively eliminating candidate numerals from cells to leave one choice. After each answer has been achieved, another scan may be performed usually checking to see the effect of the contingencies. In general, if entering a particular numeral prevents completion of the other necessary placements, then the numeral in question can be eliminated as a candidate. One method works by identifying matched cell groups.
For instance, if precisely two cells within a scope (a particular row, column, or region) contain the same two candidate numerals or if precisely three cells within a scope contain the same three candidate numerals these cells are said to be matched. The placement of those candidate numerals anywhere else within that same scope would make a solution impossible; therefore, those candidate numerals can be deleted from all other cells in the scope. What-if: In the what-if approach a cell with two candidate numerals is selected, and a guess is made.
The steps are repeated until a duplication is found or a cell is left without a possible candidate, in which case the alternative candidate must be the solution. For each cell’s candidate, the question is posed and if entering a particular numeral prevent completion of the other placements of that numeral, then that candidate can be eliminated. If the what-if exercises for both candidates show that either one is possible, another pair should be tried. Alternatively, if the what-if exercises for both candidates imply an identical result, then that result must be true.