1.数独题目传送门:https://www.acwing.com/problem/content/168/
2.靶形数独题目传送门：https://www.acwing.com/problem/content/185/
题目1是一个普通的数独，并且测试数据保证有解，但是测试数据是多组，在搜索上不讲技巧的搜索是会TLE的，就连bitset去处理状态都会。
题目2是在一个普通的数独的基础上加了两点不同，第一不同是数据里有没有解的情况，第二不同是在九宫格上还有权值，要在所有方案中寻找最优值，即找到一种方案还不行，需要在填满后，按照规则每个格子需要乘上权值后求和，输出最大的和值。那么需要把所有方案都找出并维护最大值。，还好这题数据里只有一个需要解决的数独问题。
那么把题目1的数据求解后，再做第二题就显得比较容易了。
那么对于一个普通的数独问题，我们采用如何的策略去填数独呢？
1.找横、竖和小九宫格中空白处能填的“合法数字”个数最少的格子去填，我想你如果手动填数独也会是这个策略。如果有最少可以选择的数的空白格里可以填的数有多个，暴力枚举这几个数搜索回溯，而不是随意找个空白格去填。
2.如何快速确定每个位置上能填的合法数字呢，等到要找时，再去一遍扫行，一遍扫列，一遍扫九宫格寻找，显然速度就会慢了些。
在此我们可以运用位运算来进行统计。具体方法是：
- 对于每行、每列、每个九宫格的3个二进制数（全局整数变量）保存哪些数字可以填。
- 对于每个位置，把它所在行、所在列和所在小九宫格的3个二进制数进行位与运算，就可以看到哪些数字是可以填的。如，假设（1,1）这个位置的行上的状态是100111000，列上的状态是011011011,小九宫格上的状态是110111100,那么这个位上可以用的数有2个,分别是4,5.因为位与运算后从右往左数第4个位上和第5个位上是1，就表示这两个数没有出现过。程序实现时可以参考lowbit，取最低位的1采用(x & -x)的方式。
100111000
011011011
＆110111100
－－－－－－－－
000011000 - 当一个位置上尝试放入一个可以合法的数后，把该位置的行列和小九宫格的状态该位置上的数置为0，回溯时改回1即可还原现场。
题目1具体代码是：
//同样的思路用bitset去处理状态超时，用位运算就AC了，可见bitiset在处理二进制数做
//状态时在速度上稍显不足。
#include<bits/stdc++.h>
using namespace std;
int sd[10][10],cnt =0;
int row[9],col[9],rcsmall[9];
int num[513],onenum[513];
char c;
int rcno[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},};
struct pos{int x,y;
};
void print(){for(int i = 1;i<= 9 ;i++){for(int j =1; j<= 9; j++){printf("%d",sd[i][j]);}}printf("\n");
}
pos find(){int minn =10;pos temp;temp.x = -1,temp.y = -1;for(int i =1;i<= 9;i++){for(int j = 1;j<= 9; j++){if(sd[i][j]==0){int no = rcno[i][j];int vs = row[i] & col[j] & rcsmall[no]; if(minn >onenum[vs]){minn = onenum[vs];temp.x = i;temp.y = j;}}}}return temp;
}
bool dfs(int k){if(k == cnt+1){print();return true;}pos p = find(); //找空白位置上可以放置的数据选择性最小的哪个坐标点。 int no = rcno[p.x][p.y];int x = p.x,y = p.y;int vs = row[x] & col[y] & rcsmall[no];//vs存储的是二进制位上是1的对应数可选。 for( ; vs ; vs = vs - (vs & -vs)){//通过寻找最低位为1的位置，逐渐枚举每个可以放入的数。 int t =num[vs & -vs];row[x] ^= 1<< (t-1);col[y] ^= 1<< (t-1);rcsmall[no] ^= 1<< (t-1); sd[x][y] = t;if(dfs(k+1)) return true;sd[x][y] = 0;row[x] ^= 1<< (t-1);col[y] ^= 1<< (t-1);rcsmall[no] ^= 1<< (t-1); }return false;
}
void init(){for(int i = 0;i<10;i++){row[i] = (1<<9) - 1;col[i]= (1<<9) - 1;rcsmall[i]= (1<<9) - 1;}
}
void read(){c = getchar();if(c == 'e') return;sd[1][1] = c =='.' ? 0: c-48;for(int i = 2;i<= 81; i++){c = getchar();sd[(i-1)/9 +1][(i-1) % 9+1] = c =='.' ? 0: c-48;}c = getchar(); //?üê???DD?￡
}
void pre(){//预处理原始表中每行每列每个九宫格中数字的使用状态。 for(int i = 1;i<= 9 ;i++){for(int j =1; j<= 9; j++){int no = rcno[i][j];if(sd[i][j] != 0){row[i] ^= 1<< (sd[i][j]-1);col[j] ^= 1<< (sd[i][j]-1);rcsmall[no] ^= 1<< (sd[i][j]-1); }else{cnt ++;}} }
}
int main(){ //预处理每个数上对应的二进制数中有几个1，用于查找最少合法数据的位置时用。 for(int i =0; i< (1 << 9);i++)for(int j = i; j; j = j - (j & -j))onenum[i] ++;//预处理数的二进制数中只有一个1时，它代表的时哪个数。 for(int i = 1;i<= 9 ;i ++){num[1<< (i-1)] = i;}while(1){cnt = 0;init();read();if(c == 'e')break;pre(); dfs(1);}return 0;
}
题目二的题解相比题目1，需要做以下更改：
- 输入方式不一样。
- 增加一个权值数组。
- 对出现填满时由输出改为对数值的计算并维护。
- 出现填满的方案时，需要继续寻找下面的其他方案，因此去掉函数中的返回true,false之类的。
- 在出现方案时立个flag,带搜索完毕检查其flag的状态来确定是否有解。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
int sd[10][10],cnt =0;
int row[9],col[9],rcsmall[9];
int num[513],onenum[513];
int ans = 0;
char c;
bool flag = false;
int rcno[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},};
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},
};
struct pos{int x,y;
};
void getPerfect(){int sum = 0;for(int i = 1;i<= 9 ;i++){for(int j =1; j<= 9; j++){sum += sd[i][j]*score[i][j];}}ans = max(ans,sum);
}
pos find(){int minn =10;pos temp;temp.x = -1,temp.y = -1;for(int i =1;i<= 9;i++){for(int j = 1;j<= 9; j++){if(sd[i][j]==0){int no = rcno[i][j];int vs = row[i] & col[j] & rcsmall[no]; if(minn >onenum[vs]){minn = onenum[vs];temp.x = i;temp.y = j;}}}}return temp;
}
void dfs(int k){if(k == cnt+1){flag = true;getPerfect();return;}pos p = find(); //找空白位置上可以放置的数据选择性最小的哪个坐标点。 int no = rcno[p.x][p.y];int x = p.x,y = p.y;int vs = row[x] & col[y] & rcsmall[no];//vs存储的是二进制位上是1的对应数可选。 for( ; vs ; vs = vs - (vs & -vs)){//通过寻找最低位为1的位置，逐渐枚举每个可以放入的数。 int t =num[vs & -vs];row[x] ^= 1<< (t-1);col[y] ^= 1<< (t-1);rcsmall[no] ^= 1<< (t-1); sd[x][y] = t;dfs(k+1);sd[x][y] = 0;row[x] ^= 1<< (t-1);col[y] ^= 1<< (t-1);rcsmall[no] ^= 1<< (t-1); }
}
void init(){for(int i = 0;i<10;i++){row[i] = (1<<9) - 1;col[i]= (1<<9) - 1;rcsmall[i]= (1<<9) - 1;}
}
void read(){for(int i = 1;i<= 9;i++){for(int j = 1;j<= 9 ;j++){scanf("%d",&sd[i][j]);}}
}
void pre(){for(int i = 1;i<= 9 ;i++){for(int j =1; j<= 9; j++){int no = rcno[i][j];if(sd[i][j] != 0){row[i] ^= 1<< (sd[i][j]-1);col[j] ^= 1<< (sd[i][j]-1);rcsmall[no] ^= 1<< (sd[i][j]-1); }else{cnt ++;}} }
}
int main(){ for(int i =0; i< (1 << 9);i++)for(int j = i; j; j = j - (j & -j))onenum[i] ++;for(int i = 1;i<= 9 ;i ++){num[1<< (i-1)] = i;} cnt = 0;init();read();pre(); dfs(1);if(flag)cout << ans;else cout << "-1";return 0;
}
好吧，终于还是咬咬牙把前几天一口气用bitset+搜索的方式写完且TLE程序给改AC了，也终于很快完成了靶形数独，在几年前不敢写的程序现在看来也不过如此，确实成长了，但是速度嘛不言而喻，就像我跑马拉松，人家早就在4小时内到达了终点，我设定的目标是6小时内完赛，享受沿途风景，感受途中心情变化，没人催，就靠点自律，自己感动自己，跑起来自然那就叫一个慢！
总结
以上是生活随笔为你收集整理的ACwing166数独与183靶形数独的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
