Computer solutions

For computer programmers it is relatively simple to build a backtracking search. Typically this would assign a value (say, 1, or the nearest available number to 1) to the first available cell (say, the top left hand corner) and then move on to assign the next available value (say, 2) to the next available cell. This continues until a duplication is discovered in which case the next alternative value is placed in the last field changed. Although far from computationally efficient, this method will find the solution, given sufficient computation time. A more efficient program could keep track of potential values for cells, eliminating impossible values until only one value remains for a cell, then filling that cell in and using that information for more eliminations, and so on until the puzzle is solved. This more closely emulates the way a human would solve the puzzle without resorting to guesses.

Coding the search for impossibilities based on contingencies and even multiple contingencies (as would be required for the hardest of Sudoku) is quite complex to construct by hand. However, such complications are unnecessary if all the programmer wishes to do is find a solution efficiently. A more efficient way to find solutions involves the use of finite domain constraint programming. A constraint program requires the programmer only to specify the constraints on the solution (the fact that every number in each row, each column, and each 3x3 subgrid must be unique, and the provided "givens"); the finite domain solver does all the work of propagating additional information about possible values to narrow down the solution space until a unique solution is found. The self-imposed constraints of most Sudoku puzzle publishers even ensures that the backtracking search capabilities of the finite domain solver are not required.

Elaborate, hand-crafted solvers have been designed that apply scanning and marking up in a manner similar to human solvers. This allows these solvers to estimate the difficulty for a human to find the solution, based on the complexity of the rules required by the computer.

Difficulty ratings

Published puzzles often are ranked in terms of difficulty. Surprisingly, the number of givens has little or no bearing on a puzzle's difficulty. A puzzle with a minimum number of givens may be very easy to solve, and a puzzle with more than the average number of givens can still be extremely difficult to solve. It is based on the relevance and the positioning of the numbers rather than the quantity of the numbers.

Computer solvers can estimate the difficulty for a human to find the solution, based on the complexity of the solving techniques required. This estimation allows publishers to tailor their Sudoku puzzles to audiences of varied solving experience. Some online versions offer several difficulty levels.

Wikipedia, the free encyclopedia.