(80pts)

一个暴力搜索代码，然后用一个分数数组，每次搜索完成则统计尝试更新最大值。

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int g[N][N];
int row[N][N],col[N][N],cell[3][3][N]; 
int fen[9][9]={ //处理分数数组 
    {6,6,6,6,6,6,6,6,6},
    {6,7,7,7,7,7,7,7,6},
    {6,7,8,8,8,8,8,7,6},
    {6,7,8,9,9,9,8,7,6},
    {6,7,8,9,10,9,8,7,6},
    {6,7,8,9,9,9,8,7,6},
    {6,7,8,8,8,8,8,7,6},
    {6,7,7,7,7,7,7,7,6},
    {6,6,6,6,6,6,6,6,6},
};
//row[x][i]=true表示第x行填了数i,cell[i][j][x]表示第i行第j列的小格子填了数x
int res=-1; //初始化答案 
void dfs(int x,int y)
{
    if(y==9) x++,y=0; //行已经到了结尾
    if(x==9) //搜索完成
    {
    	int cnt=0; //当前这一轮的总分 
    	for(int i=0;i<9;i++)
		{
			for(int j=0;j<9;j++)
			{
				cnt=cnt+g[i][j]*fen[i][j];	
			}	
		} 
		res=max(res,cnt); //尝试更新最大分数 
        return ;
    }
    if(g[x][y]!=0) 
    {
    	dfs(x,y+1);
    	return ;
	}
    for(int i=0;i<9;i++) //枚举当前格子需要填写的数
    {
        if(!row[x][i]&&!col[y][i]&&!cell[x/3][y/3][i])
        {
            g[x][y]=i+1;
            row[x][i]=col[y][i]=cell[x/3][y/3][i]=1;
            dfs(x,y+1);
            row[x][i]=col[y][i]=cell[x/3][y/3][i]=0;
            g[x][y]=0;
        }
    }
}
int main()
{

    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
        	cin>>g[i][j];
            if(g[i][j]!=0) //对于已经有了的数进行标记
            {
                int t=g[i][j]-1;
                row[i][t]=col[j][t]=cell[i/3][j/3][t]=1;
            }
        }
    }
    dfs(0,0);
    cout<<res<<endl;
    return 0;
}

100pts

本质上还是搜索，只不过我们在搜索的时候并不是从第一个非0的地方开始搜索，而是尽量从可选择方案少的地方开始搜索，这样就会导致搜索的分支少了很多。

#include<bits/stdc++.h>
using namespace std;
const int N=9,M=1<<N;
int ones[M],h[M];
int row[N],col[N],cell[N/3][N/3];
int g[N][N];
int ans=-1;
int lowbit(int x)
{
	return x&-x; 
}
void init()
{
	for(int i=0;i<N;i++)
	{
		h[1<<i]=i; //h[x]=k 表现2^k=x 
	}
	for(int i=0;i<M;i++) //枚举每个数字 
	{
		for(int j=i;j;j-=lowbit(j)) //遍历i中1的个数 
		{
			ones[i]++;
		}
	}
	for(int i=0;i<N;i++)
	{
		row[i]=col[i]=cell[i/3][i%3]=M-1;//初始化是都是可以选择的 
	}
}
int get_score(int x,int y,int t) //得到当前位置填写t的时候的分数值 
{
	return (min(min(x,y),min(8-x,8-y))+6)*t;	
}
void draw(int x,int y,int t)
{
	int s=1;
	if(t>0) //增加 
	{
		g[x][y]=t;
	}
	else
	{
		s=-1;
		t=-t;
		g[x][y]=0;//清空 
	}
	t--;//位运算会减少一个
	s=s<<t;
	row[x]-=s;
	col[y]-=s;
	cell[x/3][y/3]-=s;
}
int get(int x,int y) //得到当前这个位置上可以填写的数 
{
	return row[x]&col[y]&cell[x/3][y/3];
}
void dfs(int cnt,int score) //搜索
{
	if(!cnt) //所有空的位置都填写完成了
	{
		ans=max(ans,score);
		return ;
	}
	int x,y,minv=10;
	for(int i=0;i<N;i++) //找到可以填写的个数最少的位置
	{
		for(int j=0;j<N;j++)
		{
			if(!g[i][j])
			{
				int t=ones[get(i,j)];
				if(t<minv)
				{
					minv=ones[get(i,j)];
					x=i,y=j;
				}
			}
		}
	}
	for(int i=get(x,y);i;i-=lowbit(i)) //枚举当前位置可以填写的每个数
	{
		int t=h[lowbit(i)]+1;
		draw(x,y,t); //填写
		dfs(cnt-1,score+get_score(x,y,t));
		draw(x,y,-t); //清空
	}
}
int main()
{
    init();
    int cnt=0,score=0;
    for(int i=0;i<N;i++) //根据输入去更新
    {
        for(int j=0;j<N;j++)
        {
            int x;
            cin>>x;
            if(x)
            {
                draw(i,j,x);
                score+=get_score(i,j,x);
            }
            else cnt++;
        }
    }
    dfs(cnt,score);
    cout<<ans;
    return 0;
}