Solving via DancingLinksX

In[]:=
QueensCoverMatrix[dim_]:=Module[{locs,columns,rowValues},​​locs=ReplaceAll[Tuples[{Range[dim],Range[dim]}],​​{x_,y_}:>{r[x],c[y],d[x+y],b[x-y]}];​​columns=Union[Sort[Catenate[locs]]];​​rowValues=Join[​​Map[#->1&,locs,{2}],​​{#->1}&/@Cases[columns,​​Alternatives[b,d][_]]​​];​​Map[columns/.Append[#,​​Alternatives[r,b,c,d][_]:>0]&,​​rowValues]​​]

This is not especially fast

(possibly due to extra diagonal items?)

AbsoluteTiming[​​Length[ResourceFunction["FindExactCover"][​​QueensCoverMatrix[8],All,​​Method->#]]​​]&/@{"DancingLinksX","CliqueToCover","BranchAndPrune"}
Out[]=
{{1.09272,92},{9.83766,92},{1.45901,92}}

Get the search-tree

(using Queens Graph this time)

In[]:=
outComps[n_]:=outComps[n]=With[​​{qg=ResourceFunction["QueensGraph"][n]},​​Association[​​#->VertexOutComponent[​​qg,#,{1}]&/@VertexList[qg]]​​];
In[]:=
addPosition[n_][pos_,next_]:=If[​​MemberQ[​​Apply[Union,Lookup[outComps[n],pos]],​​next],​​Nothing,​​Append[pos,next]​​]
In[]:=
qgVertexList[n_]:=Range[n^2]
In[]:=
initData[n_]:={addPosition[n],{},​​Partition[qgVertexList[n],n],​​True&,All,True​​}

Faster than before:

In[]:=
AbsoluteTiming[​​Length[Apply[ResourceFunction["DepthFirstSearch"],​​Most[initData[8]]]]​​]
Out[]=
{0.790002,92}

Same vertex count:

In[]:=
sg=Graph[Apply[ResourceFunction["DepthFirstSearch"],​​initData[8]]["Edges"],AspectRatio->2/3,​​GraphLayout->"LayeredDigraphEmbedding"]
Out[]=
In[]:=
VertexCount[sg]
Out[]=
2057

This does nothing:

In[]:=
sg2=Graph[Apply[ResourceFunction["DepthFirstSearch"],​​ReplacePart[initData[8],3->Map[RandomSample,initData[8][[3]]]]​​]["Edges"],AspectRatio->2/3,​​GraphLayout->"LayeredDigraphEmbedding"]
Out[]=

Different Vertex Count:

In[]:=
sg3=Graph[Apply[ResourceFunction["DepthFirstSearch"],​​ReplacePart[initData[8],3->RandomSample[initData[8][[3]]]]​​]["Edges"],AspectRatio->2/3,​​GraphLayout->"LayeredDigraphEmbedding"]
Out[]=
In[]:=
VertexCount@sg2
Out[]=
2371

Count of different input sorts:

In[]:=
8!
Out[]=
40320