In set theory and its applications throughout mathematics, a class is a collection of sets which can be unambiguously defined by a property that all its members share. The precise definition of "class" depends on foundational context...
is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 sub-grids that compose the grid contains all of the digits from 1 to 9...
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...
s consists of a partially completed row-column grid of cells partitioned into Nregions 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.
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
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 vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
, 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 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 more sophisticated algorithms to solve graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
. 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.
A simple trick to narrow the range of the numbers of a box can be used in improving backtracking solutions efficiently. For a Sudoku with some filled boxes, the numbers of the blank boxes are often restricted to be in a small subset of N because they are required not to conflict with other boxes in the correspondent zones. For example, a zone like [1, 2, 3, {4,5},{4,6},{4,5,6},{4,5,6,7},{7,8},{8,9}] might exist after the numbers in the filled boxes are used to clean up a Sudoku. Note that there are three boxes, {4,5},{4,6} and {4,5,6}, with three possible numbers, 4,5 and 6. That means, 4,5 and 6 would definitely occupy the three boxes and other boxes should not have those numbers. Therefore, instead of backtrack the graph instantly, we can at first narrow the range of other boxes by removing the numbers 4,5 and 6 and get the result zone as [1, 2, 3, {4,5}, {4,6}, {4,5,6}, 7, 8, 9]. Using this trick, common Sudoku puzzles seldom needs many backtrackings to find the solution.
Exact cover in solving Sudokus
Sudoku can 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 instantly.
In an exact cover problem, there is given a universe U of elements and a collection of subsets of U. The task is to find a subcollection
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of such that every element in U is an element of exactly one set in .
The challenge in applying the exact cover problem to Sudoku is to find a definition for the elements of U such that every valid Sudoku solution must contain every element of U exactly once, and to find a definition for the elements of (subsets of U) such that if the union of a disjoint collection of these elements gives U, then the elements specify a completely filled-in Sudoku grid which satisfies every constraint.
Let V = {1, 2, …, 9} be the set of values that are allowed in Sudoku.
Let S = {s11, s12, …, s19, s21, …, s99} be the set of squares of the Sudoku grid.
Let ri = {si1, si2, …, si9} ⊆ S be the set of squares belonging to row i, and let R = {r1, r2, …, r9} be the set of rows.
Let cj = {s1j, s2j, …, s9j} ⊆ S be the set of squares belonging to column j, and let C = {c1, c2, …, c9} be the set of columns.
Clearly, for each row i and column j, {sij} = ri ∩ cj.
Let bk be the set of squares belonging to block k, and let B = {b1, b2, …, b9} be the set of blocks.
Thus, b1 is the intersection of rows 1 to 3 with columns 1 to 3, b2 is the intersection of rows 1 to 3 with columns 4 to 6, …, and b9 is the intersection of rows 7 to 9 with columns 7 to 9. For example,
Finally, we are ready to define a universe U and a collection of subsets of U which exactly mirror the required constraints on the placement of values in the squares of the Sudoku grid. A solution to the exact cover problem is a collection of disjoint subsets of U whose union is exactly U: each element of U appears in exactly one element of . How can this be applied to Sudoku? We need to find a set of objects each of which appears exactly once in every finished Sudoku puzzle. Every square of the grid must appear exactly once. Every row, column, and square must contain each value exactly once. Each of these constraints involves pairs: pairs of rows and columns, pairs of rows and values, pairs of columns and values, and pairs of blocks and values. Our universe is going to be made up of pairs.
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
s R×C, R×V, C×V, and B×V. Each contains 81 pairs. For example R×C = {(r1, c1), ..., (r9, c9)}.
The universe U is the 324 element union of these four Cartesian products. As it happens, every valid Sudoku solution contains exactly these 324 pairs, no more, no less. But this set of pairs does not represent a specific solution. It represents every valid solution to the blank Sudoku grid.
To represent a specific solution, we need to assign a specific value to each square. Let Sijkl denote the subset of U containing (ri, cj), (ri, vl), (cj, vl), and (bk, vl). This subset denotes the assignment of value l to square sij. The collection contains exactly those subsets Sijkl of U in which square ij is an element of block k, i.e., sij ∈ bk. Since k is completely dependent on i and j, there are 9×9×9 = 729 such subsets in .
An incomplete Sudoku grid is represented by a disjoint collection of subsets Sijkl of U which does not specify a value for every square. Since the collection is disjoint (each element of U appears in at most one subset), we know it does not violate any of the Sudoku constraints.
Now, applying the exact cover problem, we find members of disjoint from each other and from each member of , resulting in the collection of 81 disjoint four-element subsets of U whose union is exactly the 324 element set U.
This representation of the Sudoku problem eliminates all mention of rows, columns, blocks, and values from the implementation. Instead, we always work with the same collection of 729 four-element subsets of a 324 element universe. These can be represented by the integers 0 to 728, together with a function f(i,j) which is true if the subsets corresponding to i and j are disjoint. f might be implemented using a 7292 = 531441 element (66431 byte) constant bit vector. A specific puzzle is a set of fewer than 81 integers with f(i,j) true for each pair i,j. Solving the puzzle involves repeatedly finding a new integer k which passes f(i,k) for each i in the partially completed puzzle, and backtracking when no such k can be found.
Obviously, once we find that a specific k fails f(i,k) for some i, we need not consider it again so long as i remains in the proposed solution. So we keep a list of k values which have not yet failed. The length of this list estimates the amount of work required to discover that the current proposed solution fails. So at each level of recursion, we can look ahead one level to estimate how much work each proposed k will involve, and choose the k which returns failure in the shortest time.
Although the size of the complete search tree is fixed for a given puzzle, this representation of the problem gives a fast test for failure at each level, and a way of ordering the search so that the smallest subtrees are searched first.
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.
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 1021 final grids exist, using a brute force computer algorithm can be a practical method to solve puzzles 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.
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 stymied. For the purposes of this exposition, a naive iteration order of left to right, top to bottom is assumed. The iteration could, however, visit the empty cells in any order, the order can even be randomized for each solution attempt with no harm to the algorithm. Randomized algorithms are less vulnerable to worst case inputs, but don't have consistent running times when solving the same problem repeatedly.
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 assuming naive iteration order (it is not regarded as a difficult puzzle when solved by other methods).
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). Based on the specific construction of the computer code, programmers have found the solution time for this puzzle to be between 30 and 45 minutes with a computer processor running at 3 GHz. Many programmers have developed variations of the brute force algorithm which will solve this puzzle in a few seconds with a 3 GHz computer processor.
One programmer has created charts of the progression of a pointer as it advances through the 81 positions of a Sudoku using a brute force algorithm. An example is the chart for the solution to a Sudoku "Star Burst Leo" shown here.
Solving Sudokus via stochastic search / optimization methods
Some researchers have also shown how Sudoku can be solved using stochastic—i.e. random-based—search.
Such a method could work as follows: first, start by randomly assigning numbers to the blank cells in the grid, and calculate the number of errors. Now start to "shuffle" these inserted numbers around the grid until the number of mistakes has been reduced to zero. A solution to the puzzle will then have been found. Approaches for shuffling the numbers include simulated annealing
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
Tabu search is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as...
.
Stochastic-based optimisation algorithms are known to be quite fast, though they are perhaps not as fast 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/2 a second on a typical laptop.
Finally, note that 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
Simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the top 10 algorithms of the twentieth century....
seems able to handle situations with no solutions or multiple solutions quite well.
Solving Sudokus by Constraint Programming (CP)
Sudoku is a constraint problem. An article by Helmut Simoni at Imperial College London describes in great detail many different reasoning algorithm available in the form of constraints which can be applied to model and solve the problem. It requires 81 finite domain variables and 27 constraints. Any constraint solver will have an example how to model and solve Sudoku problem (e.g.). It will solve the problem in milliseconds. Moreover, 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 (still polynomial complexity) then only some of the hardest instances (diabolic) requires further code which employs a search routine.
Algorithmic search for symmetrical Sudokus with few givens
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. When working with 19 clues or fewer, there are some classes of symmetry for which no Sudoku has been found, and none may exist. The table below shows the seven classes of symmetry and whether one or more Sudokus has been discovered for the range of 20 clues and fewer.
Discovery of Sudokus with 20 Clues or Fewer for each Class of Symmetry
givens
Vertical or Horizontal
Vertical and Horizontal
180° Rotational
Full 90° Rotational
Diagonal One Axis
Diagonal Both Axes
Full Dihedral (Vertical and Horizontal and Full Rotational)
20
Yes
Yes
Yes
Yes
Yes
Yes
Yes
19
Yes
Yes
Yes
*
Yes
Yes
*
18
Yes
No
Yes
*
Yes
Yes
*
17
No
No
No
No
Yes
No
No
(asterisk indicates this number of givens does not have a pattern with this class of symmetry)
Two examples of symmetrical Sudokus with a small number of givens are shown here:
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 polynomial time algorithm
For the standard n2 x n2 grid this algorithm (java-implementation) 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;
The above procedure produces the following 9x9 Sudoku:
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 Sudoku where whose zones consist of the rows, columns and subsquares as in the classic 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 Sudoku solver (in Prolog)
/** Helper relation, more readable than member */
-op(400, xfx, in).
X in L :- member(X, L).
/**
The standard Sudoku relation is defined by following predicate:
For all vertices(1) choose a color from Colors, such
that none of the related vertices have the same color.
Grouping constraints are encoded in releatd(V1, V2) predicate.
/
sudoku_solve([], _, _, Solution, Solution).
sudoku_solve([V | Vr], Colors, Hints, Solution, Result) :-
s(V,Ch) in Hints -> % already given as hint
sudoku_solve(Vr, Colors, Hints, [s(V,Ch) | Solution], Result)
; (
C in Colors, %try next color
forall(s(Vs1,Cs1) in Hints, (Cs1 \= C ; not(related(V, Vs1)))), % hints reserved
forall(s(Vs2,Cs2) in Solution, (Cs2 \= C ; not(related(V, Vs2)))), % ensure color is unique
sudoku_solve(Vr, Colors, Hints, [s(V,C) | Solution], Result) %repeat for the rest
).
%
- End of program. The following is the test of code above -
Some of the Sudoku puzzles can only be solved using logic that is too complex for human solvers. Most would describe them as unsolvable after exhausting their arsenal of Sudoku solving techniques and would proceed to a trial and error
Trial and error
Trial and error, or trial by error, is a general method of problem solving, fixing things, or for obtaining knowledge."Learning doesn't happen from failure itself but rather from analyzing the failure, making a change, and then trying again."...
path to reach a solution.
It is no surprise that computer programmers are interested in this subject, trying to generate even more difficult puzzles or even trying to find new ways to logically solve and rate them.
Rating puzzles that are beyond human capabilities proved to be difficult as different points of view regarding what could be considered a yardstick
Yardstick
A yardstick is a straightedge used to physically measure lengths of up to a yard high. Yardsticks are flat wooden boards with markings at regular intervals.-Construction:...
for measuring difficulty resulted in heterogeneous opinions on which puzzle is the hardest of them all.
Several active discussions on this issue took place on a number of popular Sudoku forums since 2005. Several openly accessible solver programs became popular between users for the purpose of rating and generating such puzzles. (See: External links)
The following is a compilation of the latest hardest Sudoku puzzles according to a number of openly accessible solver Programs:
vertices
of subsets of U. The task is to find a subcollection
of 
such that every element in U is an element of exactly one set in 
.
(subsets of U) such that if the union of a disjoint collection of these elements gives U, then the elements specify a completely filled-in Sudoku grid which satisfies every constraint.
of subsets of U which exactly mirror the required constraints on the placement of values in the squares of the Sudoku grid. A solution to the exact cover problem is a collection 
of disjoint subsets of U whose union is exactly U: each element of U appears in exactly one element of 
. How can this be applied to Sudoku? We need to find a set of objects each of which appears exactly once in every finished Sudoku puzzle. Every square of the grid must appear exactly once. Every row, column, and square must contain each value exactly once. Each of these constraints involves pairs: pairs of rows and columns, pairs of rows and values, pairs of columns and values, and pairs of blocks and values. Our universe is going to be made up of pairs.
contains exactly those subsets Sijkl of U in which square ij is an element of block k, i.e., sij ∈ bk. Since k is completely dependent on i and j, there are 9×9×9 = 729 such subsets in 
.
of subsets
disjoint from each other and from each member of 
, resulting in the collection 
of 81 disjoint four-element subsets of U whose union is exactly the 324 element set U.
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). Based on the specific construction of the computer code, programmers have found the solution time for this puzzle to be between 30 and 45 minutes with a computer processor running at 3 GHz. Many programmers have developed variations of the brute force algorithm which will solve this puzzle in a few seconds with a 3 GHz computer processor.
Sudoku where 
whose zones consist of the rows, columns and 
subsquares as in the classic 
Sudoku.