1.将网上下载的dlx求解c程序添加int sudoku(const char *s,char *r)函数处理81个字符长的数独题目字符串
#include<cstdio>#include<cstring>#include<ctime>intcnt=0;constintXSIZE=3;constintSIZE=XSIZE*XSIZE;constintMAX_C=SIZE*SIZE*4;//最大列constintMAX_R=SIZE*SIZE*SIZE;//最大行constintMAX_SUDOKU=SIZE*SIZE;//数独矩阵大小constintMAX_LINK=MAX_C*MAX_R;//链表最大范围intL[MAX_LINK],R[MAX_LINK],U[MAX_LINK],D[MAX_LINK];//抽象链表intC[MAX_LINK],O[MAX_LINK],S[MAX_C],H[MAX_R];//C&O代表列&行，S每一列的节点数，H每一行的第一个节点intNodeNumber,RecordNumber;//用来指向节点intstate[MAX_SUDOKU],ans[MAX_SUDOKU],record[MAX_SUDOKU];//////////////////////Dancing Links模版//////////////////////voidinit(void);//Dancing Links的抽象链表初始化voidinsert(int,int);//在链表的一个位置中添加标记voidremove(int);//删除一列，同时删除这一列中的行voidresume(int);//恢复一列，同时恢复这一列中的行//////////////////////Dancing Links模版//////////////////////boolinput(void){chars[82]="";if(scanf("%s",s)==EOF)returnfalse;printf("Q %s\n",s);for(inti=0;i<81;i++)state[i]=s[i]-'0';returntrue;/* char buffer[SIZE+1][SIZE+1];//留一个空间 if(scanf("%s",buffer[0])==EOF) return false; for(int i=1;i<SIZE;i++) scanf("%s",buffer[i]); memset(state,0,sizeof(state)); for(int i=0;i<SIZE;i++) for(int j=0;j<SIZE;j++) { if(buffer[i][j]!='0') state[i*SIZE+j]=buffer[i][j]-'0'; } return true; */}voidadd(inti,intj,intk){introw=i*MAX_SUDOKU+j*SIZE+k;insert(row,i*SIZE+j+1);//注意insert(row,i*SIZE+k+MAX_SUDOKU);insert(row,j*SIZE+MAX_SUDOKU*2+k);insert(row,(i/XSIZE*XSIZE+j/XSIZE)*SIZE+MAX_SUDOKU*3+k);}voidbuild(void){intpos,row;for(inti=0;i<SIZE;i++)for(intj=0;j<SIZE;j++){pos=i*SIZE+j;if(state[pos]!=0){add(i,j,state[pos]);}elseif(state[pos]==0){for(intk=1;k<=SIZE;k++){add(i,j,k);}}}}booldfs(intk){cnt++;if(!R[0]){RecordNumber=k;returntrue;}intcount=~(1<<31),c;for(inti=R[0];i;i=R[i]){if(S[i]<count){count=S[i];c=i;if(count==1)break;}}remove(c);for(inti=D[c];i!=c;i=D[i]){for(intj=R[i];j!=i;j=R[j]){remove(C[j]);}record[k]=O[i];if(dfs(k+1))returntrue;for(intj=L[i];j!=i;j=L[j]){resume(C[j]);}}resume(c);returnfalse;}voidoutput(void){for(inti=0;i<RecordNumber;i++){ans[(record[i]-1)/SIZE]=(record[i]-1)%SIZE+1;}for(inti=0;i<SIZE;i++){for(intj=0;j<SIZE;j++)printf("%-2d",ans[i*SIZE+j]);printf("\n");}}intsudoku(constchar*s,char*r){for(inti=0;i<81;i++)state[i]=s[i]-'0';init();build();dfs(0);for(inti=0;i<RecordNumber;i++){ans[(record[i]-1)/SIZE]=(record[i]-1)%SIZE+1;}for(inti=0;i<SIZE;i++){for(intj=0;j<SIZE;j++)r[i*SIZE+j]='0'+ans[i*SIZE+j];// printf("%-2d",ans[i*SIZE+j]);//printf("\n");}r[81]='\0';return0;}intmain1(){charr[82];sudoku("070680050000000001409507000560000340000000000034000017000703804300000000090015030",r);puts(r);return0;while(input()){cnt=0;time_tstart=clock();init();build();dfs(0);output();printf("Time:%ld dfs:%d\n",clock()-start,cnt);}return0;}//////////////////////Dancing Links模版//////////////////////voidinit(void){for(inti=0;i<=MAX_C;i++){L[i]=i-1;R[i]=i+1;U[i]=i;D[i]=i;C[i]=i;O[i]=0;}L[0]=MAX_C;R[MAX_C]=0;NodeNumber=MAX_C+1;memset(S,0,sizeof(S));memset(H,0,sizeof(H));}voidinsert(inti,intj){if(H[i]){L[NodeNumber]=L[H[i]];R[NodeNumber]=H[i];L[R[NodeNumber]]=NodeNumber;R[L[NodeNumber]]=NodeNumber;}else{L[NodeNumber]=NodeNumber;R[NodeNumber]=NodeNumber;H[i]=NodeNumber;}U[NodeNumber]=U[j];D[NodeNumber]=j;U[D[NodeNumber]]=NodeNumber;D[U[NodeNumber]]=NodeNumber;C[NodeNumber]=j;O[NodeNumber]=i;S[j]++;NodeNumber++;}voidremove(intc){L[R[c]]=L[c];R[L[c]]=R[c];for(inti=D[c];i!=c;i=D[i]){for(intj=R[i];j!=i;j=R[j]){U[D[j]]=U[j];D[U[j]]=D[j];S[C[j]]--;}}}voidresume(intc){for(inti=U[c];i!=c;i=U[i]){for(intj=L[i];j!=i;j=L[j]){U[D[j]]=j;D[U[j]]=j;S[C[j]]++;}}L[R[c]]=c;R[L[c]]=c;}/* 070680050 000000001 409507000 560000340 000000000 034000017 000703804 300000000 090015030 */编译执行，验证函数的正确性。
gcc dlx_line.cpp -o dlxline dlx_line.cpp: In function 'int main()': dlx_line.cpp:154:8: warning: ISO C++ forbids converting a string constant to 'char*' [-Wwrite-strings] 154 | sudoku("070680050000000001409507000560000340000000000034000017000703804300000000090015030",r); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ root@66d4e20ec1d7:/par/cppext# ./dlxline 273681459685349721419527683561978342927134568834256917152763894346892175798415236使用官方的c++ quack插件模板程序, 在quack_extension.cpp文件中添加#include "dlx_line.cpp"和#include <string>，并修改QuackScalarFun函数，其余不动。我用的是1.3版本，其他版本的函数也许不同。
...#include"dlx_line.cpp"#include<string>namespaceduckdb{inlinevoidQuackScalarFun(DataChunk&args,ExpressionState&state,Vector&result){auto&name_vector=args.data[0];UnaryExecutor::Execute<string_t,string_t>(name_vector,result,args.size(),[&](string_t name){charr[82];sudoku(name.GetString().c_str(),r);string r1=r;returnStringVector::AddString(result,"Suduku "+name.GetString()+"solved "+r1);//return StringVector::AddString(result, "Quack "+name.GetString()+" 🐥");});}编译和转换为插件, 注意转换时插件名还沿用quack, 不要修改，否则装载插件会报错。appmeta.py是官方的python脚本
root@66d4e20ec1d7:/par/cppext# g++ -fPIC -shared -o libsudoku2.so quack_extension.cpp -I /par/include -lssl -lcrypto -I include -lduckdb -L /par/ -I /par/duckdb-0.10.3/include -lgmp root@66d4e20ec1d7:/par/cppext# python3 /par/appmeta.py -l libsudoku2.so -n sudoku -dv v1.3.0 --duckdb-platform linux_arm64 --extension-version 0.1 --abi-type "" Creating extension binary: - Input file: libsudoku2.so - Output file: sudoku.duckdb_extension - Metadata: - FIELD8 (unused) = EMPTY - FIELD7 (unused) = EMPTY - FIELD6 (unused) = EMPTY - FIELD5 (abi_type) = - FIELD4 (extension_version) = 0.1 - FIELD3 (duckdb_version) = v1.3.0 - FIELD2 (duckdb_platform) = linux_arm64 - FIELD1 (header signature) = 4 (special value to identify a duckdb extension) root@66d4e20ec1d7:/par/cppext# /par/duckdb130 -unsigned DuckDB v1.3.0 (Ossivalis) 71c5c07cdd Enter ".help" for usage hints. D load '/par/cppext/sudoku.duckdb_extension'; IO Error: Extension '/par/cppext/sudoku.duckdb_extension' did not contain the expected entrypoint function 'sudoku_init' D root@66d4e20ec1d7:/par/cppext# python3 /par/appmeta.py -l libsudoku2.so -n quack -dv v1.3.0 --duckdb-platform linux_arm64 --extension-version 0.1 --abi-type ""执行, 可以输入字符串字面量，也可以从表中读取
DuckDB v1.3.0 (Ossivalis) 71c5c07cdd Enter ".help" for usage hints. D load '/par/cppext/quack.duckdb_extension'; D select quack('070680050000000001409507000560000340000000000034000017000703804300000000090015030'); ┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ quack('070680050000000001409507000560000340000000000034000017000703804300000000090015030') │ │ varchar │ ├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤ │ Suduku 070680050000000001409507000560000340000000000034000017000703804300000000090015030solved 273681459685349721419527683561978342927134568834256917152763894346892175798415236 │ └──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘ Run Time (s): real 0.025 user 0.052000 sys 0.000000 D select quack(replace(replace(puzzle,'?','0'),chr(10),'')) a from sudoku9_9 limit 1; ┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ a │ │ varchar │ ├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤ │ Suduku 102005067684790150759621000060008205578230640291540003045900018810057020907010530solved 132485967684793152759621384463178295578239641291546873345962718816357429927814536 │ └──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘ Run Time (s): real 0.001 user 0.004000 sys 0.000000插件与原生c程序比较性能
D copy(select quack(p) a from read_csv('/par/1224/0114/sudoku17.txt',header=0)t(p)) to 'result17.txt'; 100% ▕████████████████████████████████████████████████████████████▏ Run Time (s): real 7.844 user 15.656000 sys 0.000000 root@66d4e20ec1d7:/par/cppext# time /par/dlxline < /par/1224/0114/sudoku17.txt > reult17.txt real 0m2.797s user 0m2.716s sys 0m0.052s可见，尽管插件并行执行了，用时还是原生c程序的约3倍，这是因为标量函数每次执行都有切换数据库上下文的开销。4万9千行就切换了这么多次。
