dfs +剪枝sudoku———poj2676
目录
前言
lowbit函数
这是一个利用二进制位运算取出二进制数最后一位’1‘的函数
数独
数独大家肯定都玩过，本题就是利用计算机尝试模拟人做数独游戏时的情形，每次从空白最少的行开始填写，每次填写都比对这个数字是否符合要求，如果没有符合要求的数字，则重新填写上一个数字，大家可以回忆下做数独时的情形，也可以为剪枝提供思路
suduku
问题描述
给定一个9*9的网格，又将该网格细分为九个3*3的子网格，现给出部分数字，编写程序填满该网格，要求每行，每列，每个子网格，只能出现1~9中的数字，且每行，每列，每个子网格中不能有重复的数字，若有多个答案，只输出其中一个即可。
输入
有多个测试用例，第一行输入一个整数t，代表测试个数，对于每个测试，输入一个9*9的字符串数组
输出
输出一种符合条件的答案
问题分析
子网格位置
首先要解决子网格位置问题，给定一个点（x，y）的坐标给如何知道该点位于哪个子网格中，我们先对各个子网格编号
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
然后我们再找规律：
最笨但是最实用的方法就是用9个if语句判断一下确定位置，别瞧不起它，这个是真的有用
不开玩笑了，哈哈，其实这个是有公式的：
解决了这个问题，我们在考虑剪枝
优化搜索顺序剪枝1
会玩数独的伙伴肯定清楚，填数字要从数字最多的一行开始填，也就是空白最少的一行，因为这样很可能提前确定一些数字，计算机也是这样，网格中的数字越多，dfs需要递归的次数就越少，所以每次我们都选择0（也就是空白）最少的一行开始填写
优化搜索顺序剪枝2
很简单的道理，如果1~9中有数字前面已经搜索过了，那么就没有必要再搜了，直接剪掉，这里多说两句，实现这个方法的办法有两种，一种是用一个9位二进制代表1~9，然后用lowbit（）函数逐一取出二进制数中的最后一个1，这样可以实现上述剪枝，更简单的就是用循环实现，但是需要加一点小改动，详见代码
可行性剪枝
这个就是根据题意来的，每行，每列，每个子网格中不能存在相同的数字
代码
#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool flag=false;
int map[15][15]; //九宫格
struct node{
int row; //行的编号
int num; //该行中0的数量
}cnt[15];
bool row[15][15]; //row[i][x] 标记在第i行中数字x是否出现
bool col[15][15]; //col[j][y] 标记在第j列中数字y是否出现
bool grid[15][15]; //grid[k][x] 标记在第k个3*3子格中数字x是否出现
bool cmp(node a, node b) {
return a.num < b.num; //升序排列
}
int query(int x, int y) {
if (y <= 3 && x <= 3) return 1;
if (y > 3 && y <= 6 && x <= 3) return 2;
if (y > 6 && x <= 3) return 3;
if (y <= 3 && x > 3 && x <= 6) return 4;
if (y > 3 && y <= 6 && x > 3 && x <= 6) return 5;
if (y > 6 && x > 3 && x <= 6) return 6;
if (y <= 3 && x > 6) return 7;
if (y > 3 && y <= 6 && x > 6) return 8;
if (y > 6 && x > 6) return 9;
}
void DFS(int x, int y,int pos,int p){
if (flag) {
//结束dfs
return;
}
if (p == 10) {
//打印结果，在dfs内打印优势是可以借助dfs本身的回溯将row，col，grid初始化
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
cout << map[i][j];
}
cout << endl;
}
flag = true;
return;
}
//剪枝，如果map中该位置已经有数字那么直接下一个，或者下一层
if (map[x][y]){
if (y == 9) DFS(cnt[p+1].row, 1,1,p+1); //这里用了一个辅助p，帮助计数
else DFS(x, y + 1,pos,p);
return;
}
//int k = query(x, y); //最直接方法
int k = 3 * ((x - 1) / 3) + (y - 1) / 3 + 1; //公式法
//#define lowbit(x) ((x)&-(x))
for (int i = pos; i <= 9; i++) { //其实这里可以用一个九位二进制数代表1~9这几个数字是否可选，用lowbit（）函数取出第一个1（这个是树状数组中的函数），这样就可以实现减少重复次数，但我觉得使用pos变量也可以实现同样的效果
if (!row[x][i] && !col[y][i] && !grid[k][i]) { //利用这仨进行可行性剪枝
/*同样的，这里的row，col，grid数组都可以是用九个九位二进制数来代替，但这样编码起来太麻烦了，我写不出来，所以干脆用数组，感兴趣的伙伴可以试一下，写出来了@我一下，第一时间给你点赞*/
map[x][y] = i;
row[x][i] = true;
col[y][i] = true;
grid[k][i] = true;
//优化搜索顺序剪枝，每次填写0最少的一行
if (y == 9) DFS(cnt[p+1].row, 1, 1, p + 1);
else DFS(x, y + 1,pos,p); //最优化剪枝，如果前面已经搜过，就代表一定标记过了，就不需要继续了，下一次循环从pos开始
//回溯
map[x][y] = 0;
row[x][i] = false;
col[y][i] = false;
grid[k][i] = false;
}
}
return ;
}
int main(){
int t;
cin >> t;
while (t--){
//注意有多个测试用例每次都要将这仨初始化，使用memset的时候要加cstring头文件，但如果在dfs内部输出结果则不需要手动初始化
/*memset(row, false, sizeof(row));
memset(col, false, sizeof(col));
memset(grid, false, sizeof(grid));*/
//注意题目说的是输入的是字符串，一开始没注意被坑惨了
char Map[10][10];
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++){
cin >> Map[i][j];
map[i][j] = Map[i][j] - '0'; //-'0'字符串变数字，+'0'数字变字符串，欸，不查资料还真记不住
//初始化
if (map[i][j]){
//int k = query(i, j);
//这个公式很好推的，加油
int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
row[i][map[i][j]] = true;
col[j][map[i][j]] = true;
grid[k][map[i][j]] = true;
}
else {
//对每行的索引用0的多少进行排列，首先要知道每行0的数量
cnt[i].num++;
cnt[i].row = i;
}
}
}
//每次填写0少的一行，我们玩数独也是这样玩的吧
sort(cnt + 1, cnt + 9 + 1, cmp);
//这是打印搜索行顺序代码
/*for (int k = 1; k <= 9; k++) {
cout << cnt[k].row<<" ";
}
cout<<endl;*/
//开始dfs
DFS(cnt[1].row, 1,1,1);
//记得将flag重置
flag = false;
}
return 0;
}原文地址：https://blog.csdn.net/2301_80093604/article/details/142743118
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！