This  notebook is meant to solve a Sudoku  game. The Sudoku matrix has to be input like a normal 9x9 matrix in Mathematica with 0 for the empty entries (see the examples in the Game section). 
The routine RunGame fills the matrix or sends a message that the matrix cannot be completed. Only the final matrix is displayed.
The routine RunGameWithTracking  shows in addition also the number of entries that are currently to be filled.  Each time these numbers grow this means that backtracking has occurred and the previous decisions have to be modified.

    Before playing you need to run the Routines

Routines

countzero[A_]:=Length[Flatten[Map[Select[#, #==0 &]&,A]]]

RunGame[A_]:=Module[{ },tracking=False;endofgame=False;search[A];If[!endofgame, Print["impossible matrix"]]]

RunGameWithTracking[A_]:=Module[{ },
tracking=True;endofgame=False;search[A];If[!endofgame, Print["impossible matrix"]]]

search[A_]:=Module[{AA,finished,multiple,impossible,choices, k1,k2,values,i},
     {AA,finished,multiple,impossible,choices}=fillmatrixroutine[A];If[tracking,Print[countzero[AA]]];(*Print[ {AA,finished,multiple,impossible}];*)
     endofgame=finished;
     If[! finished,
          If[ ! impossible,
                If[ multiple,
                      {{k1,k2},values}=choices[[1]];(*Print[  {{k1,k2},values}];*)
                        For[i=1, i≤Length[values] && !endofgame , i++,(*Print["within for, i=",i]; *)AA[[k1,k2]]=values[[i]];search[AA]]
                      ,Print["wrong behaviour of logical variables"]
                  ]
              ]
          ]
]

fillmatrix[A_]:=Module[{AA,choices,impossible,multiple,singlechoices,i,j,k,finished},
impossible=False;
multiple=False;
finished= False;
AA=A;
While[ !impossible && ! multiple && ! finished,
            choices=Map[{#,commonmissing[threesets[AA,#[[1]],#[[2]]]]}&,Position[AA,0]];
            finished= choices =={};
            If[ finished,
                  Print["final matrix "]
            ,
                 impossible= ! Select[choices, #[[2]]=={} &]== {};
                  If[impossible,
                        Print["impossible ! "]
                     ,
                      singlechoices=Select[choices, Length[#[[2]]]==1 &];
                      multiple=  singlechoices == {};
                       If[multiple ,
                            Print["following multiple choices",choices, " for the matrix"]
                          ,
                             Do[ {{i,j},{k}}=singlechoices[[h]];
                                    AA[[i,j]]=k ,{h,Length[singlechoices]}];
                            impossible= !checkmatrix[AA,False];
                              If[impossible,Print["impossible ! "]]
                         ]
                    ]
                  ] 
            ];
AA
]

fillmatrixroutine[A_]:=Module[{AA,choices,impossible,multiple,singlechoices,i,j,k,finished},
impossible=False;
multiple=False;
finished= False;
AA=A;
While[ !impossible && ! multiple && ! finished,
            choices=Map[{#,commonmissing[threesets[AA,#[[1]],#[[2]]]]}&,Position[AA,0]];
            finished= choices =={};
            If[ finished,
                  Print["final matrix "];Print[MatrixForm[AA]];
            ,
                 impossible= ! Select[choices, #[[2]]=={} &]== {};
                  If[! impossible,
                      singlechoices=Select[choices, Length[#[[2]]]==1 &];
                       multiple=  singlechoices == {};
                       If[ ! multiple    ,
                             Do[ {{i,j},{k}}=singlechoices[[h]];
                                    AA[[i,j]]=k ,{h,Length[singlechoices]}];
                            impossible= !checkmatrix[AA,False];
                         ]
                    ]
                  ] 
            ];
{AA,finished, multiple,impossible,choices}
]

checkmatrix[A_,mess_]:=Module[{testpassed,firstfailure },
    testpassed=True;
    firstfailure=True;
     For[i=1, i≤9 && testpassed, i++, testpassed=checkset[A[[i]]]  ];
    If[mess && !testpassed && firstfailure, firstfailure=False;Print["row ",i-1," wrong"]];
    If[testpassed,
         For[i=1, i≤9 && testpassed, i++, testpassed=checkset[Transpose[A][[i]]]  ]
       ];
   If[mess && !testpassed && firstfailure, firstfailure=False;Print["column ",i-1," wrong"]];
   If[testpassed,
         For[i=1, i≤9 && testpassed, i++, testpassed=checkset[submatrix[A,i]  ] ]
      ] ;
   If[mess && !testpassed && firstfailure, firstfailure=False;Print["submatrix ",i-1," wrong"]];
   testpassed
]

checkset[a_]:=Module[{b,c},
b=Select[a, #>0 &];
c=Union[b];
Length[b]==Length[c]
]

submatrix[A_,i_]:=Module[{},
Which[i==1, Flatten[Take[Transpose[Take[A,{1,3}]],{1,3}]],
             i==2, Flatten[Take[Transpose[Take[A,{1,3}]],{4,6}]],
             i==3, Flatten[Take[Transpose[Take[A,{1,3}]],{7,9}]],
             i==4, Flatten[Take[Transpose[Take[A,{4,6}]],{1,3}]],
             i==5, Flatten[Take[Transpose[Take[A,{4,6}]],{4,6}]],
             i==6, Flatten[Take[Transpose[Take[A,{4,6}]],{7,9}]],
             i==7, Flatten[Take[Transpose[Take[A,{7,9}]],{1,3}]],
             i==8, Flatten[Take[Transpose[Take[A,{7,9}]],{4,6}]],
             i==9, Flatten[Take[Transpose[Take[A,{7,9}]],{7,9}]]
           ]
]

threesets[A_,i_,j_]:=Module[{rowset,colset,matset},
       rowset=A[[i]];
       colset=Transpose[A][[j]];
        matset=submatrix[A,3 (Ceiling[i/3]-1)+Ceiling[j/3]];
{rowset,colset,matset}
]

commonmissing[{a_,b_,c_}]:=
Intersection[Complement[Range[9],a],Complement[Range[9],b],Complement[Range[9],c]]

Game

A=Table[0,{9},{9}]

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

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

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

RunGame[A]

RunGameWithTracking[A]