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) {
		//结束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;
}

上一篇:Spring Boot Starter Parent介绍


下一篇:华为S5735交换机配置脚本