These functions are explained in detail in the companion notebook.

Set Up

Functions to Generate the Sample Space

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

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

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

genRow[l_List, OneToNine_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
]

Function For Refining the Solution Space

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

Function To Build the Solution Using Backtrack

<<Combinatorica`

BacktrackSolve[GivenValues_List]:=
Module[
{OneToNine = Range[9],Positions,InitialSampleSpace, GivenAndPositions, SampleSpace},
Positions = Outer[Plus, 10*OneToNine,OneToNine];
InitialSampleSpace = genRow[#,OneToNine]& /@ GivenValues;
GivenAndPositions = MapThread[If[#1 ==0,#2,#1]&,{GivenValues,Positions},2];
SampleSpace = Table[Select[InitialSampleSpace[[i]],TestQ[i,GivenAndPositions]],{i,9}];
Backtrack[SampleSpace,(ColumnQ[#] && SubMatPartialQ[#,Positions])&,(ColumnQ[#] && SubMatQ[#])&]
]

Functions To Build the Solution Using Outer and Select

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

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

OuterSolve[GivenValues_List]:=
Module[
{OneToNine = Range[9],Positions,InitialSampleSpace, GivenAndPositions,SampleSpace},
Positions = Outer[Plus, 10*OneToNine,OneToNine];
InitialSampleSpace = genRow[#,OneToNine]& /@ GivenValues;
GivenAndPositions = MapThread[If[#1 ==0,#2,#1]&,{GivenValues,Positions},2];
SampleSpace = Table[Select[InitialSampleSpace[[i]],TestQ[i,GivenAndPositions]],{i,9}];
Fold[myOuter[#1,#2,Positions]&,First[SampleSpace],Rest[SampleSpace]]
]

A function to facilitate entering the given values.

ConvertString[l_List]:=ToExpression[Characters /@ l]

Tests

Test 1

t1str = {"090100500","000079801","200005006","030000700","000781000","004000020","700600004","601530000","009007060"};

MatrixForm[t1=ConvertString[t1str]]

AbsoluteTiming[MatrixForm[BacktrackSolve[t1]]]

AbsoluteTiming[MatrixForm /@ OuterSolve[t1]]

Test 2

t2str = {"010700400","006001000","090008002","900000100","260509073","003000004","500300060","000900700","008002030"};

MatrixForm[t2=ConvertString[t2str]]

AbsoluteTiming[MatrixForm[BacktrackSolve[t2]]]

AbsoluteTiming[MatrixForm /@ OuterSolve[t2]]

Test 3

t3str={"107000602","060010090","900000008","005602100","000000000","001503800","300000004","080030050","504000201"};

MatrixForm[t3=ConvertString[t3str]]

AbsoluteTiming[MatrixForm[BacktrackSolve[t3]]]

AbsoluteTiming[MatrixForm /@ OuterSolve[t3]]

Test 4

t4str = {"000010002","000000531","013900400","070005640","000608000","038200090","006004310","185000000","300060000"};

MatrixForm[t4=ConvertString[t4str]]

AbsoluteTiming[MatrixForm[BacktrackSolve[t4]]]

AbsoluteTiming[MatrixForm /@ OuterSolve[t4]]