补充：我复制了[这位的题解](https://www.luogu.com.cn/blog/user33173/solution-p1784)，本地运行4测试点的回溯次数仅为202，而我的代码没能跑出来，同时我的其他节点回溯次数也很多。我不是很能看懂两个代码在逻辑上的区别。
然而，在对于洛谷题干中的那组过强数据、以及另外几组较难数据时，我的代码却又凑巧没有回溯。
有没有大佬那个提供一些回溯算法中较为有效的剪枝思路？
by Viottery @ 2022-11-23 23:41:39
这题不是dfs+回溯即可吗。。。。。
by Patron_Saint @ 2022-11-24 07:32:17
@[Viottery](/user/287266) 第103行和115行，你删除和回溯怎么是同一个方向的..
by hjxhjx @ 2022-11-24 07:39:02
还有就是你resume和remove怎么也是同一个方向..
by hjxhjx @ 2022-11-24 07:42:54
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
const int N=4e3+10,M=40;
int row[N],col[N],l[N],r[N],u[N],d[N];
int s[N];
int n,m;
int idx;
void init()
{
for(int i=0;i<=m;i++)
{
l[i]=i-1;
r[i]=i+1;
u[i]=d[i]=i;
}
l[0]=m;
r[m]=0;
idx=m+1;
return ;
}
void add(int x,int y,int &head,int &tail)
{
if(y==253)
{
int opt=0;
opt++;
}
row[idx]=x,col[idx]=y,s[y]++;
u[idx]=y,d[idx]=d[y],u[d[y]]=idx,d[y]=idx;
r[head]=l[tail]=idx;
l[idx]=head,r[idx]=tail;
tail=idx++;
return ;
}
void remove(int p)
{
l[r[p]]=l[p],r[l[p]]=r[p];
for(int i=d[p];i!=p;i=d[i])
{
for(int j=r[i];j!=i;j=r[j])
{
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
return ;
}
void resume(int p)
{
for(int i=u[p];i!=p;i=u[i])
{
for(int j=l[i];j!=i;j=l[j])
{
u[d[j]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
l[r[p]]=p,r[l[p]]=p;
return ;
}
int ans[N];
int a[10][10];
int tot;
bool dfs(int dep)
{
if(!r[0])
return true;
int p=r[0];
for(int i=r[0];i;i=r[i])
{
if(s[i]<s[p])
p=i;
}
remove(p);
for(int i=d[p];i!=p;i=d[i])
{
for(int j=r[i];j!=i;j=r[j])
remove(col[j]);
ans[dep]=row[i];
tot=dep;
if(dfs(dep+1))
return true;
for(int j=l[i];j!=i;j=l[j])
resume(col[j]);
}
resume(p);
return false;
}
int get(int x,int y)
{
return (x-1)/3*3+(y-1)/3;
}
int get_p(int x,int y)
{
return (x-1)*9+y;
}
struct str
{
int x,y,v;
str(int x=0,int y=0,int v=0)
{
this->x=x;
this->y=y;
this->v=v;
}
}pm[N];
int main()
{
int dep=0;
n=9;
m=81+81+81+81;
init();
int rp=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",get(i,j));
}
printf("\n");
}*/
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int l=1,r=9;
if(a[i][j]!=0)
l=r=a[i][j];
for(;l<=r;l++)
{
int k=l;
rp++;
pm[rp]=str(i,j,k);
int head=idx,tail=idx;
if(a[i][j]==k)
{
ans[++dep]=idx;
}
add(rp,get(i,j)*9+k,head,tail);
add(rp,81+(i-1)*9+k,head,tail);
add(rp,81*2+(j-1)*9+k,head,tail);
add(rp,81*3+get_p(i,j),head,tail);
}
}
}
/*for(int i=1;i<=dep;i++)
{
remove(col[ans[i]]);
for(int j=r[ans[i]];j!=ans[i];j=r[j])
remove(col[j]);
}*/
dfs(1);
for(int i=1;i<=tot;i++)
{
int p=ans[i];
a[pm[p].x][pm[p].y]=pm[p].v;
}
for(int i=1;i<=9;i++)
{
for(int j=1;j<=9;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
```
代码如上
by 1179083629dsm @ 2022-11-24 08:25:22
@[hjxhjx](/user/178480)
有些不理解，因为是第一次用DLX，这个的方向会有影响吗？我感觉没影响啊
还望能解释一下原因）谢谢！
by Viottery @ 2022-11-24 09:20:07
@[hjxhjx](/user/178480)
修改了回溯和删除的方向，确实解决问题了，感谢！但还是很不解..
by Viottery @ 2022-11-24 09:26:17
@[Viottery](/user/287266)
我之前也有过一样的错误，删除和回溯的方向一样会让链表完全乱掉 然后就T了
这个确实非常不好理解
by hjxhjx @ 2022-11-24 09:38:34
@[hjxhjx](/user/178480)
好的，感谢，我后面再自己研究一下）
by Viottery @ 2022-11-24 16:37:06
@[hjxhjx](/user/178480)
为什么我写的删除和回溯的方向一样就没事？
```cpp
inline void cover(node* t){
t = t -> col_root;
rdel(t);
for(register node* p = t -> down;p != t;p = p -> down){
for(register node* q = p -> right;q != p;q = q -> right){
cdel(q);
}
}
}
inline void uncover(node* t){
t = t -> col_root;
for(register node* p = t -> down;p != t;p = p -> down){
for(register node* q = p -> right;q != p;q = q -> right){
cadd(q);
}
}
radd(t);
}
bool solve(int k = 0){
if(head -> right == head){
ct = k;
return 1;
}
register node *pmin = head -> right;
for(register node* p = pmin -> right;p != head;p = p -> right){
if(pmin -> sum > p -> sum){
pmin = p;
}
}
if(pmin -> sum == 0){
return 0;
}
cover(pmin);
for(register node *p = pmin -> down;p != pmin;p = p -> down){
ans[k] = p -> row;
for(register node *q = p -> right;q != p;q = q -> right){
cover(q);
}
if(solve(k + 1)){
return 1;
}
for(register node *q = p -> right;q != p;q = q -> right){
uncover(q);
}
}
uncover(pmin);
return 0;
}
```
by yangwuqi @ 2023-01-07 21:14:17