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[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[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}, 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=Partition[c/.Table[c[[pos[[i,1]]]]->i,{i,1,n^2}],n^2](*solution*)]
In[]:=
puzzle={{0,4,3,0,8,0,2,5,0},{6,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,9,4},{9,0,0,0,0,4,0,7,0},{0,0,0,6,0,8,0,0,0},{0,1,0,2,0,0,0,0,3},{8,2,0,5,0,0,0,0,0},{0,0,0,0,0,0,0,0,5},{0,3,4,0,9,0,7,1,0}};
In[]:=
sudokuSolve[puzzle]
Out[]=
{{1,4,3,9,8,6,2,5,7},{6,7,9,4,2,5,3,8,1},{2,8,5,7,3,1,6,9,4},{9,6,2,3,5,4,1,7,8},{3,5,7,6,1,8,9,4,2},{4,1,8,2,7,9,5,6,3},{8,2,1,5,6,7,4,3,9},{7,9,6,1,4,3,8,2,5},{5,3,4,8,9,2,7,1,6}}