//#include "stdafx.h"
#include<stdio.h>
FILE *fin=fopen("input.txt", "r");
FILE *fout=fopen("output.txt", "w");
void back(int point);
int data[9][9];
int row_chk[9][9], col_chk[10][10];
int square_num[9][9], square_chk[9][9], square_cnt;
int zero_point[81][2], zero_cnt;
int main(){
int i, j, k, l;
for(i=0; i<9; i+=3){
for(j=0; j<9; j+=3){
for(k=i; k<i+3; k++){
for(l=j; l<j+3; l++){
square_num[k][l] = square_cnt; // 3*3 square array
}
}
square_cnt++;
}
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("%d",square_num[i][j]);
printf("\n");
}
for(i=0; i<9; i++){
for(j=0; j<9; j++){
fscanf(fin, "%d", &data[i][j]); // input data[i][j]
if(data[i][j]){
row_chk[i][data[i][j]]=1; // checking row data[i][j]
col_chk[j][data[i][j]]=1; // checking col data[i][j]
square_chk[square_num[i][j]][data[i][j]]=1; // checking square data[i][j]
}
else{
zero_point[zero_cnt][0] = i; // count 0 and save 0's row
zero_point[zero_cnt++][1] = j; // and save 0's col too
}
}
}
back(0); // start backtracking
fclose(fin);
fclose(fout);
return 0;
}
void back(int point)
{
printf("back tracking %d is started\n",point);
int i, j;
int x, y;
if(point == zero_cnt){ // 0 is all filled
for(i=0; i<9; i++){
for(j=0; j<9; j++){
fprintf(fout, "%d ", data[i][j]); // printing!!
}
fprintf(fout, "\n");
}
exit(0); // and teminate program
}
x = zero_point[point][0]; // (point+1)th 0's row (array is start from 0, so +1th is just "point")
y = zero_point[point][1]; // (point+1)th 0's col
for(i=1; i<=9; i++){
if(!row_chk[x][i-1] && !col_chk[y][i-1] && !square_chk[square_num[x][y]][i-1]){ // check data[x][y] is already used
row_chk[x][i-1] = col_chk[y][i-1] = square_chk[square_num[x][y]][i-1] = 1; // checking data[x][y] is used
data[x][y] = i; // and input i at data[x][y]
back(point + 1); // we have more work...
data[x][y] = row_chk[x][i-1] = col_chk[y][i-1] = square_chk[square_num[x][y]][i-1] = 0; // if "back() is failed, init cell
}
}
printf("back tracking %d is ends\n",point);
}