In one case, a programmer found a brute force program required six hours to arrive at the solution for such a Sudoku (albeit using a 2008-era computer). Thus the program would spend significant time "counting" upward before it arrives at the grid which satisfies the puzzle. Assuming the solver works from top to bottom (as in the animation), a puzzle with few clues (17), no clues in the top row, and has a solution "987654321" for the first row, would work in opposition to the algorithm. By testing every questionable pattern against all the reduced sets that were already accepted for the other symbols the total number of patterns left for backtracking is greatly diminished.Īnd as with all sudoku brute-force techniques, run time can be vastly reduced by first applying some of the most simple solving practices which may fill in some 'easy' values.Ī Sudoku can be constructed to work against backtracking. Significant optimization can be achieved by reducing the sets of patterns even further during filtering. The Implementation is exceptionally easy when using bit vectors, because for all the tests only bit-wise logical operations are needed, instead of any nested iterations across rows and columns. In the last step, the actual backtracking part, patterns from these sets are tried to be combined or overlayed in a non-conflicting way until the one permissible combination is hit upon. ![]() Then every given symbol gets assigned a filtered set with those patterns, which are in accordance with the given clues. In manual sudoku solving this technique is referred to as pattern overlay or using templates and is confined to filling in the last values only.Ī library with all the possible patterns may get loaded or created at program start. Ī different approach which also uses backtracking, draws from the fact that in the solution to a standard sudoku the distribution for every individual symbol (value) must be one of only 46656 patterns. One programmer reported that such an algorithm may typically require as few as 15,000 cycles, or as many as 900,000 cycles to solve a Sudoku, each cycle being the change in position of a "pointer" as it moves through the cells of a Sudoku. The disadvantage of this method is that the solving time may be slow compared to algorithms modeled after deductive methods. The algorithm (and therefore the program code) is simpler than other algorithms, especially compared to strong algorithms that ensure a solution to the most difficult puzzles.Solving time is mostly unrelated to degree of difficulty.A solution is guaranteed (as long as the puzzle is valid).Notice that the algorithm may discard all the previously tested values if it finds the existing set does not fulfil the constraints of the Sudoku. The puzzle's clues (red numbers) remain fixed while the algorithm tests each unsolved cell with a possible solution. The animation shows how a Sudoku is solved with this method. This is repeated until the allowed value in the last (81st) cell is discovered. ![]() The value in that cell is then incremented by one. If a cell is discovered where none of the 9 digits is allowed, then the algorithm leaves that cell blank and moves back to the previous cell. ![]() When checking for violations, if it is discovered that the "1" is not allowed, the value is advanced to "2". If there are no violations (checking row, column, and box constraints) then the algorithm advances to the next cell and places a "1" in that cell. Briefly, a program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. Although it has been established that approximately 5.96 x 11 26 final grids exist, a brute force algorithm can be a practical method to solve Sudoku puzzles.Ī brute force algorithm visits the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid. Backtracking is a depth-first search (in contrast to a breadth-first search), because it will completely explore one branch to a possible solution before moving to another branch. Some hobbyists have developed computer programs that will solve Sudoku puzzles using a backtracking algorithm, which is a type of brute force search.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |