AC代码

(别抄了AC代码就走了，下面还有分析)

#include<bits/stdc++.h>
using namespace std;
int xu[20], G[10][10],sum[20],before=0,ans=-1;
bool g[10][10],hang[10][10],lie[10][10];
struct cmp{
	bool operator ()(const int &a,const int &b){
		return sum[a]<sum[b];
	} 
};
int wg(int x,int y){
	if (x<=3){if (y<=3) return 1;if(y<=6) return 2;else return 3;}
	if (x<=6){if (y<=3) return 4;if(y<=6) return 5;else return 6;}
	if (y<=3) return 7;if (y<=6) return 8;else return 9;
}
int fen(int i,int j){
	if (i==1 or i==9 or j==1 or j==9) return 6;
	if (i==2 or i==8 or j==2 or j==8) return 7;
	if (i==3 or i==7 or j==3 or j==7) return 8;
	if (i==4 or i==6 or j==4 or j==6) return 9;
	return 10;
}
void dfs(int x,int y,int score,int sx){
	if (y==10){
		if (sx==9){ans=max(ans,score);return;}
		dfs(xu[sx+1],1,score,sx+1);
		return;
	}
	if (G[x][y]) dfs(x,y****core,sx);
	for (int i=1;i<=9;i++){
		if (!hang[x][i] and !lie[y][i] and !g[wg(x,y)][i]){
			hang[x][i]=lie[y][i]=g[wg(x,y)][i]=1;
			dfs(x,y****core+i*fen(x,y),sx);
			hang[x][i]=lie[y][i]=g[wg(x,y)][i]=0;
		}
	}
	return;
}
int main(){
	for (int i=1;i<=9;i++){
		int tmp=0;
		for (int j=1;j<=9;j++)
			{	cin>>G[i][j];
				if (!G[i][j])tmp++;
				else{
					before+=G[i][j]*fen(i,j);
					hang[i][G[i][j]]=1;lie[j][G[i][j]]=1;
					g[wg(i,j)][G[i][j]]=1;
				}
			}
		xu[i]=i;sum[i]=tmp;
	}
	sort(xu+1,xu+1+9,cmp());
	dfs(xu[1],1,before,1);
	cout<<ans;
	return 0;
}

分析

1思路
很简单，各个格子都搜一遍，看看可以填哪个数即可，很像八皇后，但除去每行每列的数不同外，每一个九宫格中的数也不能相同，所以我们应该开三个bool数组，判断哪个数还可以填。但是没剪枝，效率往往低的让人无法忍受，所以我们可以优先填写空格子数较少的行或列。这样可以让没有数字的位置越来越少，从而减少搜索空间。

2数组与函数
此题数组很多，只能分开讲了
bool数组：

bool g[10][10],hang[10][10],lie[10][10];

如1所述，g[i][j]判断在第i个九宫格中数字j是否出现过，hang[i][j]判断在第i个行中数字j是否出现过,lie[i][j]则表示判断在第i个列中数字j是否出现过
还有个问题，怎么判断矩阵中的数（如第x行第y列的数）属于第几个九宫格呢？

int wg(int x,int y){
	if (x<=3){if (y<=3) return 1;if(y<=6) return 2;else return 3;}
	if (x<=6){if (y<=3) return 4;if(y<=6) return 5;else return 6;}
	if (y<=3) return 7;if (y<=6) return 8;else return 9;
}

wg()的功能便是将1个$9*9$的矩阵分成9个3 ∗ 3 3*33∗3的九宫格，并能返回如第x行第y列的数所属九宫格
int数组：

int xu[20], G[10][10],sum[20];

如1所述，我们应按照空格子的个数从小到大排序，按此顺序排序即可，xu便是搜索顺序，sum是此行0出现的次数具体来说：
sum数组记录每个空格子可以填入数字的数量和。是间接排序的重要辅助数组。

struct cmp{
	bool operator ()(const int &a,const int &b){
		return sum[a]<sum[b];
	} 
};
sort(xu+1,xu+1+9,cmp());

很显然，我们对xu数组排序，却看的是sum数组中数字的大小，这便是间接排序。

xu数组存储数独的行号，用于按照空格子的个数从小到大排序。在优先填写空格子数较少的行的剪枝策略中，我们可以按照xu数组的顺序依次填写每行，并对每行的空格子数从小到大排序，这样可以让没有数字的位置越来越少，从而减少搜索空间。

举个例子，xu数组初始值为{1, 2, 3, 4, 5, 6, 7, 8, 9}，则搜索时第一次从第1行开始，第二次从第2行开始，以此类推。在搜索某行的空格子时，我们可以按照该行空格子数从小到大排序，生成新的xu数组，这样可以让搜索更加高效。

综上所述，sum和xu数组均是为了优化搜索算法而引入的辅助数组。

3.DFS(深度优先搜索)

void dfs(int x,int y,int score,int sx){
	if (y==10){
		if (sx==9){ans=max(ans,score);return;}
		dfs(xu[sx+1],1,score,sx+1);
		return;
	}
	if (G[x][y]) dfs(x,y****core,sx);
	for (int i=1;i<=9;i++){
		if (!hang[x][i] and !lie[y][i] and !g[wg(x,y)][i]){
			hang[x][i]=lie[y][i]=g[wg(x,y)][i]=1;
			dfs(x,y****core+i*fen(x,y),sx);
			hang[x][i]=lie[y][i]=g[wg(x,y)][i]=0;
		}
	}
	return;
}

