sudoku solve with C

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

kjwon15

I'm a hacker, I want to improve life.

Leave a Reply

Your email address will not be published. Required fields are marked *

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.