#include <stdio.h>
#include <string.h>
#include <memory.h>
#define ArSize(XX) (sizeof(XX)/sizeof(XX[0]))
 
int b_map[9][9],ans_cnt,left_cnt;
int b_garo[9][10],b_sero[9][10],b_caan[9][10];
char sp_pzl[][81]={\
".................................................................................",\
"52...6.........7.13...........4..8..6......5...........418.........3..2...87.....",\
"6.....8.3.4.7.................5.4.7.3..2.....1.6.......2.....5.....8.6......1....",\
".6.5.1.9.1...9..539....7....4.8...7.......5.8.817.5.3.....5.2............76..8..."};
 
void pr_pzl(int b_pzl[9][9]) {
	int i,j;
	puts("");
	for(i=0 ; i<9 ; ++i) {
		for(j=0 ; j<9 ; ++j) {
			printf("%d",b_pzl[i][j]);
			if(j==2 || j==5) printf("|");
		}
		puts("");
		if(i==2 || i==5) puts("---+---+---");
	}
	puts("");
}
 
int sfs_rdy(char *pzl) {
	int i,j,xx;
	ans_cnt=left_cnt=0;
	memset(b_map,0,sizeof b_map);
	memset(b_garo,0,sizeof b_garo);
	memset(b_sero,0,sizeof b_sero);
	memset(b_caan,0,sizeof b_caan);
	for(i=0 ; i<81 ; ++i) {
		if(pzl[i]>='0' && pzl[i]<='9') {
			b_map[i/9][i%9]=pzl[i]-'0';
		} else if(pzl[i]=='.') {
			b_map[i/9][i%9]=0;
		} else return -1;
	}
	for(i=0 ; i<9 ; ++i) {
		for(j=0 ; j<9 ;++j) {
			if(!(xx=b_map[i][j])) ++left_cnt;
			else if(b_garo[i][xx]||b_sero[j][xx]||b_caan[i/3*3+j/3][xx]) return -1;
			else {
				b_garo[i][xx]=1;
				b_sero[j][xx]=1;
				b_caan[i/3*3+j/3][xx]=1;
			}
		}
	}
	puts("Input puzzle : ");
	pr_pzl(b_map);
	return 0;
}
 
int pr_dab() {
	pr_pzl(b_map);
	if(++ans_cnt>1) {
		puts("Too many answers.");
		return -1;
	}
	return 0;
}
 
