Sudoku solving algorithms

Sudoku puzzles are generally designed to be solved by human players with pencil and paper. Such players may use a range of broad strategies, but there are also a wide range of step-by-step algorithms that have been developed. These are typically used to allow computers to both produce solutions, and rate the difficulty of a particular puzzle.

Techniques

Backtracking

The basic backtracking algorithm can be adapted to solve Sudokus. A standard Sudoku contains 27 zones, namely 9 rows, 9 columns and 9 squares that are 3 x 3. In a jigsaw Sudoku, the square zones are replaced by zones having irregular boundaries, like a jigsaw piece.

One possible algorithm that uses backtracking to solve such Sudokus constructs a graph with one vertex for each box of the grid. This algorithm was used to solve a 10x10 jigsaw Sudoku that was proposed on Les-Mathematiques.net. Narrowing the range of the numbers of a box can be used in improving backtracking solutions efficiently.^{[citation needed]}

You can refer the following link for recursive/backtracking algorithm - Lecture 11 | Programming Abstractions (Stanford)

Exact cover

Main article: Exact cover#Sudoku

Sudoku may be described as an instance of the exact cover problem. This allows both for an elegant description of the problem and an efficient solution using a backtracking algorithm. While exact cover does not guarantee efficient solution times for large grids, implementations of Sudoku using algorithms for exact cover typically solve 9x9 Sudoku grids with minimal calculation time.

Brute-force algorithm

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 10²¹ final grids exist, using a brute force computer algorithm can be a practical method to solve puzzles if the code is well designed.

Advantages of this method are:

• a solution is guaranteed (as long as the puzzle is valid)
• solving time is mostly unrelated to degree of difficulty

The disadvantage of this method is that it may be comparatively slow when compared to computer solution methods modeled after deductive methods.

A brute force algorithm visits the empty cells in some order, filling in digits sequentially from the available choices, or backtracking (removing failed choices) when a dead-end is reached. For example, 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, it is discovered that the "1" is not allowed, so the value is advanced to a "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 increased to "2". The algorithm is repeated until a valid solution for all 81 cells is found. See this Python example shortest-sudoku-solver-in-python

Stochastic search / optimization methods

Sudoku can be solved using stochastic (random-based—search) methods. An example of this is:

1. randomly assigning numbers to the blank cells in the grid
2. calculate the number of errors
3. "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.

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. "Sudoku as a constraint problem" describes in 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 problem. 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.

Computation time

Computer algorithms work through increasingly more cycles 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.

Blank Sudoku grids

Although Sudoku grids that come with some of their cells pre-filled can often be quite challenging to solve, blank Sudoku grids can actually be solved very quickly. Perhaps the easiest way of doing this is to produce the root solution, which can be achieved using the following simple polynomial time algorithm.

External links

• http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html Sudoku Explainer by Nicolas Juillerat (Popular for rating Sudokus in general)
• http://www.research.att.com/~gsf/man/man1/sudoku.html sudoku by gsf (Popular for rating the hardest Sudokus amongst other things)
• http://magictour.free.fr/sudoku.htmsuexrat9 by dukuso (Popular for rating the hardest sudokus)
• http://magictour.free.fr/suexratt.exe suexratt by dukuso (Popular for rating the hardest sudokus)
• http://www.emanueleferonato.com/2008/12/09/sudoku-creatorsolver-with-php/ Sudoku creator/solver using Php
• http://www.idontplaydarts.com/code/sudoku-solver/ An open source PHP Sudoku solver class using a Depth first Search
• A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles quoted also in a popular British newspaper the Daily Mail
• Solving sudoku in PL/pgSQL from Microshell.
• Solving Sudoku in APL.
• Solving Sudoku in Tcl.
• Interactive Excel Sudoku solver, using only Excel formulas.
• Interactive Javascript Sudoku solver, Only Javascript.
• Interactive Javascript Sudoku solver with source code for Ruby, Python, and Objective-C.
• Chewdoku program website.
• Essay explaining how to write a sudoku solver in Python using constraint propagation.
• Artificial Intelligence through Search: Solving Sudoku Puzzles. A tutorial by Tim Kovacs on how computers can solve Sudoku, starting from the absolute basics.
• Open Source Code for Developing Sudoku in Objective C for iPhone and OS X.
• Sudoku solver in core.logic (constraint logic programming library for Clojure)