本文主要是介绍爆搜创造性剪枝实验，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：靶形数独
各种小优化和位运算，待补充，程序并未完成，实际上优化是无止境的！
代码：
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
const int id[10][10]={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};const int sc[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 a[10][10],ans;
bool o=false;
unsigned int xx[10],yy[10],kui[10];
struct aa
{int x,i;bool operator <(const aa &b) const {return x<b.x;}
}t[10];
struct aaa
{int x,y;
}pos[102];
int num;int last[11][11];
void dfs(int t,int now)
{if (t==num+1) {o=true;ans=max(ans,now);return ;} int xc=pos[t].x,yc=pos[t].y;for (int i=1;i<=9;i++)if (!(xx[xc]&(1<<i))&&!(yy[yc]&(1<<i))&&!(kui[id[xc][yc]]&(1<<i))){xx[xc]^=(1<<i);yy[yc]^=(1<<i);kui[id[xc][yc]]^=(1<<i);dfs(t+1,sc[xc][yc]*i+now);xx[xc]^=(1<<i);yy[yc]^=(1<<i);kui[id[xc][yc]]^=(1<<i);}
}int main()
{for (int i=1;i<=9;i++)for (int j=1;j<=9;j++) scanf("%d",&a[i][j]); for (int i=1;i<=9;i++)for (int j=1;j<=9;j++)if (a[i][j]>0){int t=a[i][j];xx[i]|=(1<<t);yy[j]|=(1<<t);kui[id[i][j]]|=(1<<t);ans+=a[i][j]*sc[i][j];}for (int i=1;i<=9;i++){for (int j=1;j<=9;j++)if (a[i][j]==0) t[i].x++; t[i].i=i;}sort(t+1,t+9+1);for (int i=1;i<=9;i++)for (int j=1;j<=9;j++) if (a[t[i].i][j]==0)pos[++num].x=t[i].i,pos[num].y=j;dfs(1,ans);if (o) printf("%d",ans);else printf("-1");return 0;
}
这篇关于爆搜创造性剪枝实验的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
