Alejandra’s solution

code from above


DepthFirstSearch is slow

state update function

In[]:=
sudokuBlockMap=Association[Catenate[Map[​​Function[set,#->set&/@set​​],GatherBy[Tuples[{Range[9],Range[9]}],​​Position[Partition[Table[{i,j},​​{i,1,9},{j,1,9}],{3,3}],​​#][[1,1;;2]]&]]]];
In[]:=
SudokuStateQ[state_,{row_,col_},val_​​]:=And[​​!MemberQ[state[[row,All]],val],​​!MemberQ[state[[All,col]],val],​​!MemberQ[Map[state[[Sequence@@#]]&,​​sudokuBlockMap[{row,col}]],val]​​]
In[]:=
SudokuWriteNumber[state_,update_]:=If[​​SudokuStateQ[state,First[update],Last[update]],​​ReplacePart[state,update],Nothing]

testing

In[]:=
SudokuWriteNumber[puzzle,{1,1}->1]
Out[]=
{{1,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[]:=
SudokuWriteNumber[puzzle,{1,1}->4]
Out[]=
Nothing

Sort slots

cols=Transpose[ConstantArray[#,9]&/@Total[Sign[puzzle]]];
In[]:=
rows=ConstantArray[Total[#],9]&/@Sign[puzzle];
In[]:=
boxes=ArrayFlatten[Map[ConstantArray[Total[#,2],{3,3}]&,​​Partition[Sign[puzzle],{3,3}],{2}]];
In[]:=
solveWeights1=Times[cols,rows,boxes,1-Sign[puzzle]];
In[]:=
solveWeights2=Times[Plus[cols,rows,boxes],1-Sign[puzzle]];
In[]:=
solveWeights1//TableForm
Out[]//TableForm=
45
0
0
30
0
30
0
0
60
0
12
6
6
4
6
8
16
12
27
36
18
18
12
0
24
0
0
0
24
12
36
24
0
12
0
18
12
16
8
0
16
0
8
16
12
18
0
12
0
24
36
12
24
0
0
0
24
0
12
18
18
36
27
12
16
8
6
4
6
6
12
0
60
0
0
30
0
30
0
0
45
In[]:=
solveWeights2//TableForm
Out[]//TableForm=
11
0
0
10
0
10
0
0
12
0
8
6
6
5
6
7
9
8
9
10
8
8
7
0
9
0
0
0
9
7
10
9
0
7
0
8
7
8
6
0
8
0
6
8
7
8
0
7
0
9
10
7
9
0
0
0
9
0
7
8
8
10
9
8
9
7
6
5
6
6
8
0
12
0
0
10
0
10
0
0
11
In[]:=
SudokuLevelsData[weightMatrix_]:=Map[​​Function[ind,ind->#&/@Range[9]],​​Keys[ReverseSort[DeleteCases[Association[​​Catenate[MapIndexed[Rule[#2,#1]&,​​weightMatrix,{2}]]],0]]]]
In[]:=
Apply[Labeled,Reverse[AbsoluteTiming[​​g1=Graph[ResourceFunction["DepthFirstSearch"][SudokuWriteNumber,​​puzzle,SudokuLevelsData[solveWeights1][[1;;2^#]],True&,1,True]["Edges"]]]]]&/@{1,2,3,4,5}
Out[]=

0.002298
,
0.002418
,
0.00249
,
0.030494
,
0.683047

In[]:=
Apply[Labeled,Reverse[AbsoluteTiming[​​g2=Graph[ResourceFunction["DepthFirstSearch"][SudokuWriteNumber,​​puzzle,SudokuLevelsData[solveWeights2][[1;;2^#]],True&,1,True]["Edges"]]]]]&/@{1,2,3,4,5}
Out[]=

0.002402
,
0.002714
,
0.00287
,
0.01899
,
3.24226


bad heuristics:

Algorithm needs about 60,000 edges, not fast.

Using DancingLinksX

Encode time:

Time / complexity tests:

remove extra sort order:

MRV Heuristic:

right-nearest column

Equivalent solutions:

Packaging and decoding:

comparison with Alejandra:

The faster time isn’t even compiled here!