dfs +剪枝sudoku———poj2676

目录

前言

   lowbit函数

   数独         

suduku

   问题描述    

   输入

   输出

问题分析

   子网格位置

   优化搜索顺序剪枝1

   优化搜索顺序剪枝2

   可行性剪枝

代码

---

前言

   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) {//结束dfsreturn;}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;*///开始dfsDFS(cnt[1].row, 1,1,1);//记得将flag重置flag = false;}return 0;
}