We do this until we have a valid solution for the board. After we pick a random value for the selected cell, we go back to execute the 4 basic strategies again. This is the strategy to avoid the need of a backtracking algorithm. We do so, to avoid picking a random value to a cell with a high set of possible solutions, because this can cause cells with a short set of valid solutions to end up without any value. If the 4 strategies are applied, and no new solution for a cell is generated, and the Sudoku board is not complete, then this Sudoku has more than one solution, so we must use the random strategy.įirst, we determinate which cell has the minimum of possible valid values. If any of those strategies produces a solution, then the first strategy will be run again, until the Sudoku board is solved. To solve the puzzle, the application applies the 4 deterministic strategies, in the same order as shown before. If you don't write any initial value for any cell, the program will generate a random Sudoku board. The application shows in the main user interface a Sudoku board where you can place the initial values for the puzzle. This concept can be applied as well for each column and "square" to find other solutions. All of the other cells in this row cannot have this value, because of the cells with the red circles. The row marked can only host the value 2 in the grayed cell. If one of these values can only be placed into one cell in a specific row, then we have found a solution for that cell. This strategy consists of finding all the cells where each digit can be placed. Searching for Rows, Columns and "Squares" with a Unique Cell for a Specific DigitĮach row must have all the digits between 1 and 9. If you check, all the other values create a conflict with the cells with the red circles. The grayed cell can only have one valid solution: 7. This means that a cell has only one possible value according to the rules of the puzzle. This strategy consists of finding the list of all the possible values for a cell that don't have a conflict with the current values of the other cells. Searching for Cells with a Unique Solution Possible If the Sudoku puzzle has more than one solution, the last strategy is needed: Pick a Random value for the cell. In other words, if a Sudoku puzzle has only one solution, these 4 strategies are enough to find this solution. This 4 strategies have proven to be sufficient to solve any Sudoku puzzle with one solution. This programs applies the 4 first strategies into a loop. Pick a value randomly from the available valid values for a cell.Search for "squares" with a unique cell for an specific digit.Search for columns with a unique cell for an specific digit.Search for rows with a unique cell for an specific digit.Search for cells with a unique solution possible.The algorithm uses four strategies to determine a valid value for a cell in the Sudoku board. You cannot write the same digit in two or more cells of the same "square".You cannot write the same digit in two or more cells of the same column.You cannot write the same digit in two or more cells of the same row. The idea is to write a digit between 1 and 9 in each cell, but the game has some rules: Additionally, there are 9 groups of 3x3-matrixes (as shown above), that we call "squares" in this article. This matrix is composed of 9 rows and 9 columns, each with 9 cells. What is Sudoku?Īs shown in the image above, Sudoku consists in 81 cells, distributed in a 9x9 matrix. Several friends like this puzzle, but they spend much more time, so my wife has something! A week after, I share her advices to solve this puzzle with all of you, but in a language I understand. However, after seeing my wife spend 5 to 10 minutes every day solving the daily puzzle in the newspaper, I try to understand her strategy. First of all, I must confess that I'm not a fan of Sudoku.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |