Sudoku solving algorithms

The class of Sudoku puzzles consists of a partially completed row-column grid of cells partitioned into N regions or zones each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each row, column and region contains exactly one of each element of the set. The puzzle can be solved using a variety of algorithms. This page provides algorithms only.

Solving a blank sudoku grid

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 very simple, linear algorithm, first proposed by Lewis

For the standard n² x n² grid this algorithm is as follows:

int x := 0;
for i := 1 to n do
   for j := 1 to n do
      for k := 1 to n^2 do
         grid[n*(i-1)+j][k] := x(mod n^2) + 1
         x := x + 1;
       x := x + n;
   x := x + 1

(Here, the notation grid[i][j] represents the value that is contained in the ith row and jth column of cells). If we set n = 3, then this procedure will produce the following root solution.

 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

Obviously, this algorithm can easily be adapted to different sized puzzles if needed.

Solving sudokus by backtracking

The basic backtracking algorithm can be adapted to solve sudokus. This is straightforward. Say a zone is a subset of N boxes of an N x N grid, which must contain the numbers from 1 to N. 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 on $N^{2}$ vertices, one vertex for each box of the grid. Two vertices are connected by an edge if there exists a zone containing the two boxes. The problem is then equivalent to coloring this graph with N colors, where adjacent vertices may not have the same color. This is done by starting with an empty assignment of colors (for jigsaw sudokus) and assigning colors to vertices one after another, using some fixed order of the vertices. Whenever a color is being assigned, we check whether it is compatible with the existing assignments, i.e. whether the new color occurs among the neighbors of that vertex. If it doesn't, then we may assign it to the vertex and try to process another vertex. We backtrack once all N colors have been tried for a given vertex. If all vertices have been assigned a color, then we have found a solution. There are of course much more sophisticated algorithms to solve graph coloring. If the sudoku contains initial data, i.e. some boxes have already been filled, then these go into the color assignment before backtracking begins and the vertex sequence includes only the empty boxes.

The above algorithm was used to solve a 10x10 jigsaw sudoku that was proposed on Les-Mathematiques.net A link to the proposal may be found in the section for external links. The first section of the program defines the 10 jigsaw pieces (zones), the second the row and column zones. Thereafter the graph is constructed as an adjacency list. The search procedure prints completed solutions (when all 100 boxes have been assigned). Otherwise it computes the set of colors present among the neighbors of the next vertex to be processed, and recursively tries those assignments that do not conflict with this set. The search starts with an empty assignment.

Exact Cover in solving sudokus

Sudoku can be described as an Exact cover problem. This allows both for a very elegant description of the problem and an efficient backtrack algorithm for solving the problem.

In an exact cover problem, there is given a universe U of elements and a collection ${\mathcal {S}}$ of subsets of U. The task is to find a subcollection ${\mathcal {S}}^{*}$ of ${\mathcal {S}}$ such that every element in U is contained in exactly one set in ${\mathcal {S}}^{*}$.

