In[]:=
graphHints[g_] := Module[{m, n = Sqrt[Length[g]], pos, gra, info, s},​​m = Partition[Range[n^4], n^2]; ​​s = ResourceFunction["SudokuGraph"][n];(*position of hints*) ​​pos = Table[Extract[Flatten[m], Position[Flatten[g], i]], {i, 1, n^2}];​​(*additional connections to neighbours of cells with the same number*)​​gra = Flatten@Table[If[pos[[i]]=={},{ii},Thread[pos[[i, j]]  AdjacencyList[s, DeleteElements[pos[[i]], {pos[[i, j]]}]]]], {i, 1, Length[pos]}, {j, 1, Length[pos[[i]]]}];​​(*additional connections to cells with different number*)​​info = Flatten@Table[If[pos[[i]]=={},{ii},Thread[pos[[i, j]]  Flatten[Delete[pos, i]]]], {i, 1, Length[pos]}, {j, 1, Length[pos[[i]]]}];​​(*full graph*)​​GraphUnion[s, SimpleGraph@gra, SimpleGraph[info, VertexLabels  Thread[Range[n*n*n*n]  Flatten[g]]], VertexCoordinates  Thread[Flatten[Reverse[Partition[Range[n^4], n^2]]]  Reverse[Table[Reverse[Position[m, i][[1]]], {i, n^4, 1, -1}]]]]]
In[]:=
sudokuSolve[g_]:=Module[{c,pos,n=Sqrt[Length[g]],p,c2}, ​​c=FindVertexColoring[graphHints[g]]/.Thread[Range[9]ColorData[97,"ColorList"][[;;9]]];(*coloring*)​​pos=Table[Extract[Range[n^4],Position[Flatten[g],i]],{i,1,n^2}](*hints positions*);​​p=Table[If[pos[[i]]=={},0,c[[pos[[i,1]]]]i],{i,1,n^2}];​​c2=Partition[c/.DeleteElements[p,{0}],n^2];​​If[DeleteCases[Flatten[c2],_Integer]=={},c2,​​c2/.Thread[DeleteCases[DeleteDuplicates[Flatten[c2]],_Integer]DeleteElements[Range[9],DeleteDuplicates[Flatten[c2]]]]]]
In[]:=
hintsA={{0,0,0,0,0,4,1,8,2},{0,0,0,0,0,0,0,0,5},{8,0,0,0,0,9,0,0,0},{2,0,4,1,0,0,0,0,0},{0,0,0,0,0,0,7,0,4},{0,0,0,0,0,0,3,2,0},{0,0,0,7,0,8,4,0,0},{7,0,3,4,0,0,0,1,0},{5,0,0,0,2,1,0,0,9}};
In[]:=
sudokuSolve[hintsA]
Out[]=
{{6,7,9,5,3,4,1,8,2},{4,2,1,6,8,7,9,3,5},{8,3,5,2,1,9,6,4,7},{2,6,4,1,7,3,5,9,8},{3,1,8,9,5,2,7,6,4},{9,5,7,8,4,6,3,2,1},{1,9,2,7,6,8,4,5,3},{7,8,3,4,9,5,2,1,6},{5,4,6,3,2,1,8,7,9}}
In[]:=
​​hintsB={{9,8,0,0,0,0,0,0,3},{3,0,0,0,0,0,0,0,0},{0,0,0,0,7,0,0,0,0},{0,0,0,0,0,0,0,2,8},{6,0,2,8,0,0,7,9,0},{0,5,0,0,0,0,0,0,0},{0,7,8,3,0,5,2,0,0},{0,0,4,0,0,0,0,6,5},{0,0,0,0,0,4,0,8,0}};
In[]:=
sudokuSolve[hintsB]
Out[]=
{{9,8,7,5,2,6,4,1,3},{3,2,5,4,1,8,9,7,6},{4,1,6,9,7,3,8,5,2},{7,4,1,6,3,9,5,2,8},{6,3,2,8,5,1,7,9,4},{8,5,9,7,4,2,6,3,1},{1,7,8,3,6,5,2,4,9},{2,9,4,1,8,7,3,6,5},{5,6,3,2,9,4,1,8,7}}