Sudoku solving algorithms

Some hobbyists have developed computer programs that will solve Sudoku puzzles using a backtracking algorithm, which is a type of brute force search.

Although it has been established that approximately 5.96 x 1026 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.

The puzzle's clues (red numbers) 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 fulfill the constraints of the Sudoku.

[8][9] A 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.

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.

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.

And 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.

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).

Approaches for shuffling the numbers include simulated annealing, genetic algorithm and tabu search.

However, for proper Sudokus, linear programming presolve techniques alone will deduce the solution without any need for simplex iterations.

[15][16] If the code employs a strong reasoning algorithm, incorporating backtracking is only needed for the most difficult Sudokus.