Let R, C, B, and V denote the set of rows, columns, blocks, and values in the sudoku. Each of these sets has nine elements. Each of the following combinations must occur exactly once in each sudoku: R×C (in each row-column intersection there must be exactly one number), R×V (each value must appear exactly once in each row), C×V (each value must appear exactly once in each column), and B×V (each value must appear exactly once in each 3×3 block. The union of these four sets of 81 elements each is the universe of 324 elements in the exact cover formulation.

The subsets available for covering the elements of the universe correspond to writing a number in a square. Writing the value v in row r in column c in block b corresponds to the set with the elements (r,c), (r,v), (c,v), (b,v). The sudoku can then be solved by finding 81 such subsets that together cover each element in the universe exactly once.

Where this method really excels is that one does not have to consider the various types of constraints separately. Rather, one can simply structure the backtrack search so that at each level of recursion one chooses the element from the universe for which there are the fewest number of sets with which it can be covered without violating the exact cover constraints.

With this approach and an efficient library for solving exact cover problems, one can solve 9×9 sudokus in such a short time on a modern PC that measuring the computation time becomes challenging.

Standard Sudoku solver and enumerator

This section contains a discussion of a modified backtracking algorithm that can be used to create and solve Sudokus even with modest computing resources. A standard Sudoku is an $NxN$ Sudoku where $N=k^{2}$ whose zones consist of the rows, columns and $kxk$ subsquares as in the classic $9x9$ Sudoku.

Key modifications to the algorithm

Conceptually there is one modification only: the backtracking algorithm sorts the vertices by the number of colors already assigned among its neighbors before selecting the next vertex to try. The vertex with the largest number of assigned colors, and hence, the smallest number of choices, is tried first. (There may be more than one such vertex).

The data structures used during the backtracking search are chosen to make this easy and fast, although further optimization is possible. The search state is stored in three data structures: a hash table whose keys are the vertices and whose values are the colors that have been assigned to them. There is an array that contains the vertices that have not yet been assigned a color. Finally, there is a hash table whose keys are again the vertices and whose values are hash tables containing the colors present among the neighbors of the respective vertex, as well as a hint as to who assigned them.

Discussion of the modified algorithm

The algorithm follows this sequence of steps:

• Create the row and column zones, then create the subsquare zones.
• Construct the adjacency matrix of the graph.
• The search routine:
  • Print the solution if there are no more vertices to be assigned a color, and return.
  • Sort the remaining vertices in descending order of colors present among their neighbors.
  • Pick the/a vertex with the largest number of assigned colors.
  • Try each of the remaining possible colors recursively.
    • Update the hash table of vertex neighboring colors to reflect the assignment.
    • Update the partial solution to reflect the assignment.
    • Recurse.
    • Remove the color from the partial solution.
    • Undo the color assignments from the neighboring colors hash table.
• Before the search begins, read the initial color assignment.
• Compute the set of vertices to be assigned a color, i.e. not present in the initial assignment.
• Compute the initial state of the hash table of neighbor colors.
• Start the search.

The above algorithm can enter into loops. To detect this, add a hash table that stores seen configurations. When this happens, terminate the computation and indicate FAIL (e.g. by throwing an exception). Repeat with a different seed of the random number generator if desired.

Example of a back-tracking Sudoku solver

def read_matrix
  matrix = []

  (0..8).each { |i|
    l = readline
    matrix[i] = []
    (0..8).each { |j|
      matrix[i][j] = l[j..j].to_i
    }
  }
  matrix
end

def permissible(matrix, i, j)
  ok = [true,true,true,true,true,true,true,true,true]
  # Same as another in the column isn't permissible...
  (0..8).each { |i2|
    next if matrix[i2][j] == 0
    ok[matrix[i2][j] - 1] = false
  }
  # Same as another in the row isn't permissible...
  (0..8).each { |j2|
    next if matrix[i][j2] == 0
    ok[matrix[i][j2] - 1] = false
  }
  # Same as another in the 3x3 block isn't permissible...
  igroup = (i / 3) * 3
  jgroup = (j / 3) * 3
  (igroup..(igroup + 2)).each { |i2|
    (jgroup..(jgroup + 2)).each { |j2|
      next if matrix[i2][j2] == 0
      ok[matrix[i2][j2] - 1] = false
    }
  }
  # Convert to the array format...
  ret = []
  (0..8).each { |i2| ret.push(i2 + 1) if ok[i2] }
  ret
end

def deep_copy_sudoku(matrix)
  newmat = []
  (0..8).each { |i|
    newmat[i] = []
    (0..8).each { |j|
      newmat[i][j] = matrix[i][j]
    }
  }
  newmat
end

def solve_sudoku(matrix)
  while true
    options = []
    (0..8).each { |i|
      (0..8).each { |j|
        next if matrix[i][j] != 0
        p = permissible(matrix, i, j)
        # If nothing is permissible, there is no solution at this level.
        return false if (p.length == 0)
        options.push({:i => i, :j => j, :permissible => p})
      }
    }
    # If the matrix is complete, we have a solution...
    return matrix if options.length == 0

    omin = options.min { | a, b |
      a[:permissible].length <=> b[:permissible].length
    }

    # If there is an option with only one solution, set it and re-check permissibility
    if omin[:permissible].length == 1
      matrix[omin[:i]][omin[:j]] = omin[:permissible][0]
      next
    end

    # We have two or more choices. We need to search both...
    omin[:permissible].each { |v|
      mtmp = deep_copy_sudoku(matrix)
      mtmp[omin[:i]][omin[:j]] = v
      ret = solve_sudoku(mtmp)
      if ret != false
        return ret
      end
    }

    # We did an exhaustive search on this branch and nothing worked out.
    return false
  end
end

def print_matrix(matrix)
  if (matrix == false)
    print "Impossible\n"
    return
  end

  (0..8).each { |i|
    (0..8).each { |j|
      print matrix[i][j]
    }
    print "\n"
  }
end

print_matrix(solve_sudoku(read_matrix()))

Solving sudokus by a 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 algorithm can be a practical method to solve puzzles using a computer program if the code is well designed.

An advantage of this method is that if the puzzle is valid, a solution is guaranteed. There is not a strong relation between the solving time and the degree of difficulty of the puzzle; generating a solution is just a matter of waiting until the algorithm advances to the set of numbers that satisfies the puzzle. The disadvantage of this method is that it may be comparatively slow when compared to computer solution methods modeled after human-style deductive methods.

Briefly, 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 incremented by one. The algorithm is repeated until the allowed value in the 81st cell is discovered. The construction of 81 numbers is parsed to form the 9 x 9 solution matrix.

Most Sudoku puzzles will be solved in just a few seconds with this method, but there are exceptions. The following puzzle was designed to be a near worst case situation for solution by brute force (although it is not regarded as a difficult puzzle when solved by other methods).

"Near worst case" sudoku puzzle for brute force solver.

Solving this puzzle by brute-force requires a large number of iterations because it has a low number of clues (17), the top row has no clues at all, and the solution has "987654321" as its first row. Thus a brute-force solver will spend an enormous amount of time "counting" upward before it arrives at the final grid which satisfies the puzzle. If one iteration is defined as one attempt to place one value in one cell, then this puzzles requires 641,580,843 iterations to solve. These iterations do not include the work involved at each step to learn if each digit entered is valid or not (required for every iteration). One programmer found the solution time for this puzzle to be 96 minutes with a computer processor running at 500 MHz, and all PC screen output disabled (program sends video output only when the solution is obtained).

Solving sudokus via stochastic search / optimisation methods

Recently, some researchers have also shown how sudoku can be solved using stochastic -- i.e. random-based -- search. Perhaps the first algorithm of this kind was produced by Lewis.

This particular algorithm starts by randomly assigning numbers to the blank cells in the grid in a haphazard fashion. The number of errors in the grid is then calculated and the objective of the algorithm is to then "shuffle" the numbers around the grid until the number of mistakes has been reduced to zero. A solution to the puzzle will then have been found. In this algorithm, the optimisation is achieved using simulated annealing, Though other optimisation methods such as tabu search may prove just as applicable.

The advantage of this type of method is that the puzzle does not have to be "logic-solvable" in order for the algorithm to be able solve it. In other words, unlike other methods, the puzzles that are given to this algorithm do not have to be specially constructed so that they provide sufficient clues for filling the grid using forward chaining logic only. In fact, the only pre-requisite for the stochastic search algorithm to work is that puzzle has at least one solution.

The simulated annealing method in Lewis's paper is also quite fast (though perhaps not as quick as some logic-based techniques with logic solvable puzzles): depending on the type of instance given to the algorithm, generally 9x9 puzzles will be solved in less than 1 second on a typical year-2000 lap top; 16x16 puzzles will take around 10-15 seconds.

Exceptionally difficult Sudokus

File:Top1465number77.JPG

"Top 1465 Number 77"

File:Qassim Hamza Memorial.JPG

"Qassim Hamza"

Some puzzles have been developed which seem to defy solution by logical analysis. The most difficult among these are even regarded as beyond the scope of human deductive capability. One such puzzle has become known as "Top 1465 Number 77" and has been widely analyzed by enthusiasts in an endeavor to develop stronger solution methods which will crack these types of puzzles and reveal their solutions.

More recently, an even more perplexing puzzle has been developed, which has become known as "Qassim Hamza". This puzzle has proven to be extremely daunting, and even an exhaustive application of all basic solution methods will not advance this puzzle towards a solution.

Puzzles of this complexity are generally better suited for solving by computer analysis, and the algorithms involved typically require some form of sequentially applied guesswork or trial and error. By using computer code to analyze puzzles, the challenge is no longer focused on the solution of individual puzzles with pencil and paper, but rather to create a fast and efficient algorithm that will solve any puzzle regardless of how formidable it may be.

External links

• Riedel, Marko. Solving a 10x10 jigsaw sudoku
• A Java library implementation of Donald Knuth's "Algorithm X" and a Sudoku solver using the library
• A three-line sudoku solver
• A probabilistic suduko solver in PHP, solves 'ambiguous' puzzles
• Sudoku Puzzle Solver in Visual Prolog
• Metaheuristics Can Solve Sudoku Puzzles Journal of Heuristics, vol. 13 (4), pp 387-401.
• Online Sudoku Solver