int sfs_slv(int rline) {
	int i,j,k;
	if(left_cnt==0) return pr_dab();
	for(i=rline ; i<9 ; ++i) {
		for(j=0 ; j<9 ; ++j) {
			if(b_map[i][j]==0) break;
		}
		if(j<9) break;
	}
	if(i==9&&j==9) return -2;
	for(k=1 ; k<=9 ; ++k) {
		b_map[i][j]=k;
		if(b_garo[i][k]||b_sero[j][k]||b_caan[i/3*3+j/3][k]) continue;
		else {
			b_garo[i][k]=1;
			b_sero[j][k]=1;
			b_caan[i/3*3+j/3][k]=1;
			--left_cnt;
			if(sfs_slv(i)!=0) return -1;
			++left_cnt;
			b_garo[i][k]=0;
			b_sero[j][k]=0;
			b_caan[i/3*3+j/3][k]=0;
		}
	}
	b_map[i][j]=0;
	return 0;
}
 
 
int main(int argc,char **argv) {
	int i;
	for(i=0 ; i<ArSize(sp_pzl) ; ++i) {
		if(sfs_rdy(sp_pzl[i])!=0) {
			puts("Wrong puzzle!!");
			continue;
		}
		puts("Solving...");
		sfs_slv(0);
		puts("Solved.\n");
	}
	return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPG1lbW9yeS5oPgojZGVmaW5lIEFyU2l6ZShYWCkgKHNpemVvZihYWCkvc2l6ZW9mKFhYWzBdKSkKCmludCBiX21hcFs5XVs5XSxhbnNfY250LGxlZnRfY250OwppbnQgYl9nYXJvWzldWzEwXSxiX3Nlcm9bOV1bMTBdLGJfY2Fhbls5XVsxMF07CmNoYXIgc3BfcHpsW11bODFdPXtcCiIuLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4iLFwKIjUyLi4uNi4uLi4uLi4uLjcuMTMuLi4uLi4uLi4uLjQuLjguLjYuLi4uLi41Li4uLi4uLi4uLi40MTguLi4uLi4uLi4zLi4yLi4uODcuLi4uLiIsXAoiNi4uLi4uOC4zLjQuNy4uLi4uLi4uLi4uLi4uLi4uNS40LjcuMy4uMi4uLi4uMS42Li4uLi4uLjIuLi4uLjUuLi4uLjguNi4uLi4uLjEuLi4uIixcCiIuNi41LjEuOS4xLi4uOS4uNTM5Li4uLjcuLi4uNC44Li4uNy4uLi4uLi41LjguODE3LjUuMy4uLi4uNS4yLi4uLi4uLi4uLi4uNzYuLjguLi4ifTsKCnZvaWQgcHJfcHpsKGludCBiX3B6bFs5XVs5XSkgewoJaW50IGksajsKCXB1dHMoIiIpOwoJZm9yKGk9MCA7IGk8OSA7ICsraSkgewoJCWZvcihqPTAgOyBqPDkgOyArK2opIHsKCQkJcHJpbnRmKCIlZCIsYl9wemxbaV1bal0pOwoJCQlpZihqPT0yIHx8IGo9PTUpIHByaW50ZigifCIpOwoJCX0KCQlwdXRzKCIiKTsKCQlpZihpPT0yIHx8IGk9PTUpIHB1dHMoIi0tLSstLS0rLS0tIik7Cgl9CglwdXRzKCIiKTsKfQoKaW50IHNmc19yZHkoY2hhciAqcHpsKSB7CglpbnQgaSxqLHh4OwoJYW5zX2NudD1sZWZ0X2NudD0wOwoJbWVtc2V0KGJfbWFwLDAsc2l6ZW9mIGJfbWFwKTsKCW1lbXNldChiX2dhcm8sMCxzaXplb2YgYl9nYXJvKTsKCW1lbXNldChiX3Nlcm8sMCxzaXplb2YgYl9zZXJvKTsKCW1lbXNldChiX2NhYW4sMCxzaXplb2YgYl9jYWFuKTsKCWZvcihpPTAgOyBpPDgxIDsgKytpKSB7CgkJaWYocHpsW2ldPj0nMCcgJiYgcHpsW2ldPD0nOScpIHsKCQkJYl9tYXBbaS85XVtpJTldPXB6bFtpXS0nMCc7CgkJfSBlbHNlIGlmKHB6bFtpXT09Jy4nKSB7CgkJCWJfbWFwW2kvOV1baSU5XT0wOwoJCX0gZWxzZSByZXR1cm4gLTE7Cgl9Cglmb3IoaT0wIDsgaTw5IDsgKytpKSB7CgkJZm9yKGo9MCA7IGo8OSA7KytqKSB7CgkJCWlmKCEoeHg9Yl9tYXBbaV1bal0pKSArK2xlZnRfY250OwoJCQllbHNlIGlmKGJfZ2Fyb1tpXVt4eF18fGJfc2Vyb1tqXVt4eF18fGJfY2FhbltpLzMqMytqLzNdW3h4XSkgcmV0dXJuIC0xOwoJCQllbHNlIHsKCQkJCWJfZ2Fyb1tpXVt4eF09MTsKCQkJCWJfc2Vyb1tqXVt4eF09MTsKCQkJCWJfY2FhbltpLzMqMytqLzNdW3h4XT0xOwoJCQl9CgkJfQoJfQoJcHV0cygiSW5wdXQgcHV6emxlIDogIik7Cglwcl9wemwoYl9tYXApOwoJcmV0dXJuIDA7Cn0KCmludCBwcl9kYWIoKSB7Cglwcl9wemwoYl9tYXApOwoJaWYoKythbnNfY250PjEpIHsKCQlwdXRzKCJUb28gbWFueSBhbnN3ZXJzLiIpOwoJCXJldHVybiAtMTsKCX0KCXJldHVybiAwOwp9CgppbnQgc2ZzX3NsdihpbnQgcmxpbmUpIHsKCWludCBpLGosazsKCWlmKGxlZnRfY250PT0wKSByZXR1cm4gcHJfZGFiKCk7Cglmb3IoaT1ybGluZSA7IGk8OSA7ICsraSkgewoJCWZvcihqPTAgOyBqPDkgOyArK2opIHsKCQkJaWYoYl9tYXBbaV1bal09PTApIGJyZWFrOwoJCX0KCQlpZihqPDkpIGJyZWFrOwoJfQoJaWYoaT09OSYmaj09OSkgcmV0dXJuIC0yOwoJZm9yKGs9MSA7IGs8PTkgOyArK2spIHsKCQliX21hcFtpXVtqXT1rOwoJCWlmKGJfZ2Fyb1tpXVtrXXx8Yl9zZXJvW2pdW2tdfHxiX2NhYW5baS8zKjMrai8zXVtrXSkgY29udGludWU7CgkJZWxzZSB7CgkJCWJfZ2Fyb1tpXVtrXT0xOwoJCQliX3Nlcm9bal1ba109MTsKCQkJYl9jYWFuW2kvMyozK2ovM11ba109MTsKCQkJLS1sZWZ0X2NudDsKCQkJaWYoc2ZzX3NsdihpKSE9MCkgcmV0dXJuIC0xOwoJCQkrK2xlZnRfY250OwoJCQliX2dhcm9baV1ba109MDsKCQkJYl9zZXJvW2pdW2tdPTA7CgkJCWJfY2FhbltpLzMqMytqLzNdW2tdPTA7CgkJfQoJfQoJYl9tYXBbaV1bal09MDsKCXJldHVybiAwOwp9CgoKaW50IG1haW4oaW50IGFyZ2MsY2hhciAqKmFyZ3YpIHsKCWludCBpOwoJZm9yKGk9MCA7IGk8QXJTaXplKHNwX3B6bCkgOyArK2kpIHsKCQlpZihzZnNfcmR5KHNwX3B6bFtpXSkhPTApIHsKCQkJcHV0cygiV3JvbmcgcHV6emxlISEiKTsKCQkJY29udGludWU7CgkJfQoJCXB1dHMoIlNvbHZpbmcuLi4iKTsKCQlzZnNfc2x2KDApOwoJCXB1dHMoIlNvbHZlZC5cbiIpOwoJfQoJcmV0dXJuIDA7Cn0=