A standard Sudoku contains 81 cells, in a 9×9 grid, and has 9 boxes, each box 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, and each number can only occur once in each row, column, and box. A Sudoku starts with some cells containing numbers, and the goal is to solve the remaining cells. Proper Sudokus have one solution. Players and investigators may use a wide range of computer algorithms to solve Sudokus, study their properties, and make new puzzles, including Sudokus with interesting symmetries and other properties. There are several computer algorithms that will solve most 9×9 puzzles in fractions of a second, but combinatorial explosion occurs as increases, creating limits to the properties of Sudokus that can be constructed, analyzed, and solved as increases.
Techniques
Backtracking
Some hobbyists have developed computer programs that will solve Sudoku puzzles using a backtracking algorithm, which is a type of brute force search. Backtracking is a depth-first search, because it will completely explore one branch to a possible solution before moving to another branch. Although it has been established that approximately 5.96 x 1126 final grids exist, a brute force algorithm can be a practical method to solve Sudoku puzzles. 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 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 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 cell is discovered. The animation shows how a Sudoku is solved with this method. The puzzle's clues remain fixed while the algorithm tests each unsolved cell with a possible solution. 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. Advantages of this method are:
The algorithm is simpler than other algorithms, especially compared to strong algorithms that ensure a solution to the most difficult puzzles.
The disadvantage of this method is that the solving time may be slow compared to algorithms modeled after deductive methods. 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. A Sudoku can be constructed to work against backtracking. Assuming the solver works from top to bottom, a puzzle with few clues, no clues in the top row, and has a solution "987654321" for the first row, would work in opposition to the algorithm. Thus the program would spend significant time "counting" upward before it arrives at the grid which satisfies the puzzle. In one case, a programmer found a brute force program required six hours to arrive at the solution for such a Sudoku. Such a Sudoku can be solved nowadays in less than 1 second using an exhaustive search routine and faster processors.
Sudoku can be solved using stochastic algorithms. An example of this method is to:
Randomly assign numbers to the blank cells in the grid.
Calculate the number of errors.
"Shuffle" the inserted numbers until the number of mistakes is reduced to zero.
A solution to the puzzle is then found. Approaches for shuffling the numbers include simulated annealing, genetic algorithm and tabu search. Stochastic-based algorithms are known to be fast, though perhaps not as fast as deductive 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 problems. Algorithms designed for graph colouring are also known to perform well with Sudokus. It is also possible to express a Sudoku as an integer linear programming problem. Such approaches get close to a solution quickly, and can then use branching towards the end. The simplex algorithm is able to solve non-proper Sudokus, indicating if the Sudoku is not valid, or providing the set of answers when there is more than one solution.
Constraint programming
A Sudoku may also be modelled as a constraint satisfaction problem. In his paper Sudoku as a Constraint Problem, Helmut Simonis describes many reasoning algorithms based on constraints which can be applied to model and solve problems. Some constraint solvers include a method to model and solve Sudokus, and a program may require less than 100 lines of code to solve a simple Sudoku. If the code employs a strong reasoning algorithm, incorporating backtracking is only needed for the most difficult Sudokus. An algorithm combining a constraint-model-based algorithm with backtracking would have the advantage of fast solving time, and the ability to solve all sudokus.
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. Modelling Sudoku as an exact cover problem and using an algorithm such as Knuth's Algorithm X will typically solve a Sudoku in a few milliseconds. An alternative approach is the use of Gauss elimination in combination with column and row striking.
Developing (searching for) Sudokus
Computer programs are often used to "search" for Sudokus with certain properties, such as a small number of clues, or certain types of symmetry. Over 49,000 Sudokus with 17 clues have been found, but discovering new distinct ones is becoming more difficult as undiscovered ones become more rare. One common method of searching for Sudokus with a particular characteristic is called neighbor searching. Using this strategy, one or more known Sudokus which satisfy or nearly satisfy the characteristic being searched for is used as a starting point, and these Sudokus are then altered to look for other Sudokus with the property being sought. The alteration can be relocating one or more clue positions, or removing a small number of clues, and replacing them with a different number of clues. For example, from a known Sudoku, a search for a new one with one fewer clues can be performed by removing two clues and adding one clue in a new location.. Each new pattern would then be searched exhaustively for all combinations of clue values, with the hope that one or more yields a valid Sudoku. Methods can also be employed to prevent essentially equivalent Sudokus from being redundantly tested. As a specific example, a search for a 17-clue Sudoku could start with a known 18-clue Sudoku, and then altering it by removing three clues, and replacing them with only two clues, in different positions. This may discover new Sudokus, but there would be no immediate guarantee that they are essentially different from already known Sudokus. If searching for truly new Sudokus, a further confirmation would be required to ensure each find is not a transformation of an already known Sudoku.
