POJ2627 数独 （dfs or bfs）

POJ2627 数独 （dfs or bfs）

给出一个数独，空白用0表示，输出一个合理答案即可；

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

常规dfs对每一个为0的单元对1-9进行判断，如果可以填，dfs下一个空，如果不可以，返回到上一个空。值得注意的是需要用一个变量记录当前填到的位置，当全部填完时就不再继续尝试其他的答案；

#include <cstdio>
#include <cstring>
int table[9][9];
int now;
bool check(int num,int p){
	if(table[p / 9][p % 9] == 0) {
		for(int i = 0;i < 9;i++) {
			if(table[i][p % 9] == num || table[p / 9][i] == num) return false;
		}
		int x = (p / 9 / 3) * 3, y = (p % 9 / 3) * 3;
		for(int i = 0;i < 3;i++){
			for(int j = 0;j < 3;j++){
				if(table[x + i][y + j] == num) return false;
			}
		}
	}
	return true;
}
void dfs(int cur){
	if(now == 80){
		return;
	}
	if(table[cur / 9][cur % 9] == 0){
		for(int i = 1;i <= 9;i++){
			if(check(i,cur)){
				table[cur / 9][cur % 9] = i;
				now = cur;
				dfs(cur + 1);
				if(now == 80){
					return;
				}
				table[cur / 9][cur % 9] = 0;
			}
		}
	}
	else{
		now = cur;
		dfs(cur + 1);
		if(now == 80){
			return;
		}
	}
	
}
int main() {
	int n;
	scanf("%d", &n);
	while(n--){
		for(int i = 0;i < 9;i++){
			for(int j = 0;j < 9;j++)
				scanf("%1d", &table[i][j]);
		}
		now = 0;
		dfs(0);
		for(int i = 0;i < 9;i++){
			for(int j = 0;j < 9;j++){
				printf("%d",table[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}