数独问题 解数独

数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。 现要求用计算机求解数独。

输入描述:

输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的数字。

输出描述:

输出九行，每行九个空格隔开的数字，为解出的答案。

示例1

输入
0 9 0 0 0 0 0 6 0
8 0 1 0 0 0 5 0 9
0 5 0 3 0 4 0 7 0
0 0 8 0 7 0 9 0 0
0 0 0 9 0 8 0 0 0
0 0 6 0 2 0 7 0 0
0 8 0 7 0 5 0 4 0
2 0 5 0 0 0 8 0 7
0 6 0 0 0 0 0 9 0
输出
7 9 3 8 5 1 4 6 2
8 4 1 2 6 7 5 3 9
6 5 2 3 9 4 1 7 8
3 2 8 4 7 6 9 5 1
5 7 4 9 1 8 6 2 3
9 1 6 5 2 3 7 8 4
1 8 9 7 3 5 2 4 6
2 3 5 6 4 9 8 1 7
4 6 7 1 8 2 3 9 5

解法一：利用DFS进行状态搜索（搜到一种就输出）

#include<bits/stdc++.h>
using namespace std;

int a[9][9];
int sum=0;
bool sign=false;

//只能输出第一次搜索出的正确结果
bool check(int key,int n){
	//检查行
	int j=n/9; 
	for(int i=0;i<9;i++)
	    if(a[j][i]==key) 
	        return false;
	//检查列 
	j=n%9;
	for(int i=0;i<9;i++) {
		if(a[i][j]==key)
		    return false;
	}
	//检查九个小方块
	int x=n/9;//n的行坐标
	int y=n%9;//n的列坐标
	//***最重要的技巧*** 
	x=x/3*3;
	y=y/3*3; //x和y是n所在的小方块最左上角的坐标 
	for(int i=x;i<x+3;i++)
	    for(int j=y;j<y+3;j++)
		    if(a[i][j]==key)
			    return false; 	 
	return true;
}
int DFS(int n){//把棋盘标号，n是二维棋盘的一维序号 
	if(n>80){//此时说明找到了 
		sign=true;//信号量 说明找到了 
		return 0;
	}
	if(a[n/9][n%9]!=0){
		DFS(n+1);
	}
	else{
		for(int i=1;i<=9;i++){
			if(check(i,n)){
			    a[n/9][n%9]=i;
				if(n<=80) DFS(n+1);
				//这个if用于在找到一种解法之后的回溯过程中防止棋盘复原 
			/*	if(sign){
					return 0;	
				}	*/
				//只有没找到的情况才回溯，如果不加下面的if语句，在递归回退的过程中填好的空又变回去了 
				if(sign==false) a[n/9][n%9]=0;//回溯 
			}
		}	
	}	 
	return 0;
} 

int main()
{
	for(int i=0;i<9;i++)
	    for(int j=0;j<9;j++) 
	        cin>>a[i][j];
 
	DFS(0); 
	//不一定必有解，先按必有解的情况输出 
	cout<<"******************"<<endl;
    for(int i=0;i<9;i++){
	    for(int j=0;j<9;j++)
	    	cout<<a[i][j]<<' '; 
        cout<<endl;	
    }
	return 0;
 } 

解法二：利用DFS搜索所有结果

#include<bits/stdc++.h>
using namespace std;

int a[9][9];
int sum=0;
int s=0;
int t=0;

//输出所有正确结果或无结果的情况 
bool check(int key,int n){
	//行
	int j=n/9; 
	for(int i=0;i<9;i++)
	    if(a[j][i]==key) 
	        return false;
	//列 
	j=n%9;
	for(int i=0;i<9;i++) {
		if(a[i][j]==key)
		    return false;
	}
	//九个小方块
	int x=n/9;//n的行坐标
	int y=n%9;//n的列坐标
	//最重要的技巧 
	x=x/3*3;//n所在的小方块最左上角的坐标 
	y=y/3*3; 
	for(int i=x;i<x+3;i++)
	    for(int j=y;j<y+3;j++)
		    if(a[i][j]==key)
			    return false; 	 
			    
	return true;
}
void shuchu(){
	t++; 
	cout<<"******************"<<endl;
    for(int i=0;i<9;i++){
	    for(int j=0;j<9;j++)
	    	cout<<a[i][j]<<' '; 
        cout<<endl;	
    }
}
int DFS(int n){
	s++;
	if(n>80){
		sum++;
		shuchu();
	    cout<<sum<<endl; 
		return 0;
	}
	if(a[n/9][n%9]!=0){
		DFS(n+1);
	}
	else{
		for(int i=1;i<=9;i++){
			if(check(i,n)){
			    a[n/9][n%9]=i;
				DFS(n+1);
				//shuchu();
				a[n/9][n%9]=0;//回溯 
			}
		}	
	}	 
	 return 0;
} 


int main()
{
//	freopen("sample.out","w",stdout);
	
	for(int i=0;i<9;i++)
	    for(int j=0;j<9;j++) 
	        cin>>a[i][j];
 
	DFS(0); 
	
	//不一定必有解，先按必有解的情况输出 
	cout<<"答案数："; 
	cout<<sum<<endl;
	cout<<"进入DFS次数："; 
	cout<<s<<endl;	
	cout<<"输出次数：";
	cout<<t<<endl;	
	
//	fclose(stdout);
	
	return 0;
 } 

解法三：利用解法二找出所有数独存在的结果，然后在结果中搜索符合给出的数独空缺条件的。
在解法二中输入

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

会搜索出 M种结果并保存起来，写个程序在这些结果中搜索即可。在搜索时应该注意优化。
这个M看起来有点大啊，已经跑到200w了还没结束。

一个技巧：
假设搜索库有M个数独结果，待填数独有N个数已知，即有N个条件（数独中的非0数即为条件），那么有复杂度为O(M+N)和O(MN)的两种算法。
O(M+N)的方法：
依次拿着N个条件在M个结果的结果库中搜索，因为搜索出来的结果在一定顺序上是从小到大的，因此可以在第a个条件在结果库中找到后，继续用第a+1个条件在后面的结果库中搜索。若所有条件都用光了，那么从最后一个条件搜索到的第一个结果到结果库的最后一个结果都是符合条件的数独。
O（MN）的方法：
遍历结果库然后在遍历过程中匹配所有的条件，若符合所有的条件就输出。

这个搜索的方法好像不大行啊！！！