Sudoku (POJ2676)

Posted on | In |

题意

将数字1到9,填入9x9矩阵中的小方格，使得矩阵中
的每行，每列，每个3x3的小格子内，9个数字都会
出现。

解题思路

几乎纯暴力搜索

将空白格子的位置放入一个数组，然后用Dfs尝试每个空白格子所放的数字。
会超时

剪枝：

放入一个数字后，就要做个标记，表面在当前行，当前列，以及当前小块已经放过这
个数字了，那么以后就不会在同行，同列或同小块放同样数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAX 100
using namespace std;
//每行每列每小块不重复 
//行数 num->标记数组  
int rowFlag[100][100];
int columnFlag[100][100];
int blockFlag[100][100];
int board[100][100];//!!
struct pos{
	int x,y;
	pos(int xx,int yy):x(xx),y(yy){
		
	}
};
vector<pos> blankpos;
int getBlockNum(int r,int c){
//	return r/3*3+c/3;
int rr = r /3;
int cc = c /3;
return rr * 3 + cc;
}
void setFlags(int r,int c,int num,int f){
//	int k=getBlockNum(r,c);
//	//rowFlag[r][c]=f; 錯了 应该是r这行放Num数字 判断flag
//	rowFlag[r][num]=f;
//	columnFlag[c][num]=f;
//	blockFlag[k][num]=f; 
rowFlag[r][num] = f;
columnFlag[c][num] = f;
blockFlag[getBlockNum(r,c)][num] = f;
}
bool IsOK(int i,int j,int num)
{//  看num在 能否放在 i,j 位置
return !rowFlag[i][num]&&!columnFlag[j][num]&&!blockFlag[getBlockNum(i,j)][num];
}
bool dfs(int n)
{// 处理前n 个空格
if( n < 0)
return true;
int r = blankpos[n].x;
int c = blankpos[n].y;
for( int num = 1; num <= 9; ++ num ) {
if( IsOK(r,c,num)) {
board[r][c] = num;
setFlags(r,c,num,1);
if( dfs(n-1))
return true;
setFlags(r,c,num,0);
}
}
return false;
}

int main(){
		int n;
		//freopen("11-16.txt","r",stdin);
		int t;
		cin>>t;
		while(t--){
		memset(rowFlag,0,sizeof(rowFlag));
		memset(columnFlag,0,sizeof(columnFlag));		
		memset(blockFlag,0,sizeof(blockFlag));	
		blankpos.clear();
		for(int i=0;i<9;i++){
			for(int j=0;j<9;j++){
				char c;
				cin>>c;
				board[i][j]=c-'0';
				if(board[i][j]) setFlags(i,j,board[i][j],1);
				else 
					blankpos.push_back(pos(i,j));
				
			}
		} 


		if(dfs(blankpos.size()-1)) {//!! dfs(blankpos.size())-1 括号问题 
				for(int i=0;i<9;i++){
			for(int j=0;j<9;j++)
				cout<<char(board[i][j]+'0');
			cout<<endl;
		}
}	
		}
	
}