A Beginner’s Guide to Solving Sudoku Puzzles by Computer

Robert Cowen

We simultaneously introduce effective techniques for solving Sudoku puzzles and explain how to implement them in Mathematica. The hardest puzzles require some guessing, and we include a simple backtracking technique that solves even the hardest puzzles. The programming skills required are kept at a minimum.

Introduction to Sudoku

Sudoku, for those unfamiliar with this puzzle, consists of a 9×9 square grid with nine 3×3 subgrids. The 81 entries are to be filled with the integers 1 to 9 in such a way that each row, column and subgrid contains all the nine integers. Some of the entries are already chosen, and the final puzzle solution must contain these initial choices. Here is a sample puzzle.

First Steps to Solving Sudoku

The input for this puzzle is a list of nine lists consisting of blanks (shown as □) or integers between 1 and 9. A list of lists of the same length is regarded as a matrix in Mathematica, so we input b for the puzzle and then show it in matrix form.

b={{\[Placeholder],3,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],7,\[Placeholder]},{\[Placeholder],1,\[Placeholder],8,\[Placeholder],6,\[Placeholder],2,\[Placeholder]},{\[Placeholder],\[Placeholder],9,1,7,5,4,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],7,\[Placeholder],\[Placeholder],\[Placeholder],6,\[Placeholder],\[Placeholder]},{2,\[Placeholder],\[Placeholder],4,\[Placeholder],9,\[Placeholder],\[Placeholder],3},{\[Placeholder],\[Placeholder],3,\[Placeholder],\[Placeholder],\[Placeholder],1,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],1,5,4,8,2,\[Placeholder],\[Placeholder]},{\[Placeholder],6,\[Placeholder],3,\[Placeholder],2,\[Placeholder],1,\[Placeholder]},{\[Placeholder],5,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],4,\[Placeholder]}};

MatrixForm[b]

We can also display this in Sudoku format by drawing column and row lines and a frame.

