Row By Row Solution of Sudoku Using Combinatorica`Backtrack or Outer and Select

Frank J. Kampas
fkampas@msn.com

Abstract

A Sudoku can be regarded as a Constraint Satisfaction Problem with 27 All-Different constraints.  Two methods of solving Sudoku are described.  Both start by generating the possibilities for each row which satisfy the constraints, consistent with the given values.  The first method then uses the "Backtrack" function in the Combinatorica package to build the solution row by row using the constraints.  The second method also builds the solution row by row, using "Outer" to find all possibilities for the partial solution and selecting out those which satisfy the constraints.  This notebook explains the two methods in detail.  The companion notebook compares the two for several test cases.

Introduction

As described in Wikipedia, "Backtracking is a general algorithm  for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution".  Backtracking is an important technique for solving constraint satisfaction problems, such as a Sudoku, which has 27 "All-Different Constraints".  This notebook explores the use of backtracking to solve a Sudoku and compares backtracking to a different approach which constructs all partial candidates simultaneously.

The Backtrack Function

The first step is loading the Combinatorica package

<<Combinatorica`

The "Backtrack" function takes 3 arguments:  a list of possible solutions for each component of the desired solution, a Boolean test for partial solutions and a Boolean test for a complete solution.

?Backtrack

Backtracking will be performed row by row, rather than element by element.  Therefore the solution space will consist of a list of 9 arrays, one for each row of the Sudoku.  Each array will contain all possible permutations of the numbers from 1 to 9 that satisfy the 27 All-Different Constraints, given the initial values.  The partialQ and solutionQ functions will implement the all-different constraints for partial and complete solutions, respectively.

Implementation of the Constraints

The given values in the Sudoku are specified in an array in which the unknown values are 0.

GivenValues={
{0,9,0,1,0,0,5,0,0},
{0,0,0,0,7,9,8,0,1},
{2,0,0,0,0,5,0,0,6},
{0,3,0,0,0,0,7,0,0},
{0,0,0,7,8,1,0,0,0},
{0,0,4,0,0,0,0,2,0},
{7,0,0,6,0,0,0,0,4},
{6,0,1,5,3,0,0,0,0},
{0,0,9,0,0,7,0,6,0}
};

The Mathematica equivalent of All-Different is the "Unequal" function, which returns False if its arguments are not all equal.

Unequal[1,2,3]

Unequal[1,2,1]

In order to illustrate the implementation of the All-Different Constraints, it is convenient to define a list of the numbers from 1 to 9 and an 9x9 array whose values indicate their position in the array.

OneToNine = Range[9]

MatrixForm[Positions = Outer[Plus, 10*OneToNine,OneToNine]]

It is not necessary to write an All-Different Constraint for the rows, since they will be constructed to satisfy that constraint.  A combined constraint for the columns can be written as

ColumnQ[l_List]:= And @@MapThread[Unequal,l]

The structure of this constraint can be understood by using a dummy function "f" and the Positions array to see how "MapThread" is used here.  The "And @@" Applies the function "And" to the results of "Unequal" for the nine columns.

MapThread[f,Positions]

The "And @@" construction works by replacing the "Head" of the List (which is List) by "And".

And @@ {True,False}

The All-Different Constraint for the 9 3x3 subarrays is more complicated.  It partitions the 9x9 array into 9 3x3 arrays, flattens the result and then repartitions the result into a list of 9 lists.  The argument of "Unequal" is "Sequence @@ #" since "Unequal" expects a sequence of arguments, not a list of arguments.  This is an example of the use of a "Pure Function" to modify a function, where # represents the new argument.  Note the use of the "/@" form which Maps the modified "Unequal" function onto the component lists.

