8x8 Attacking Queens Timings:
8x8 Attacking Queens Timings:
System:
System:
In[]:=
AbsoluteTiming[FindIndependentVertexSet[ResourceFunction["QueensGraph"][8],{8},All]//Length]
Out[]=
{0.397034,92}
WFR:
WFR:
queenCoversData[size_]:=Table[Flatten[ReplacePart[Table[If[Or[i==k,j==l,i+j==k+l,i-j==k-l],0,Blank[]],{i,Part[size,1]},{j,Part[size,2]}],{k,l}->1]],{k,Part[size,1]},{l,Part[size,2]}]
In[]:=
rowsCombine[r1_,r2_]:=Catch[MapThread[Function[{x,y},Switch[{x,y},{Verbatim[Blank[]],Blank[]},y,{Blank[],Verbatim[Blank[]]},x,{Blank[],Blank[]},If[x===y,x,Throw[Nothing]]]],{r1,r2}]]
AbsoluteTiming[ResourceFunction["DepthFirstSearch"][rowsCombine,ConstantArray[_,64],queenCoversData[{8,8}],True&,All]//Length]
Out[]=
{1.14994,92}
Counting nodes on search graph:
Counting nodes on search graph:
In[]:=
g1=Graph[ResourceFunction["DepthFirstSearch"][rowsCombine,ConstantArray[_,64],queenCoversData[{8,8}],True&,All,True]["Edges"],GraphLayout->"LayeredDigraphEmbedding",AspectRatio->2/3]
Out[]=
In[]:=
TreeGraphQ[g1]
Out[]=
True
In[]:=
VertexCount[g1]
Out[]=
2057
Disorder, try again:
Disorder, try again:
g2=Graph[ResourceFunction["DepthFirstSearch"][rowsCombine,ConstantArray[_,64],RandomSample[RandomSample/@queenCoversData[{8,8}]],True&,All,True]["Edges"],GraphLayout->"LayeredDigraphEmbedding",AspectRatio->2/3]
Out[]=
In[]:=
Count[GraphDistanceMatrix[g2][[Position[VertexList[g2],Verbatim@Select[VertexList[g2],VertexInDegree[g2,#]==0&][[1]]][[1,1]]]],8]
Out[]=
92
In[]:=
TreeGraphQ[g2]
Out[]=
True
In[]:=
VertexCount[g2]
Out[]=
3043