#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;
for(i=0 ; i<9 ; ++i) {
for(j=0 ; j<9 ; ++j) {
}
if(i
==2 || i
==5) puts("---+---+---"); }
}
int sfs_rdy(char *pzl) {
int i,j,xx;
ans_cnt=left_cnt=0;
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;
}
}
}
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) {
continue;
}
sfs_slv(0);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPG1lbW9yeS5oPgojZGVmaW5lIEFyU2l6ZShYWCkgKHNpemVvZihYWCkvc2l6ZW9mKFhYWzBdKSkKCmludCBiX21hcFs5XVs5XSxhbnNfY250LGxlZnRfY250OwppbnQgYl9nYXJvWzldWzEwXSxiX3Nlcm9bOV1bMTBdLGJfY2Fhbls5XVsxMF07CmNoYXIgc3BfcHpsW11bODFdPXtcCiIuLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4iLFwKIjUyLi4uNi4uLi4uLi4uLjcuMTMuLi4uLi4uLi4uLjQuLjguLjYuLi4uLi41Li4uLi4uLi4uLi40MTguLi4uLi4uLi4zLi4yLi4uODcuLi4uLiIsXAoiNi4uLi4uOC4zLjQuNy4uLi4uLi4uLi4uLi4uLi4uNS40LjcuMy4uMi4uLi4uMS42Li4uLi4uLjIuLi4uLjUuLi4uLjguNi4uLi4uLjEuLi4uIixcCiIuNi41LjEuOS4xLi4uOS4uNTM5Li4uLjcuLi4uNC44Li4uNy4uLi4uLi41LjguODE3LjUuMy4uLi4uNS4yLi4uLi4uLi4uLi4uNzYuLjguLi4ifTsKCnZvaWQgcHJfcHpsKGludCBiX3B6bFs5XVs5XSkgewoJaW50IGksajsKCXB1dHMoIiIpOwoJZm9yKGk9MCA7IGk8OSA7ICsraSkgewoJCWZvcihqPTAgOyBqPDkgOyArK2opIHsKCQkJcHJpbnRmKCIlZCIsYl9wemxbaV1bal0pOwoJCQlpZihqPT0yIHx8IGo9PTUpIHByaW50ZigifCIpOwoJCX0KCQlwdXRzKCIiKTsKCQlpZihpPT0yIHx8IGk9PTUpIHB1dHMoIi0tLSstLS0rLS0tIik7Cgl9CglwdXRzKCIiKTsKfQoKaW50IHNmc19yZHkoY2hhciAqcHpsKSB7CglpbnQgaSxqLHh4OwoJYW5zX2NudD1sZWZ0X2NudD0wOwoJbWVtc2V0KGJfbWFwLDAsc2l6ZW9mIGJfbWFwKTsKCW1lbXNldChiX2dhcm8sMCxzaXplb2YgYl9nYXJvKTsKCW1lbXNldChiX3Nlcm8sMCxzaXplb2YgYl9zZXJvKTsKCW1lbXNldChiX2NhYW4sMCxzaXplb2YgYl9jYWFuKTsKCWZvcihpPTAgOyBpPDgxIDsgKytpKSB7CgkJaWYocHpsW2ldPj0nMCcgJiYgcHpsW2ldPD0nOScpIHsKCQkJYl9tYXBbaS85XVtpJTldPXB6bFtpXS0nMCc7CgkJfSBlbHNlIGlmKHB6bFtpXT09Jy4nKSB7CgkJCWJfbWFwW2kvOV1baSU5XT0wOwoJCX0gZWxzZSByZXR1cm4gLTE7Cgl9Cglmb3IoaT0wIDsgaTw5IDsgKytpKSB7CgkJZm9yKGo9MCA7IGo8OSA7KytqKSB7CgkJCWlmKCEoeHg9Yl9tYXBbaV1bal0pKSArK2xlZnRfY250OwoJCQllbHNlIGlmKGJfZ2Fyb1tpXVt4eF18fGJfc2Vyb1tqXVt4eF18fGJfY2FhbltpLzMqMytqLzNdW3h4XSkgcmV0dXJuIC0xOwoJCQllbHNlIHsKCQkJCWJfZ2Fyb1tpXVt4eF09MTsKCQkJCWJfc2Vyb1tqXVt4eF09MTsKCQkJCWJfY2FhbltpLzMqMytqLzNdW3h4XT0xOwoJCQl9CgkJfQoJfQoJcHV0cygiSW5wdXQgcHV6emxlIDogIik7Cglwcl9wemwoYl9tYXApOwoJcmV0dXJuIDA7Cn0KCmludCBwcl9kYWIoKSB7Cglwcl9wemwoYl9tYXApOwoJaWYoKythbnNfY250PjEpIHsKCQlwdXRzKCJUb28gbWFueSBhbnN3ZXJzLiIpOwoJCXJldHVybiAtMTsKCX0KCXJldHVybiAwOwp9CgppbnQgc2ZzX3NsdihpbnQgcmxpbmUpIHsKCWludCBpLGosazsKCWlmKGxlZnRfY250PT0wKSByZXR1cm4gcHJfZGFiKCk7Cglmb3IoaT1ybGluZSA7IGk8OSA7ICsraSkgewoJCWZvcihqPTAgOyBqPDkgOyArK2opIHsKCQkJaWYoYl9tYXBbaV1bal09PTApIGJyZWFrOwoJCX0KCQlpZihqPDkpIGJyZWFrOwoJfQoJaWYoaT09OSYmaj09OSkgcmV0dXJuIC0yOwoJZm9yKGs9MSA7IGs8PTkgOyArK2spIHsKCQliX21hcFtpXVtqXT1rOwoJCWlmKGJfZ2Fyb1tpXVtrXXx8Yl9zZXJvW2pdW2tdfHxiX2NhYW5baS8zKjMrai8zXVtrXSkgY29udGludWU7CgkJZWxzZSB7CgkJCWJfZ2Fyb1tpXVtrXT0xOwoJCQliX3Nlcm9bal1ba109MTsKCQkJYl9jYWFuW2kvMyozK2ovM11ba109MTsKCQkJLS1sZWZ0X2NudDsKCQkJaWYoc2ZzX3NsdihpKSE9MCkgcmV0dXJuIC0xOwoJCQkrK2xlZnRfY250OwoJCQliX2dhcm9baV1ba109MDsKCQkJYl9zZXJvW2pdW2tdPTA7CgkJCWJfY2FhbltpLzMqMytqLzNdW2tdPTA7CgkJfQoJfQoJYl9tYXBbaV1bal09MDsKCXJldHVybiAwOwp9CgoKaW50IG1haW4oaW50IGFyZ2MsY2hhciAqKmFyZ3YpIHsKCWludCBpOwoJZm9yKGk9MCA7IGk8QXJTaXplKHNwX3B6bCkgOyArK2kpIHsKCQlpZihzZnNfcmR5KHNwX3B6bFtpXSkhPTApIHsKCQkJcHV0cygiV3JvbmcgcHV6emxlISEiKTsKCQkJY29udGludWU7CgkJfQoJCXB1dHMoIlNvbHZpbmcuLi4iKTsKCQlzZnNfc2x2KDApOwoJCXB1dHMoIlNvbHZlZC5cbiIpOwoJfQoJcmV0dXJuIDA7Cn0=