SubMatQ[l_List]:=And @@ (Unequal[Sequence @@ #]& /@ Partition[Flatten[Partition[l,{3,3}]],9])

Partition[Flatten[Partition[Positions,{3,3}]],9]

The function SubMatQ has the problem that it only works correctly for an array in which the number of rows is a multiple of 3.  For example, if there were 8 rows, the rows numbered 7 and 8 are ignored.  This can be seen using the first 8 rows of the Positions array.

Partition[Flatten[Partition[Take[Positions,8],{3,3}]],9]

The problem is overcome by splicing extra rows from the end of the Positions array onto the partial array, since all the elements of the Positions array are greater than 9 and are all different from each other.  Note the use of "@" to denote that the SubMatQ takes the result of the Join as its argument.  I feel that this is easier to read in this situation than using brackets for functional dependence.

SubMatPartialQ[l_List]:= SubMatQ @ Join[l,Take[Positions,Length[l]-9]]

Construction of the Sample Space

The first step in the construction of the sample space is constructing all the possible permutations of 1 to 9 that have the given initial values in the correct places.  The simplest way to do this, by constructing all the possible permutations and then finding the subset with the initial values, is illustrated next.  This is done by converting the 0s to "_", which matches anything.  However, it is fairly slow, as shown here.

AbsoluteTiming[SampleSpaceSlow = Cases[Permutations[Range[9]], # /. 0 -> _]& /@  GivenValues;]

The following function, although more complicated, it much faster.  It constructs the permutations of the numbers in each row which aren't already specified and then inserts the given numbers into the result.

genRow[l_List]:=
Module[
{nz,cmp,perms},
(* Find the values and locations of the given elements *)
nz = Select[Thread[{l,OneToNine}],#[[1]]>0 &];
(* Find the numbers from 1 to 9 which aren't specified *)
cmp = Complement[OneToNine,nz[[All,1]]];
(* Find the permutations of the numbers not specified *) 
perms = Permutations[cmp];
(* Insert the specified numbers back in  *)
Fold[Insert[#1,Sequence @@ #2]&,#,nz]& /@perms
]

Note that the red caret inside the Insert function is Mathematica's way of complaining that I've only given two arguments to Insert instead of the expected 3.

?Insert

The repeated insertion is done with Fold, which expects a function with two arguments.  By using Sequence, I've made the second argument, which is a list of two values, into one component.  Note that the last line in genRow is an example of a Pure function nested inside another Pure function.

?Fold

?FoldList

As expected, using genRow is considerably faster and gives the same result as the slower method.  Since genRow takes a single row as an argument, it is mapped onto all the rows of GivenValues.

AbsoluteTiming[InitialSampleSpace = genRow /@ GivenValues;]

InitialSampleSpace == SampleSpaceSlow

By mapping the Length function onto the sample space, we can see how many possibilities there are for each row of the Sudoku, as this point.

Length /@ InitialSampleSpace

The rows generated for the sample space individually satisfy the All-Different Constraint for rows.  However, the rows may have values in them which are duplicated by given numbers in the same column or the same subarray.  These can be seen by taking the first candidate for each row in the sample space.  The 2 in the 3rd row, first column, is specified, so the candidates for the other rows should not have a 2 in the first column.

MatrixForm[InitialSampleSpace[[All,1]]]

In order to get rid of the sample space rows which violate the column and subarray constraints, it is necessary to construct an array which has the given values in it but has numbers not between 1 and 9 in the other positions so as to not interfere with the constraints.  This can be done using the Positions matrix.  Use of a Pure Function based on "If" avoids having to define a function which would only be used once.

MatrixForm[GivenAndPositions = MapThread[If[#1 ==0,#2,#1]&,{GivenValues,Positions},2]]

To test each candidate row, it is necessary to use it to replace the corresponding row in GivenAndPositions and implement the previously-defined constraints.  The argument n is the number of the row being tested.

TestQ[n_]:= (ColumnQ[#]&& SubMatQ[#])& @  ReplacePart[GivenAndPositions, n-> #]&

AbsoluteTiming @ Length[SampleSpace = Table[Select[InitialSampleSpace[[i]],TestQ[i]],{i,9}]]

The new sample space is considerably smaller than the original sample space.

Length /@SampleSpace

Running Backtrack and Checking the Solution

Having constructed the constraints and the sample space, it is now possible to run "Backtrack" to solve the Sudoku. It solves quite quickly.  The total time required for all the steps is less than a second on my computer.

AbsoluteTiming[MatrixForm[res=Backtrack[SampleSpace,(ColumnQ[#] && SubMatPartialQ[#])&,(ColumnQ[#] && SubMatQ[#])&]]]

MatchQ can be used to see if the solution has the correct given values by (once again) converting the 0s in GivenValues to "_" which matches anything.

?MatchQ

MatchQ[res,GivenValues /. x_/; x== 0 -> _]

Each row satisfies the All-Different Constraint

And @@ (Unequal[Sequence @@ #]& /@ res)

Each column satisfies the All-Different Constraint

ColumnQ[res]

The subarrays each satisfy the All-Different Constraint.

SubMatQ[res]

Outer And Select As An Alternative to Backtrack

An alternate approach to using Backtrack involves building up the final result row at a time, using "Outer" to generate all possibilities and the constraints to select out the partial solutions that satisfy them.  This approach can give all solutions, rather than just one, but can possibly exhaust all the available memory.

The first step will combine two rows but later steps will combined an array with an arrow.  This requires a modified "Join" function.

myJoin[l1_List, l2_List]:=
If[Length[Dimensions[l1]]==1,Join[{l1},{l2}],Join[l1,{l2}]]

This next function combines the existing partial solutions with the possibilities for the next row and selects the subset satisfying the constraints.

myOuter[l1_List, l2_List]:= Select[Flatten[Outer[myJoin,l1,l2,1],1],(ColumnQ[#] && SubMatPartialQ[#])&]

Only one solution is found (in a somewhat longer time) and it is the same as the solution found using "Backtrack".

AbsoluteTiming @ (foldres=Fold[myOuter,First[SampleSpace],Rest[SampleSpace]])

MatrixForm[foldres[[1]]]

res==foldres[[1]]

A number of tests are run in the companion notebook.  There it is seen that the method using Outer and Select generally runs somewhat faster than the method using Backtrack.

Conclusions

Two related approches to solving Sudoku have been demonstrated, illustrating some of the methods used in Constraint Satisfaction Programming.