Sudoku solving algorithms

From Wikipedia, the free encyclopedia
  (Redirected from Sudoku algorithms)
Jump to: navigation, search
A typical Sudoku puzzle, a 9x9 grid with several numbers missing
A typical Sudoku puzzle

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.



Backtracking algorithms are adapted to solve the Sudoku that iterates all the possible solutions for the given sudoku. If the solutions assigned do not lead to the solution of Sudoku, the algorithm discards the solutions and rollbacks to the original solutions and retries again and hence the name backtracking.[1]

Below is the general pseudocode of backtracking algorithm for standard sudoku template (9x9.) [2]

 Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
 Fill in some empty grid with the known values
 Make an original copy of the array
 Start from top left grid (nx = 0, ny = 0), check if grid is empty
 if (grid is empty) {
   assign the empty grid with values (i)
   if (no numbers exists in same rows & same columns same as (i) & 3x3 square (i) is currently in)
     fill in the number
   if (numbers exists in same rows | same columns same as (i) | 3x3 square (i) is currently in)
     discard (i) and repick other values (i++)
 else {
   while (nx < 9) {
     Proceed to next row grid(nx++, ny)
     if (nx equals 9) {
       reset nx = 1
       proceed to next column grid(nx,ny++)
       if (ny equals 9) {
         print solution

The animated GIF shows how the Sudoku is solved using backtracking. The red numbers are "fixed," while the backtrack algorithm tries to find a solution of blue numbers to complete the Sudoku grid. Notice how the algorithm discards all the previous solutions if it finds the existing solutions do not fulfil the Sudoku requirement, hence the name "backtrack".

The animated GIF shows how the Sudoku is solved using backtracking. The red numbers are "fixed," while the backtrack algorithm tries to find a solution of blue numbers to complete the Sudoku grid.

Exact cover[edit]

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, such as Dancing Links, typically solve 9x9 Sudoku grids with minimal calculation time of the order of seconds.

Brute Force Algorithm[edit]

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.

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, and backtracking (removing failed choices) as dead-ends are reached. At each backtrack, the algorithm iterates the digit in the cell most recently filled before the cell where the dead end was seen. If that particular cell is tried with all possible digits, the algorithm steps back to the second prior cell filled before the last dead end and iterates that cell's digit.

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 by 1. The algorithm is repeated until a valid solution for all 81 cells is found.[3][4]

Stochastic search / optimization methods[edit]

Sudoku can be solved using stochastic (random-based—search) methods.[5][6] An example of this approach is to:

  1. Randomly assign 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. Algorithms designed for graph colouring are also known to perform very well with Sudoku puzzles.[7]

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[edit]

Sudoku is a constraint problem. In his paper Sudoku as a Constraint Problem,[8] 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.[9][10] 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[edit]

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.[11]

Blank Sudoku grids[edit]

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.[5]

For the standard n2 x n2 (9 x 9) grid this algorithm (equivalent implementations in Java and Haskell) is as follows:

final int n = 3;
final int[][] field = new int[n*n][n*n];
for (int i = 0; i < n*n; i++)
	for (int j = 0; j < n*n; j++)
		field[i][j] = (i*n + i/n + j) % (n*n) + 1;
sol :: [[Int]]
sol = [ [ witness (build i j) | j <- [0..heightGame] ]
                              | i <- [0..heightGame] ]
    build i j     = (i * heightRegion) + (i `div` heightRegion) + j
    witness       = (`mod` heightGame) . (+ 1)
    heightRegion  = 3
    heightGame    = heightRegion^2

The above procedure produces the following 9x9 Sudoku:

| 1 2 3 | 4 5 6 | 7 8 9 |
| 4 5 6 | 7 8 9 | 1 2 3 |
| 7 8 9 | 1 2 3 | 4 5 6 |
| 2 3 4 | 5 6 7 | 8 9 1 |
| 5 6 7 | 8 9 1 | 2 3 4 |
| 8 9 1 | 2 3 4 | 5 6 7 |
| 3 4 5 | 6 7 8 | 9 1 2 |
| 6 7 8 | 9 1 2 | 3 4 5 |
| 9 1 2 | 3 4 5 | 6 7 8 |


  1. ^ Zelenski, Julie (July 16, 2008). Lecture 11 | Programming Abstractions (Stanford). Stanford Computer Science Department. 
  2. ^
  3. ^ "Backtracking - Set 7 (Sudoku)". GeeksforGeeks. GeeksforGeeks. Archived from the original (HTML) on 28 Aug 2016. Retrieved 24 December 2016. 
  4. ^ Norvig, Peter. "Solving Every Sudoku Puzzle". Peter Norvig (personal website). Archived from the original (HTML) on 20 Oct 2016. Retrieved 24 December 2016. 
  5. ^ a b Lewis, R (2007) Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4), pp 387-401.
  6. ^ Perez, Meir and Marwala, Tshilidzi (2008) Stochastic Optimization Approaches for Solving Sudoku arXiv:0805.0697.
  7. ^ Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015.
  8. ^ Simonis, Helmut (2005). "Sudoku as a Constraint Problem" (PDF). H Simonis homepage. Cork Constraint Computation Centre at University College Cork: Helmut Simonis. Retrieved 8 December 2016. paper presented at the Eleventh International Conference on Principles and Practice of Constraint Programming 
  9. ^ Multiple Authors. "Java Constraint Programming solver" (Java). JaCoP. Krzysztof Kuchcinski & Radoslaw Szymanek. Retrieved 8 December 2016. 
  10. ^ Rhollor. "Sudokusolver" (C++). GitHub. Rhollor. Retrieved 8 December 2016. 
  11. ^ "17 Clue Sudoku with Diagonal Symmetry"

External links[edit]