[数据结构与算法]dfs数独问题

题目描述

数独游戏规则如下：在9 * 9的盘面上有些已知的数字及未知的数字，推理出所有未知的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。

有些局面存在多个解或无解，这属于不标准的数独。对于不标准的局面，输出No Solution。

?核心思路

? ? ? ? 与N皇后一样，这是一个dfs的题型，遍历并不难，关键在于剪枝操作

? ? ? ? 而在dfs的过程中采用回溯法进行进退转换，同时加入add和del操作进行进或退

基本思路

? ? ? ? 1.首先要明白如何剪枝找界限，其基本思路如下

1.对于第i行来讲，采用数组line[i][k]来表示当前行有几个k，如果有一个以上，则不能填k

2.对于第j列来讲，采用数组arr[j][k]来表示当前列有几个k，如果有一个以上，则不能填k

3.对于九宫格内的查重，方法值得借鉴和类比使用，采用数组judge[(i-1)/3][(j-1)/3][k]来记录九宫格内有几个k，如果有一个以上，则不能重复；其中(i-1)/3和(j-1)/3能够代表同一个九宫格，可以在草稿纸上表示，体会其奥妙之处

? ? ? ? 2.dfs的时候，依次检查每一个格子，如果该位置没有数字，利用（1）检查该位置是否可以填写数字

? ? ? ? 3.同时，填写后进行进一步深搜，如果无解则回溯，回溯时采用del操作

? ? ? ? 4.一些代码的写法详见注释?

?

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

inline int read(){
	int x=0;
	int f=1;
	char ch;
	ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch='-') f=-f;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

int map[10][10];
int mop[10][10];
int line[10][10];
int arr[10][10];
int judge[4][4][10];
bool flag=0;
int ans;

void add(int i,int j,int k){
	map[i][j]=k;
	judge[(i-1)/3][(j-1)/3][k]++;
	line[i][k]++;
	arr[j][k]++;
}

void del(int i,int j,int k){
	map[i][j]=0;
	judge[(i-1)/3][(j-1)/3][k]--;
	line[i][k]--;
	arr[j][k]--;
}

inline void dfs(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			if(map[i][j]==0){//图已填完会跳过if语句 
				for(int k=1;k<=9;k++){
					if(line[i][k]==0&&arr[j][k]==0&&judge[(i-1)/3][(j-1)/3][k]==0){
						add(i,j,k);
						dfs();
						if(ans>1) return;
						del(i,j,k);
					}
				}
				return ;//图未填满会继续填图 
			} 
		}
	}
	ans++;
	if(ans>1) return; 
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			mop[i][j]=map[i][j];
		}
	}
	return;
}

int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			map[i][j]=read();
			if(flag) continue;
			if(map[i][j]>0){
				judge[(i-1)/3][(j-1)/3][map[i][j]]++;
				line[i][map[i][j]]++;
				arr[j][map[i][j]]++;
				if(line[i][map[i][j]]>1||arr[j][map[i][j]]>1||judge[(i-1)/3][(j-1)/3][map[i][j]]>1){
					flag=true;
				}
			}
		}
	}
	if(flag){
		printf("No Solution");
		return 0;
	}
	dfs();
	if(ans==1){
		for(int i=1;i<=9;i++){
			for(int j=1;j<=9;j++){
				printf("%d ",mop[i][j]);
			}
			printf("\n");
		}
		return 0;
	}
	printf("No Solution");
	return 0;
} 

一些话

? ? ? ? ?CSP复赛很快要来了

? ? ? ? 深搜的时候一定要注重剪枝操作的规定！！！