靶形数独,一道搜索能做出来的题，数独相信大家都会，靶形数独就是给它加个权，然后搞一个和A*差不多的东西? 有几个剪枝：第一是如果现在的val加上剩余的格子弄最大的数，占最大的权都不如现在的ans，就属于根本扶不起来的，就return；还有就是在所有格子中找一个格子，让它可以填的情况最少，那么如果是这样需要枚举的次数就会减少。然后就水过了。。
//Writer : Hsz %WJMZBMR %tourist %hzwer #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #include<map> #include<set> #include<stack> #include<vector> #include<cstdlib> #include<algorithm> #define LL long long using namespace std; int g[10][10],ans,tot=81; bool hang[10][10],lie[10][10],kuai[10][10]; bool flag; int v[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 ju[10][10]= {//打表*2 0,0,0,0,0,0,0,0,0,0, 0,1,1,1,2,2,2,3,3,3, 0,1,1,1,2,2,2,3,3,3, 0,1,1,1,2,2,2,3,3,3, 0,4,4,4,5,5,5,6,6,6, 0,4,4,4,5,5,5,6,6,6, 0,4,4,4,5,5,5,6,6,6, 0,7,7,7,8,8,8,9,9,9, 0,7,7,7,8,8,8,9,9,9, 0,7,7,7,8,8,8,9,9,9, }; void dfs(int rest,int val) { if(rest==0) { ans=max(ans,val); // cout<<ans; flag=1;//判没有解的情况 return; } if(rest*9*10+val<=ans) return; int way=0,mn=10,tx=0,ty=0,bc; for(int i=1; i<=9; i++) for(int j=1; j<=9; j++) { if(!g[i][j]) { way=9; bc=ju[i][j]; for(int k=1; k<=9; k++) { if(hang[i][k]||lie[j][k]||kuai[bc][k]) way--;//找那个最少可能的点。 } if(mn>way) mn=way,tx=i,ty=j; } } int tc=ju[tx][ty]; int i=tx,j=ty; for(int w=1; w<=9; w++) if(!hang[i][w]&&!lie[j][w]&&!kuai[ju[i][j]][w]&&!g[i][j]) { hang[i][w]=1; lie[j][w]=1; kuai[ju[i][j]][w]=1; g[i][j]=w; dfs(rest-1,val+w*v[i][j]); hang[i][w]=lie[j][w]=kuai[ju[i][j]][w]=g[i][j]=0; } } int main() { for(int i=1; i<=9; i++) for(int j=1; j<=9; j++) { cin>>g[i][j]; if(g[i][j]) hang[i][g[i][j]]=1, lie[j][g[i][j]]=1, kuai[ju[i][j]][g[i][j]]=1, --tot, ans+=g[i][j]*v[i][j]; } dfs(tot,ans); if(flag)cout<<ans;else cout<<"-1"; return 0; }