2199.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2199 on 2006-04-10 at 20:18:03 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

bool vst[3][10][10];
char game[10][10], line[9];

bool find(int, int);

int main()
{
	int t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		if(t != 0) printf("---\n");
		gets(line); memset(vst, false, sizeof(vst));
		bool vaild = true;
		for(i = 0; i < 9; i++) {
			gets(game[i]);
			for(j = 0; j < 9; j++) {
				if(game[i][j] == '?') continue;
				int n = game[i][j] - '0', s = (i/3)*3+j/3;
				if(vst[0][i][n] || vst[1][j][n] || vst[2][s][n]) vaild = false;
				vst[0][i][n] = vst[1][j][n] = vst[2][s][n] = true;
			}
		}
		if(vaild && find(0, 0))
			for(i = 0; i < 9; i++) puts(game[i]);
		else printf("impossible\n");
	}
	
	return 0;
}

bool find(int x, int y)
{
	if(x == 9) return true;
	else if(y == 9) return find(x+1, 0);
	else if(game[x][y] != '?') return find(x, y+1);
	else {
		int s = (x/3)*3+y/3, i;
		for(i = 1; i <= 9; i++) {
			if(vst[0][x][i] || vst[1][y][i] || vst[2][s][i]) continue;
			vst[0][x][i] = vst[1][y][i] = vst[2][s][i] = true; game[x][y] = i+'0';
			if(find(x, y+1)) return true;
			vst[0][x][i] = vst[1][y][i] = vst[2][s][i] = false; game[x][y] = '?';
		}
		return false;
	}
}