 | ||
A standard Sudoku puzzle contains 81 cells, in a 9 by 9 grid, and has 9 zones, each zone being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns. Each cell may contain a number from one to nine; each number can only occur once in each zone, row, and column of the grid. At the beginning of the game, many cells begin with numbers in them, and the goal is to fill in the remaining cells. Players may use a wide range of strategies to solve Sudoku puzzles, and this article goes over a number of methods for doing so.
Contents
Brute Force Algorithm (Backtracking)
Some hobbyists have developed computer programs that will solve Sudoku puzzles using a brute force algorithm. Although it has been established that approximately 6.67 x 1021 final grids exist, a brute force computer algorithm can be a practical method to solve puzzles if the code is well designed.
A 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. Briefly, a brute force program would solve a puzzle by placing the digit "1" in the first cell and checking if it is allowed to be there. 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. When checking for violations, if it is discovered that the "1" is not allowed, the value is advanced to "2". 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. The value in that cell is then incremented by one. This is repeated until the allowed value in the last (81st) cell is discovered.
The animation shows how a Sudoku is solved using backtracking. The puzzle's clues (red numbers) remain fixed while the algorithm tests each unsolved cell with a possible solution (blue numbers). Notice that the algorithm will discard all the previously tested values if it finds the existing set of values do not fulfil the constraints of the Sudoku.
Advantages of this method are:
The disadvantage of this method is that the solving time may be comparatively slow compared to algorithms modeled after deductive methods.
Exact cover
Sudoku puzzles may be described as an exact cover problem. This allows for an elegant description of the problem and an efficient solution. Modeling Sudoku as an exact cover problem and using an algorithm such as Dancing Links will typically solve a Sudoku in a few seconds.
Stochastic search / optimization methods
Sudoku can be solved using stochastic (random-based—search) methods. An example of this approach is to:
- Randomly assign numbers to the blank cells in the grid
- Calculate the number of errors
- "Shuffle" these inserted numbers around the grid until the number of mistakes is reduced to zero
A solution to the puzzle will then have been found. Approaches for shuffling the numbers include simulated annealing, genetic algorithm and tabu search. Stochastic-based optimisation algorithms are known to be quite fast, though they are perhaps not as fast as some logic-based techniques. Unlike the latter however, optimisation algorithms do not necessarily require problems to be logic-solvable, giving them the potential to solve a wider range of problem instance. Algorithms designed for graph colouring are also known to perform very well with Sudoku puzzles.
It is also possible to express a Sudoku as an integer linear programming problem. Such approaches seem to get close to a solution quite quickly, and can then use branching towards the end. The Simplex algorithm seems able to handle situations with no solutions or multiple solutions quite well.
Constraint programming
Sudoku is a constraint problem. In his paper Sudoku as a Constraint Problem, Helmut Simonis describes many reasoning algorithms available in the form of constraints which can be applied to model and solve the problem. Some constraint solvers include an example how to model and solve Sudoku problems. The constraint program modeling and solving Sudoku will in most solvers have less than 100 lines of code. If the code employs a strong reasoning algorithm, incorporating a search routine is only needed for the hardest puzzles.
Developing Sudokus (Computation time)
Computer programs are often used to "search" for Sudokus with certain properties, such as a small number of clues clues, or certain types of symmetry. An algorithm will usually require more cycles (longer time) when searching for Sudokus with 20 clues or fewer. Indeed, puzzles with 17 clues are notoriously difficult to find. When the constraint of symmetry is applied, the expected search time will dramatically increase yet further.