display[X_]:=Grid[
Map[
If[ListQ@#,Row[#],#]&,X,{2}
],
GridFrame->True,
RowLines->{False,False,True,False,False,True,False,False}, ColumnLines->{False,False,True,False,False,True,False,False}]

display[b]

In attempting a solution, a blank gets replaced with a list of candidate entries shown compactly without braces or commas.

Row[{4,5,6,8}]

Each element of a Sudoku matrix X is obtainable as X[[i,j]], where i and j are the row and column of the element in the matrix.

b[[1,2]]

b[[1,1]]

To obtain the entire row in X that contains the entry X[[i,j]], we evaluate X[[i]]; so, for example, this gives row 3, which contains element b[[3,5]].

b[[3]]

To obtain the column in X that contains X[[i,j]] is a little trickier. One could first “transpose” the matrix X, that is, interchange rows and columns and then find row j of the transposed matrix; the command for transposing a matrix is Transpose. However, Mathematica has a faster way using the option All. We just enter X[[All,j]] to get column j of X. For example, the column that contains b[[3,5]], that is, column 5 of b, can be obtained by entering b[[All,5]].

b[[All,5]]

The function Column displays that list vertically.

Column@b[[All,5]]

It is more difficult to obtain the block to which X[[i,j]] belongs. To do this we define a function block[X,i,j] that gives a list of the entries that comprise the block of X[[i,j]] in X.

block[X_,i_,j_]:=Which[
1≤i≤3&&1≤j≤3,Take[X,{1,3},{1,3}],
4≤i≤6&&1≤j≤3,Take[X,{4,6},{1,3}],
7≤i≤9&&1≤j≤3,Take[X,{7,9},{1,3}],
1≤i≤3&&4≤j≤6,Take[X,{1,3},{4,6}],
4≤i≤6&&4≤j≤6,Take[X,{4,6},{4,6}],
7≤i≤9&&4≤j≤6,Take[X,{7,9},{4,6}],
1≤i≤3&&7≤j≤9,Take[X,{1,3},{7,9}],
4≤i≤6&&7≤j≤9,Take[X,{4,6},{7,9}],
7≤i≤9&&7≤j≤9,Take[X,{7,9},{7,9}]
]

For example, this is the block containing b[[1,6]], the sixth entry in row 1, □.

block[b,1,6]

MatrixForm[block[b,1,6]]

To get a single list of these entries by removing the inner parentheses, we use Flatten.

Flatten[block[b,1,6]]

Our first step is to replace each □ in b (using ReplaceAll) by the list of the nine numbers, {1,2, ... ,9}, which are possible candidates to occupy that position in b.

c=ReplaceAll[b,\[Placeholder]->Range[9]]

display[c]

Our next task is to start eliminating candidate values in the entries that are lists of numbers in X, proceeding one entry X[[i,j]] at a time. We start with A=X in order to be able to redefine entries.

Since no entry can appear more than once in any row, column or block, we let B be the set of integers in the row, column and block containing A[[i,j]].

If the entry A[[i,j]] is a list rather than an integer, we redefine A[[i,j]] by removing the entries that also belong to B.

Finally, if A[[i,j]] is a list of one element, we redefine it to be that element.

DeleteSingletonsFromLists[X_]:=Module[{A=X,integers},
Table[
integers=Select[
Join[A[[i]],A[[All,j]],Flatten[block[A,i,j],1]],
IntegerQ[#]&
];
If[ListQ[A[[i,j]]],A[[i,j]]=Complement[A[[i,j]],integers]];If[Length[A[[i,j]]]==1,A[[i,j]]=First[A[[i,j]]]],
{i,9},{j,9}];A]

DeleteSingletonsFromLists[c]//display

To apply DeleteSingletonsFromLists again and again to c until the result no longer changes, we use FixedPoint. The puzzle simplifies, but we see that we are still not done!

(d=FixedPoint[DeleteSingletonsFromLists,c])//display

However, the first block has three entries (colored red) that are all sublists of {5,6,8}.

({{(RowDefault[5, 6, 8]), 3, (RowDefault[5, 8]), 9, 2, 4, (RowDefault[5, 8]), 7, (RowDefault[1, 5, 6, 8])}, {(RowDefault[4, 5, 7]), 1, (RowDefault[4, 5]), 8, 3, 6, (RowDefault[5, 9]), 2, (RowDefault[5, 9])}, {(RowDefault[6, 8]), 2, 9, 1, 7, 5, 4, (RowDefault[3, 6, 8]), (RowDefault[6, 8])}, {(RowDefault[1, 4, 5, 9]), (RowDefault[4, 9]), 7, 2, (RowDefault[5, 8]), 3, 6, (RowDefault[8, 9]), (RowDefault[4, 8, 9])}, {2, 8, 6, 4, 1, 9, 7, 5, 3}, {(RowDefault[4, 5, 9]), (RowDefault[4, 9]), 3, 6, (RowDefault[5, 8]), 7, 1, (RowDefault[8, 9]), (RowDefault[2, 4, 8, 9])}, {(RowDefault[3, 7, 9]), (RowDefault[7, 9]), 1, 5, 4, 8, 2, (RowDefault[3, 6, 9]), (RowDefault[6, 7, 9])}, {(RowDefault[4, 7, 8]), 6, (RowDefault[4, 8]), 3, 9, 2, (RowDefault[5, 8]), 1, (RowDefault[5, 7, 8])}, {(RowDefault[3, 8, 9]), 5, (RowDefault[2, 8]), 7, 6, 1, (RowDefault[3, 8, 9]), 4, (RowDefault[8, 9])}});

While we do not know the exact value of any of the red entries, we know that the three numbers 5, 6 and 8 will be used up filling them; thus we can remove 5, 6 and 8 from the other entries in this block (colored green).

({{(RowDefault[5, 6, 8]), 3, (RowDefault[5, 8]), 9, 2, 4, (RowDefault[5, 8]), 7, (RowDefault[1, 5, 6, 8])}, {47, 1, 4, 8, 3, 6, (RowDefault[5, 9]), 2, (RowDefault[5, 9])}, {(RowDefault[6, 8]), 2, 9, 1, 7, 5, 4, (RowDefault[3, 6, 8]), (RowDefault[6, 8])}, {(RowDefault[1, 4, 5, 9]), (RowDefault[4, 9]), 7, 2, (RowDefault[5, 8]), 3, 6, (RowDefault[8, 9]), (RowDefault[4, 8, 9])}, {2, 8, 6, 4, 1, 9, 7, 5, 3}, {(RowDefault[4, 5, 9]), (RowDefault[4, 9]), 3, 6, (RowDefault[5, 8]), 7, 1, (RowDefault[8, 9]), (RowDefault[2, 4, 8, 9])}, {(RowDefault[3, 7, 9]), (RowDefault[7, 9]), 1, 5, 4, 8, 2, (RowDefault[3, 6, 9]), (RowDefault[6, 7, 9])}, {(RowDefault[4, 7, 8]), 6, (RowDefault[4, 8]), 3, 9, 2, (RowDefault[5, 8]), 1, (RowDefault[5, 7, 8])}, {(RowDefault[3, 8, 9]), 5, (RowDefault[2, 8]), 7, 6, 1, (RowDefault[3, 8, 9]), 4, (RowDefault[8, 9])}});

Similarly, in the first row, there are three entries that are sublists of {5,6,8}, so we remove 5, 6 and 8 from {1,5,6,8} at the end of row 1; this defines e.

({{(RowDefault[5, 6, 8]), 3, (RowDefault[5, 8]), 9, 2, 4, (RowDefault[5, 8]), 7, (RowDefault[1, 5, 6, 8])}, {47, 1, 4, 8, 3, 6, (RowDefault[5, 9]), 2, (RowDefault[5, 9])}, {(RowDefault[6, 8]), 2, 9, 1, 7, 5, 4, (RowDefault[3, 6, 8]), (RowDefault[6, 8])}, {(RowDefault[1, 4, 5, 9]), (RowDefault[4, 9]), 7, 2, (RowDefault[5, 8]), 3, 6, (RowDefault[8, 9]), (RowDefault[4, 8, 9])}, {2, 8, 6, 4, 1, 9, 7, 5, 3}, {(RowDefault[4, 5, 9]), (RowDefault[4, 9]), 3, 6, (RowDefault[5, 8]), 7, 1, (RowDefault[8, 9]), (RowDefault[2, 4, 8, 9])}, {(RowDefault[3, 7, 9]), (RowDefault[7, 9]), 1, 5, 4, 8, 2, (RowDefault[3, 6, 9]), (RowDefault[6, 7, 9])}, {(RowDefault[4, 7, 8]), 6, (RowDefault[4, 8]), 3, 9, 2, (RowDefault[5, 8]), 1, (RowDefault[5, 7, 8])}, {(RowDefault[3, 8, 9]), 5, (RowDefault[2, 8]), 7, 6, 1, (RowDefault[3, 8, 9]), 4, (RowDefault[8, 9])}});

(e={{{5,6,8},3,{5,8},9,2,4,{5,8},7,1},{{4,7},1,4,8,3,6,{5,9},2,{5,9}},{{6,8},2,9,1,7,5,4,{3,6,8},{6,8}},{{1,4,5,9},{4,9},7,2,{5,8},3,6,{8,9},{4,8,9}},{2,8,6,4,1,9,7,5,3},{{4,5,9},{4,9},3,6,{5,8},7,1,{8,9},{2,4,8,9}},{{3,7,9},{7,9},1,5,4,8,2,{3,6,9},{6,7,9}},{{4,7,8},6,{4,8},3,9,2,{5,8},1,{5,7,8}},{{3,8,9},5,{2,8},7,6,1,{3,8,9},4,{8,9}}})//display

Then we use FixedPoint again and display the result. We are done! We explore this technique further in the next section.

FixedPoint[DeleteSingletonsFromLists,e]//display

Sudoku Twins and Multiples

If any row, column or block contains the pair {a,b} twice, both a and b must be used up in the two entries containing {a,b}, even though we do not know which pair contains a and which contains b. Hence, no other entry in that row, column or block can contain either a or b. This obvious fact is surprisingly useful in solving Sudoku puzzles.

To use it, we define the function Twin.

1. We select the set of pairs (the lists of length two).

2. The twins are the identical pairs.

3. The numbers in the twins are the numbers to prune.

4. The lists are pruned.

5. Any singleton list is changed to its element.

Twin[X_]:=
Module[{pairs,twins,numberstoprune,prunedlists},
pairs=Select[X,Length[#]==2&];
twins=Select[Subsets[pairs,{2}],#[[1]]==#[[2]]&,1]; 
numberstoprune=Union[Flatten[twins]];
prunedlists=If[Length[#]>1&&#≠numberstoprune,Complement[#,numberstoprune],#]&/@X;
If[Length[#]==1,First[#],#]&/@prunedlists
]

Here are some examples using d, which was defined before. The twins in this row are {5,8} and {5,8}.

d[[1]]

Hence 5 and 8 are removed from the other lists in the row.

Twin[d[[1]]]

The twins in row 3 are {6,8} and {6,8}.

d[[3]]

Twin[d[[3]]]

We can map Twin over all the rows of a matrix.

TwinRow[X_]:=Twin/@X

(f=Twin/@d)//display

We now use DeleteSingletonsFromLists starting with f until the result does not change.

FixedPoint[DeleteSingletonsFromLists,f]//display

We are done. It was only necessary to use Twin on the rows.

It is easy to apply Twin on the columns: transpose, apply Twin to the rows, and transpose back.

TwinColumn[X_]:= Transpose[TwinRow[Transpose[X]]]

The blocks are more complicated. We make use of a general theorem: transform an (n^2)×(n^2) matrix M by taking the (n^2) elements of each block in order as the rows of a new (n^2)×(n^2) matrix BT(M); then BT(BT(M))=M (i.e. BT is an involution). Here BT stands for block transpose.

This verifies the theorem in the 9×9 case.

M=Table[(Subscript[m, i,j]),{i,9},{j,9}];MatrixForm[M]

To construct the new kind of transposed matrix, we define the function BlockTranspose.

BlockTranspose[x_]:={
Flatten[block[x,1,1],1],
Flatten[block[x,1,4],1],
Flatten[block[x,1,7],1],
Flatten[block[x,4,1],1],
Flatten[block[x,4,4],1],
Flatten[block[x,4,7],1],
Flatten[block[x,7,1],1],
Flatten[block[x,7,4],1],
Flatten[block[x,7,7],1]
}

Here is the transformed matrix BlockTranspose[M].

BlockTranspose[M]//MatrixForm

Finally, we look at the matrix BlockTranspose[BlockTranspose[M]].

BlockTranspose[BlockTranspose[M]]//MatrixForm

It is the same as the original matrix M; here is a direct check that they are equal.

BlockTranspose[BlockTranspose[M]]==M

It is a common technique in problem solving to first transform the problem, solve the transformed problem and then transform back. As an example, we apply BlockTranspose, followed by Twin, followed by BlockTranspose, to the matrix f defined earlier; blocks (1,3), (2,1) and (2,3) change.

display[f]

BlockTranspose[Twin/@BlockTranspose[f]]//display

This makes a function out of that line of code.

TwinBlock[X_]:=BlockTranspose[Twin/@BlockTranspose[X]]

The function TwinSolver puts together the discussion so far.

TwinSolver[X_]:=FixedPoint[
TwinBlock@TwinColumn@TwinRow@FixedPoint[DeleteSingletonsFromLists,#]&,X]

We apply it to the matrix f and get a solution as before.

TwinSolver[f]//display

We generalize the function Twin to Multiple to deal with triples and quadruplets as well as twins.

Multiple[X_,n_]:=Module[
{ntuples,multiplets,numberstoprune,prunedlists},
ntuples=Select[X,1<Length[#]≤n&];
multiplets=Select[Subsets[ntuples,{n}],Length[Union[Flatten[#]]]==n&];
numberstoprune=Union[Flatten[If[{}≠multiplets,First[multiplets],{}]]];
prunedlists=(If[Length[#1]>1&&!MemberQ[If[multiplets=={},{},First[multiplets]],#1],Complement[#1,numberstoprune],#1]&)/@X;
If[Length[#]==1,First[#],#]&/@prunedlists
]

Just as with Twin, we want to use Multiple on rows, columns and blocks of a matrix and then combine them in MultipleSolver.

MultipleRow[X_,n_]:=Multiple[#,n]&/@X

MultipleColumn[X_,n_]:=Transpose[Multiple[#,n]&/@Transpose[X]]

MultipleBlock[X_,n_]:=BlockTranspose[Multiple[#,n]&/@BlockTranspose[X]]

MultipleSolver[X_,n_]:=FixedPoint[MultipleBlock[#,n]& @MultipleColumn[#,n]& @MultipleRow[#,n]& @FixedPoint[DeleteSingletonsFromLists,#]&,X]

We had already solved f with TwinSolver, but let us apply MultipleSolver for triples as a check.

display[f]

MultipleSolver[f,3]//display

MasterSolver combines the three solvers into one.

MasterSolver[X_]:=
DeleteSingletonsFromLists@MultipleSolver[#,2]&@MultipleSolver[#,3]&@MultipleSolver[#,4]&@
ReplaceAll[X,\[Placeholder]->Range[9]]

Consider the puzzle g.

(g={{5,\[Placeholder],\[Placeholder],\[Placeholder],6,3,\[Placeholder],\[Placeholder],4},{\[Placeholder],7,\[Placeholder],1,5,\[Placeholder],6,8,\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],6,1},{\[Placeholder],\[Placeholder],2,\[Placeholder],3,\[Placeholder],4,\[Placeholder],\[Placeholder]},{6,9,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],5,3,\[Placeholder],7,6,\[Placeholder],2,\[Placeholder]},{1,\[Placeholder],\[Placeholder],5,4,\[Placeholder],\[Placeholder],\[Placeholder],8}})//display

Unfortunately, MasterSolver does not solve the puzzle.

(g1=MasterSolver[g])//display

However, there are entries that are pairs.

Select[Flatten[g1,1],Length[#]==2&]

We propose to replace the pair {1,8} by 1 and to try to solve the modified puzzle; if that leads to a contradiction, then g1[[1,2]]=8.

We introduce the functions GoLeft and GoRight via the helper function GoAux. If there are any pairs in X, GoLeft[X] replaces the first such pair {u,v} with its left entry u and applies MasterSolver; the function GoRight replaces {u,v} with its right entry v.

GoAux[X_,leftorright_]:=Module[
{firstpair=SelectFirst[Flatten[X,1],Length@#==2&]},
MasterSolver@If[
2≠Length@firstpair,(* there was no pair *)
X,
ReplacePart[X,First@Position[X,firstpair]->If[leftorright===Left,First,Last]@firstpair]
]
]

GoLeft[X_]:=GoAux[X,Left]

GoRight[X_]:=GoAux[X,Right]

The two blank entries indicate a contradiction.

GoLeft[g1]//display

Therefore, the alternative g1[[1,2]]=8 must solve the puzzle, and it does.

GoRight[g1]//display

Backtracking

We have just seen that guessing between two alternatives quickly led us to a solution. However, if a solution was not obtained with the first alternative, it might be necessary to again guess between two alternatives, and so on. If there are always just two alternatives, this leads to a binary tree with the root at the top.

It is not clear how many levels or guesses are needed before reaching a solution. Also, it may not be necessary to generate the entire tree before a solution is reached. There is a systematic and efficient way to search such a tree, usually referred to as backtracking.

Here is the method: start at the root and go left as long as there is no contradiction. If there is a contradiction, go back one level and go right. Then resume going left as far as possible. If there is a contradiction after going right, go back through all the right branches traversed so far; then go back through an additional left branch and go right.

For example, assume that contradictions exist at all nodes on level 4 except for the last one, node 15. The labels in the following tree indicate how to backtrack to the solution at node 15.

The binary choice in the Sudoku situation is to go either left or right. A path through the tree corresponds to a sequence of such choices; for example, the path (1, 2, 6, 8) generates the sequence: {Left,Right,Right}, from which a composition of functions can be built.

Here is how the built-in function RightComposition works with undefined functions.

(RightComposition@@{F,G,H})[x]

This example shows a clear contradiction, since there are two blank entries.

(g2=(RightComposition@@{GoLeft,GoRight,GoLeft})[g1])//display

The function BacktrackSequence, when given a nonempty sequence of GoLeft and GoRight functions, drops the last GoRight in the sequence (if any) until there are none, drops the last GoLeft, and finally appends a GoRight.

BacktrackSequence[x_]:=Module[
{go=x},
While[
go≠{}&&Last[go]==GoRight,
go=Drop[go,-1]
];
If[!go=={},go=Drop[go,-1]];
Append[go,GoRight]
]

Here is an example.

BacktrackSequence[{GoLeft,GoRight,GoLeft,GoRight,GoRight}]

In the next two functions, this kind of code tests for a list of lists of integers, a necessary condition for a Sudoku solution.

VectorQ[Flatten[g2,1]]

The function Backtrack goes left if applying the sequence go (a global variable with entries GoRight and GoRight) to the matrix with RightComposition does not contain an empty list {}; otherwise it backtracks using BacktrackSequence. If the new sequence applied to the matrix contains only numbers, Backtrack throws the matrix to the nearest containing Catch.

Backtrack[X_]:=Module[
{t},
go=If[
!MemberQ[Flatten[(RightComposition@@go)[X],1],{}],
Append[go,GoLeft],
BacktrackSequence[go]
];
t=(RightComposition@@go)[X];
If[VectorQ[Flatten[t,1]],Throw[t]];
go
]

We now use Backtrack inside the function BacktrackSolver, which initializes the global variable go.

BacktrackSolver[X_]:=Catch[
go={};
While[
!VectorQ[Flatten[(RightComposition@@go)[X],1]],
Backtrack[X]
]
]

Consider the following Sudoku puzzle.

(h={{1,\[Placeholder],\[Placeholder],\[Placeholder],9,8,\[Placeholder],4,\[Placeholder]},{\[Placeholder],2,\[Placeholder],\[Placeholder],5,\[Placeholder],\[Placeholder],9,\[Placeholder]},{3,\[Placeholder],8,\[Placeholder],\[Placeholder],\[Placeholder],6,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],5,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],9,6,\[Placeholder],4,2,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],9,\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],2,\[Placeholder],\[Placeholder],\[Placeholder],1,\[Placeholder],9},{\[Placeholder],8,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],6,\[Placeholder]},{\[Placeholder],1,\[Placeholder],8,7,\[Placeholder],\[Placeholder],\[Placeholder],3}})//display

(h1=MasterSolver[h])//display

We have failed so far to solve the puzzle using MasterSolver; so we try the backtracking technique.

BacktrackSolver[h1]//display

To see what sequence solved this puzzle, we only have to enter go.

go

We next try BacktrackSolver on g1 defined in the previous section.

BacktrackSolver[g1]//display

If we now enter go, we can see what sequence solved this puzzle.

go

Next is Evil Puzzle 8,076,199,743 from Web Sudoku [].

(i={{\[Placeholder],7,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],3,\[Placeholder]},{8,1,\[Placeholder],4,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],6},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],5,4,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],2,\[Placeholder],\[Placeholder],\[Placeholder],9},{\[Placeholder],\[Placeholder],9,1,5,4,2,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],8,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],7,9,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{2,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],6,\[Placeholder],7,5},{\[Placeholder],9,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],6,\[Placeholder]}})//display

(i1=MasterSolver[i])//display

BacktrackSolver[i1]//display

Again, the solving sequence is given by go.

go

This final puzzle was created by Arto Inkala, a mathematician based in Finland; it is claimed to be the world’s hardest Sudoku puzzle [].

(j={{8,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],3,6,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],7,\[Placeholder],\[Placeholder],9,\[Placeholder],2,\[Placeholder],\[Placeholder]},{\[Placeholder],5,\[Placeholder],\[Placeholder],\[Placeholder],7,\[Placeholder],\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],4,5,7,\[Placeholder],\[Placeholder]},{\[Placeholder],\[Placeholder],\[Placeholder],1,\[Placeholder],\[Placeholder],\[Placeholder],3,\[Placeholder]},{\[Placeholder],\[Placeholder],1,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],6,8},{\[Placeholder],\[Placeholder],8,5,\[Placeholder],\[Placeholder],\[Placeholder],1,\[Placeholder]},{\[Placeholder],9,\[Placeholder],\[Placeholder],\[Placeholder],\[Placeholder],4,\[Placeholder],\[Placeholder]}})//display

(j1=MasterSolver[j])//display

BacktrackSolver[j1]//display

Here is how this puzzle was solved.

go

There are many other techniques known to experienced Sudoku solvers that could be added to our programs; also backtracking could obviously be extended to triples, and so on.

Conclusion

Sudoku provides a superb opportunity to introduce useful programming techniques to students of Mathematica. Backtracking is one such technique that is largely absent from standard discussions of Mathematica programming but, as we have shown, is easily implemented in Mathematica when needed.

References

Web Sudoku. (Jan 18, 2018) www.websudoku.com.

Efamol. “Introducing the World’s Hardest Sudoku.” (Jan 18, 2018) www.efamol.com/efamol-news/news-item.php?id=43.