2263.cpp

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

/* This Code is Submitted by wywcgs for Problem 2263 on 2006-10-31 at 19:58:41 */
#include <cstdio>
#include <algorithm>
using namespace std;
 
int s[9][9];
bool vst[3][9][10];
 
bool set(int, int, int, bool);
bool find(int, int);
 
int main()
{
	int i, j, t;
	
	for(t = 1; true; t++) {
		memset(vst, false, sizeof(vst));
		for(i = 0; i < 9; i++)
			for(j = 0; j < 9; j++) {
				scanf("%d", &s[i][j]);
				if(s[i][j] == -1) return 0;
				else if(s[i][j] != 0) set(i, j, s[i][j], true);
			}
		if(t != 1) putchar('\n');
		printf("Case %d:\n", t);
		find(0, 0);
	}
}
 
bool set(int x, int y, int v, bool p)
{
	int r = x/3, c = y/3, cd = r*3+c;
	if(vst[0][x][v] == p || vst[1][y][v] == p || vst[2][cd][v] == p) return false;
	vst[0][x][v] = vst[1][y][v] = vst[2][cd][v] = p;
	return true;
}
bool find(int x, int y)
{
	int i, j;
	if(x == 9) {
		for(i = 0; i < 9; i++)
			for(j = 0; j < 9; j++)
				printf("%d%c", s[i][j], j == 8 ? '\n' : ' ');
		return true;
	} else if(y == 9) return find(x+1, 0);
	else {
		if(s[x][y] != 0) return find(x, y+1);
		for(i = 1; i <= 9; i++) {
			if(!set(x, y, i, true)) continue;
			s[x][y] = i;
			if(find(x, y+1)) return true;
			set(x, y, i, false); s[x][y] = 0;
		}
		return false;
	}
}