参数：

在dfs函数中，4个参数分别是：

• x：当前要填的空格子的行数；
• y：当前要填的空格子的列数；
• score：当前方案的总分数，包括已经填好的格子权值之和以及当前正在填的格子的权值；
• sx：记录目前x在xu数组中的下标。

其中，x、y用来确定当前要填的空格子的位置，因为搜索是从左到右、从上到下的，所以需要记录行、列号。score则是当前方案的总分数，需要在搜索时不断更新。最终的答案就是所有可行方案中最大的总分数。
sx参数则是辅助作用，因为在dfs函数中，我们按照每行空格子的数量从小到大依次进行搜索，所以需要记录当前搜索的是哪一行的空格子，以便于下一步搜索，即剪枝。
边界：
当搜索到当前行的最后一列，即y==10时，需要判断是否已经填完了整个数独，即sx == 9。如果是，说明已经填完了整个数独，此时需要将当前方案的总分数与之前找到的最大分数进行比较，更新最大分数，然后结束本次搜索。
如果还没有填完整个数独，就需要继续搜索下一行，并从该行的第一列开始搜索。

回溯：
由于使用了bool数组作为标记，所以在向下搜索后取消标记

$$\bold E\bold N\bold D$$

---

我相信读者能够读懂main函数，我不过多赘述，另外这是一道相对来说比较困难的搜索题目，通过后可以加深对搜索和剪枝算法理解。也比较难优化。

附：

#include<bits/stdc++.h>
#include<vector>
using namespace std;
const int M=1e6,MN=1e7;int last_ans=-1;
int fen(int i,int j){
	i++,j++;
	if (i==1 or i==9 or j==1 or j==9) return 6;
	if (i==2 or i==8 or j==2 or j==8) return 7;
	if (i==3 or i==7 or j==3 or j==7) return 8;
	if (i==4 or i==6 or j==4 or j==6) return 9;
	return 10;
}
inline int encode(int a,int b,int c){
	return a*81+b*9+c+1;
}
inline void decode(int code,int &a,int &b,int &c){
	code--;c=code%9;code/=9;
	b=code%9;code/=9;
	a=code;return;
}
struct DLX{
	int n,sz;
	int S[M];int row[MN],col[MN];
	int L[MN],R[MN],U[MN],D[MN];
	int ansd,ans[M];
	
	void init(int n){
		this->n=n;
		for (int i=0;i<=n;i++)
			{U[i]=D[i]=i;L[i]=i-1;R[i]=i+1;}
		sz=n+1;R[n]=0;L[0]=n;memset(S,0,sizeof(S));
	}
	void addROW(int r,vector<int> cols){
		int first=sz;
		for (int i=0;i<cols.size();i++){
			int c=cols[i];
			L[sz]=sz-1;R[sz]=sz+1;
			U[sz]=U[c];D[sz]=c;
			D[U[c]]=sz;U[c]=sz;
			row[sz]=r;col[sz]=c;
			S[c]++;sz++;
		}
		R[sz-1]=first;L[first]=sz-1;
	}
	#define FOR(i,A,s) for (int i=A[s];i!=s;i=A[i])
	void remove(int c){
		L[R[c]]=L[c];R[L[c]]=R[c];
		FOR(i,D,c)
			FOR(j,R,i) {U[D[j]]=U[j];D[U[j]]=D[j];S[col[j]]--;}
	}
	void restore(int c){
		FOR(i,U,c)
			FOR(j,L,i) {S[col[j]]++;U[D[j]]=j;D[U[j]]=j;}
		L[R[c]]=c;R[L[c]]=c;
	}
	bool dfs(int d){
		if (R[0]==0){last_ans=max(d,last_ans);return true;}
		int c=R[0];bool flag=false;
		FOR(i,R,0) if(S[i]<S[c]) c=i;
		remove(c);
		FOR(i,D,c){
			FOR(j,R,i) remove(col[j]);
			int rr,cc,vv;
			decode(row[i],rr,cc,vv);
			if(dfs(d+fen(rr,cc)*(vv+1))) flag = true;
			FOR(j,L,i) restore(col[j]);
		}
		restore(c);return flag;
	}
	bool solve(vector<int> &v){
		v.clear();
		if (!dfs(0)) return false;
		for (int i=0;i<ansd;i++) v.push_back(ans[i]);
		return true;
	}
}solve;

vector<int> tmp;
int mp[9][9];
int main(){
	for (int i=0;i<=8;i++)
		for (int j=0;j<=8;j++) cin>>mp[i][j];
	solve.init(9*9*4);
	for (int r=0;r<=8;r++)
		for (int c=0;c<=8;c++)
			for (int v=0;v<=8;v++){
				if (mp[r][c]==0 or mp[r][c]==v+1){
					vector<int> cols;
					cols.push_back(encode(0,r,c));
					cols.push_back(encode(1,r,v));
					cols.push_back(encode(2,c,v));
					cols.push_back(encode(3,(r/3)*3+c/3,v));
					solve.addROW(encode(r,c,v),cols);
				}
			}
	solve.dfs(0);
	cout<<last_ans;
	return 0;
}

清晰易懂，效率极(鸡)高