https://www.luogu.org/problemnew/show/P1074
显然是dfs 而且没有什么剪枝记忆化之类的 但是预处理比较麻烦
我用三个二维数组存状态：visx[x][i]代表x行有没有选 i 这个数 visy[y][i]代表y列有没有选 i visg[g][i]代表第g个九宫格有没有选i
当遍历的时候 发现visx[x][i]==0&&visy[y][i]==0&&visg[g][i]==0 说明 i 还没有被选 就可以向下dfs
至于遍历的顺序 我们玩数独的时候都知道 肯定先从已知点比较多的地方开始考虑
比如 第一行：7 0 0 9 0 0 0 0 1 有6个位置未知
第九行：0 8 0 5 0 4 0 1 2 只有4个位置未知 那么我们肯定先考虑第九行
所以只需要把行sort排序一下 调整一下遍历的顺序即可
不过排序又引申出来一个问题 就是我们不知道排序之后的第一行 原来是第几行 为了解决这个问题 我们可以用一个结构体存储每一行有几个未知位置：
typedef struct
{
int nums=; //未知位置数量
int x; //行数
}node;
最后 我们需要维护一个一维数组，用来保存修正后的遍历的序列（当然二维也可以）
最后的的最后 每找到一组数独的解 都要更新最大值
具体看代码吧：
#include<bits/stdc++.h> using namespace std; typedef struct
{
int nums=;
int x;
}node;
node e[]; int m[][],anss,u,visx[][],visy[][],visg[][],q[],pre,flag;
int s[][]={,,,,,,,,,,, //保存每个位置上的分数 比较懒 直接打表了
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,,
,,,,,,,,,,}; bool cmp(node a,node b)
{
return a.nums<b.nums;
} void dfs(int t)
{
int i,j;
if(t==u+)
{
flag=;
int p=;
for(i=;i<=;i++)
for(j=;j<=;j++)
p+=m[i][j]*s[i][j];
anss=max(anss,p); //更新最大值
return;
}
int x=(q[t]-)/+;
int y=q[t]-(x-)*;
int g=((x-)/)*+(y-)/+;
for(i=;i<=;i++)
{
if(visx[x][i]==&&visy[y][i]==&&visg[g][i]==)
{
visx[x][i]=;
visy[y][i]=;
visg[g][i]=;
m[x][y]=i;
dfs(t+);
visx[x][i]=;
visy[y][i]=;
visg[g][i]=;
}
}
} int main()
{
int i,j;
for(i=;i<=;i++)
e[i].x=i;
for(i=;i<=;i++)
for(j=;j<=;j++)
{
scanf("%d",&m[i][j]);
if(m[i][j]==)
e[i].nums++;
else
{
pre+=m[i][j]*s[i][j];
visx[i][m[i][j]]=;
visy[j][m[i][j]]=;
int g=((i-)/)*+(j-)/+; //计算当前点属于哪一个九宫格
visg[g][m[i][j]]=;
}
}
sort(e+,e+,cmp);
for(i=;i<=;i++)
for(j=;j<=;j++)
{
if(m[e[i].x][j]==)
{
int nums=(e[i].x-)*+j; //如果当前位置未知，把他放入准备遍历的序列里
q[++u]=nums; //u记录了有多少点未知
}
}
dfs();
if(flag==) //如果无解
{
cout<<-<<endl;
return ;
}
cout<<anss<<endl; }