//#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); }