
<<DiscreteMath`Combinatorica`;

reserved[li_List]:= Union[Flatten[Select[Subsets[(Flatten[{#1},1]&)/@
  (#1 /. {j_List->j, i_Integer-> Sequence[]}&)/@li], Length[#1]===Length[Union@@#1]&]]];


blokje[m_,r_,c_]:=Take[m,{1+3*Floor[r/3-1/3],3+3*Floor[r/3-1/3]},{1+3*Floor[c/3-1/3],3+3*Floor[c/3-1/3]}];

inx[r_, c_] := 
  Table[{x, y}, {x, 1 + 3*Floor[r/3 - 1/3], 3 + 3*Floor[r/3 - 1/3]}, 
  {y, 1+3*Floor[c/3-1/3],3+3*Floor[c/3-1/3]}];

putblok[m_, new_, {r_, c_}] := Block[{},
  kandi = ReplacePart[m, new , Flatten[inx[r, c], 1], Flatten[inx[1, 1], 1]  ] ];

putrow[m_, new_, r_] := Block[{},
  kandi = ReplacePart[m, new , Table[{r, c}, {c, 9}], Table[{c}, {c, 9}]   ] ];

putcol[m_, new_, c_] := Block[{},
  kandi = ReplacePart[m, new , Table[{r, c}, {r, 9}], Table[{r}, {r, 9}]   ] ];

elimblok[{x_, y_}, q_] := Block[{},
  kandi = putblok[kandi, blokje[kandi, x, y] /. q -> Sequence[], {x, y}] ];

elimrow[r_, q_] := Block[{},
  kandi = putrow[kandi, Part[kandi, r, All] /. q -> Sequence[], r] ];

elimcol[c_, q_] := Block[{},
  kandi = putcol[kandi, Part[kandi, All, c] /. q -> Sequence[], c] ];



sudokutest[mat2_?MatrixQ] := FreeQ[mat2,{}] &&
  Union@Flatten[{Map[PermutationQ, {mat2, Transpose[mat2]}, {2}], 
          Map[PermutationQ, 
            Table[Flatten@blokje[mat2, 3r, 3c], {r, 3}, {c, 3}], {2}]}] === {True};

consistentQ[li_] := 
  And[
       FreeQ[li, {}],
       Union@Flatten[{Map[
            PermutationQ[Union[Flatten[#]]] &, {li, Transpose[li]}, {2}], 
          Map[PermutationQ[Union[Flatten[#]]] &, 
            Table[Flatten@blokje[li, 3r, 3c], {r, 3}, {c, 
                3}], {2}]}] === {True}, 
        Union@Flatten[{Map[ 		
        	Apply[UnsameQ,Sort[Cases[#/.{q_Integer}->q,_Integer]]]&, {li,Transpose[li]},{2}],
 		Map[Apply[UnsameQ,Sort[Cases[#/.{q_Integer}->q,_Integer,{1}]]]&,
   		Table[Flatten[blokje[li,3r,3c],1],{r,3},{c,3}],{2}]}] === {True}
  ];

(* START main, Options:: steps->False|True, levels->False|True *)

sudoku[mat_ /; (MatchQ[mat, Table[_Integer, {9}, {9}]] && Max[mat] <= 9 && 
          Min[mat] >= 0), opts___] := 
  Module[{}, mat2 = mat1 = mat; kandi = Table[Range[9], {9}, {9}]; 
    oldkandi = Table[{0}, {9}, {9}]; lev={};niv=1;
Options[sudoku] = { steps-> False, levels -> False };

Catch[


 While[kandi =!= oldkandi &&  consistentQ[kandi] , (* lev 4 *)
  While[kandi =!= oldkandi &&  consistentQ[kandi] , (* lev 3 *)
   While[kandi =!= oldkandi &&  consistentQ[kandi] , (* lev 2 *)
    While[kandi =!= oldkandi &&  consistentQ[kandi] , (* lev 1 *)

AppendTo[lev,niv];

If[And[(steps/.{opts}/.Options[sudoku])=!=False , mat2=!=mat1],
	(* previous in black, latest in red *)
	out=MapAt[StyleForm[#,FontColor->Hue[0],FontWeight->Bold]&,mat2,Position[mat2-mat1,_?Positive,{2}]];
	Print[MatrixForm[out],Last[lev]]];
	mat1=mat2;
	

	niv=1; oldkandi = kandi;
      mat2 = 
        Map[(# /. {_Integer, _Integer..} -> 0) &, (kandi = 
                MapAt[0 &, 
                    Table[Complement[Flatten[{Part[kandi, r, c]}], 
                        Flatten[blokje[mat2, r, c]], Part[mat2, All, c], 
                        Part[mat2, r, All]], {r, 9}, {c, 9}], 
                    Position[mat2, _?Positive, {2}]] + 
                  mat2), {2}] /. {i_Integer} -> i;

       If[!consistentQ[kandi],Throw[0]]; 
    ]; (* lev 1 *)

	niv=2;oldkandi = kandi; 
      mat2 = 
        Map[(# /. {} -> 0) &, (obligado= 
                MapAt[0 &, 
                    Table[Intersection @@ (Complement[
                                Flatten[{Part[kandi, r, 
                                      c]}], #] & /@ {Flatten[
                                blokje[MapAt[{} &, kandi, {r, c}], r, c]], 
                              Part[MapAt[{} &, kandi, {r, c}], All, c], 
                              Part[MapAt[{} &, kandi, {r, c}], r, All]}), {r, 
                        9}, {c, 9}], Position[mat2, _?Positive, {2}]] + 
                  mat2), {2}] /. {i_Integer} -> i;
      kandi=MapAt[0&,kandi,Position[mat2,_?Positive,{2}]]+(mat2);
    If[!consistentQ[kandi],Throw[0]];     
   ]; (* lev 2 *)
	
	niv=3; oldkandi = kandi; 
      mat2 = 
        Map[(# /. {_Integer, _Integer..} -> 0) &, (kandi = 
                MapAt[0 &, 
                    Table[Intersection @@ (Complement[
                                Flatten[{Part[kandi, r, c]}], 
                                reserved[#]] & /@ {Flatten[
                                blokje[MapAt[0 &, kandi, {r, c}], r, c], 1], 
                              Part[MapAt[0 &, kandi, {r, c}], All, c], 
                              Part[MapAt[0 &, kandi, {r, c}], r, All]}), {r, 
                        9}, {c, 9}], Position[mat2, _?Positive, {2}]] + 
                  mat2), {2}] /. {i_Integer} -> i;

       If[!consistentQ[kandi],Throw[0]]; 
  ]; (* lev 3 *)

	niv=4; oldkandi = kandi; mat1=(mat2 /. StyleForm[i_Integer,__]->i); mat2=mat1;
	Do[mem = blokje[kandi, r, c]; 
 	 it = Take[Position[mem, #, {-1}], All, 2] & /@ Range[9]; 
 	 Cases[it, f:{{a_, _}, {a_, _}..} :> elimrow[a + r - 1, Position[it, f][[1, 1]]]];
 	  Cases[it,f:{{_, a_}, {_, a_}..} :> elimcol[a + c - 1, Position[it, f][[1, 1]]]];
	  putblok[kandi, mem, {r, c}],{r, 1, 9, 3}, {c, 1, 9, 3}];

       If[!consistentQ[kandi],Throw[0]]; 

	Do[mem = Part[kandi, r, All]; 
  	it = Take[Position[Partition[mem, 3], #, {-1}], All, 2] & /@ Range[9]; 
  	Cases[it, f:{{a_, _}, {a_, _}..} :> elimblok[{r, 3a}, Position[it, f][[1, 1]]]];
	  putrow[kandi, mem, r],
	 {r, 9}];

       If[!consistentQ[kandi],Throw[0]]; 

	Do[mem = Part[kandi, All, c]; 
 	 it = Take[Position[Partition[mem, 3], #, {-1}], All, 2] & /@ Range[9]; 
  	Cases[it,f:{{a_, _}, {a_, _}..} :> elimblok[{3a, c}, Position[it, f][[1, 1]]]];
 	 putcol[kandi, mem, c],
	 {c, 9}];

	If[!consistentQ[kandi],Throw[0]]; 

      mat2 = 
        Map[(# /. {_Integer, _Integer..} -> 0) &, (kandi),{2}]/. {i_Integer} -> i;
 ]; (* lev 4 *)

]; (* end catch *)
	 (* all levels tried with no change, finished or give up *)
    If[(levels/.{opts}/.Options[sudoku])=!=False,Print[lev]];
    If[sudokutest[mat2]===True, MatrixForm[mat2], If[consistentQ[kandi],MatrixForm[kandi],{{}}] ] 
];