题解：P1074 [NOIP2009 提高组] 靶形数独

· · 题解

题目传送门

思路

本题要求出数独的所有解法，在所有解中找最大值，所以搜索量巨大。显然的优化思路是优先选择限制条件多的位置填写。比如某行已经填了 7 个数，那么还剩 2 个格子，只有 2 种情况。可以把搜索过程想象成一棵树，根节点是起点，这样做可以使刚开始的分叉少，之后的分叉多，一旦发生剪枝，减去的节点就更多，剪枝的效果就更加显著。这个剪枝原则适用于所有数独问题，虽然看起来代码里浪费了时间去找已填数最多的行和列，但实际上浪费的时间相比剪枝节省的时间，微不足道。

代码

#include<bits/stdc++.h>
using namespace std;
const int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
int row[10][10],col[10][10],grid[10][10],a[10][10];
int row_cnt[10],col_cnt[10],cnt,ans=-1;
int tran(int x,int y){
    return (x-1)/3*3+(y-1)/3+1;
}
int calc(){
    int tmp=0;
    for(int i=1;i<=9;i++)
        for(int j=1;j<=9;j++)
            tmp+=score[i][j]*a[i][j];
    return tmp;
}
void dfs(int x,int y,int tot){
    if(tot==81){
        ans=max(ans,calc());
        return;
    }
    for(int i=1;i<=9;i++){
        if(row[x][i]||col[y][i]||grid[tran(x,y)][i])continue;
        row[x][i]=col[y][i]=grid[tran(x,y)][i]=true;
        row_cnt[x]++,col_cnt[y]++;
        a[x][y]=i;
        int tmpr=-1,nxt_x=0,tmpc=-1,nxt_y=0;
        for(int j=1;j<=9;j++)
            if(row_cnt[j]>tmpr&&row_cnt[j]<9)
                tmpr=row_cnt[j],nxt_x=j;
        for(int j=1;j<=9;j++)
            if(col_cnt[j]>tmpc&&!(a[nxt_x][j]))
                tmpc=col_cnt[j],nxt_y=j;
        dfs(nxt_x,nxt_y,tot+1);
        row[x][i]=col[y][i]=grid[tran(x,y)][i]=false;
        row_cnt[x]--,col_cnt[y]--;
        a[x][y]=0;
    }
}
int main(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cin>>a[i][j];
            if(a[i][j]!=0){
                row[i][a[i][j]]=true;
                col[j][a[i][j]]=true;
                grid[tran(i,j)][a[i][j]]=true;
                row_cnt[i]++,col_cnt[j]++;
                cnt++;//已经填了的数量
            }
        }
    }
    int tmpr=-1,x,tmpc=-1,y;
    for(int j=1;j<=9;j++)
        if(row_cnt[j]>tmpr&&row_cnt[j]<9)
            tmpr=row_cnt[j],x=j;//选已填数最多的行x出发
    for(int j=1;j<=9;j++)
        if(col_cnt[j]>tmpc&&(!a[x][j]))
            tmpc=col_cnt[j],y=j;//选行x里填数最多的列y出发
    dfs(x,y,cnt);
    cout<<ans;
    return 0;
}