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=0; //未知位置数量 int x; //行数 }node;
最后 我们需要维护一个一维数组，用来保存修正后的遍历的序列（当然二维也可以）
最后的的最后 每找到一组数独的解 都要更新最大值
具体看代码吧：
#include<bits/stdc++.h> using namespace std; typedef struct { int nums=0; int x; }node; node e[15]; int m[15][15],anss,u,visx[15][15],visy[15][15],visg[15][15],q[100],pre,flag; int s[11][11]={0,0,0,0,0,0,0,0,0,0,0, //保存每个位置上的分数 比较懒 直接打表了 0,6,6,6,6,6,6,6,6,6,0, 0,6,7,7,7,7,7,7,7,6,0, 0,6,7,8,8,8,8,8,7,6,0, 0,6,7,8,9,9,9,8,7,6,0, 0,6,7,8,9,10,9,8,7,6,0, 0,6,7,8,9,9,9,8,7,6,0, 0,6,7,8,8,8,8,8,7,6,0, 0,6,7,7,7,7,7,7,7,6,0, 0,6,6,6,6,6,6,6,6,6,0, 0,0,0,0,0,0,0,0,0,0,0}; bool cmp(node a,node b) { return a.nums<b.nums; } void dfs(int t) { int i,j; if(t==u+1) { flag=1; int p=0; for(i=1;i<=9;i++) for(j=1;j<=9;j++) p+=m[i][j]*s[i][j]; anss=max(anss,p); //更新最大值 return; } int x=(q[t]-1)/9+1; int y=q[t]-(x-1)*9; int g=((x-1)/3)*3+(y-1)/3+1; for(i=1;i<=9;i++) { if(visx[x][i]==0&&visy[y][i]==0&&visg[g][i]==0) { visx[x][i]=1; visy[y][i]=1; visg[g][i]=1; m[x][y]=i; dfs(t+1); visx[x][i]=0; visy[y][i]=0; visg[g][i]=0; } } } int main() { int i,j; for(i=1;i<=9;i++) e[i].x=i; for(i=1;i<=9;i++) for(j=1;j<=9;j++) { scanf("%d",&m[i][j]); if(m[i][j]==0) e[i].nums++; else { pre+=m[i][j]*s[i][j]; visx[i][m[i][j]]=1; visy[j][m[i][j]]=1; int g=((i-1)/3)*3+(j-1)/3+1; //计算当前点属于哪一个九宫格 visg[g][m[i][j]]=1; } } sort(e+1,e+10,cmp); for(i=1;i<=9;i++) for(j=1;j<=9;j++) { if(m[e[i].x][j]==0) { int nums=(e[i].x-1)*9+j; //如果当前位置未知，把他放入准备遍历的序列里 q[++u]=nums; //u记录了有多少点未知 } } dfs(1); if(flag==0) //如果无解 { cout<<-1<<endl; return 0; } cout<<anss<<endl; }