#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int** create_sudoku();
int** read_sudoku();
void print_sudoku(int** sudoku);
int calculate_square(int lin, int col);
bool solve(int ***sudoku, int lin, int col);

bool lines[9][10], columns[9][10], squares[9][10]; 

int main(){
    //int** sudoku = create_sudoku();
    int** sudoku = read_sudoku();
    //print_sudoku(sudoku);

    memset(lines, 0, sizeof(lines));
    memset(columns, 0, sizeof(columns));
    memset(squares, 0, sizeof(squares));

    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            int val = sudoku[i][j];
            if(val != 0){
                lines[i][val] = true;
                columns[j][val] = true;
                squares[calculate_square(i, j)][val] = true;
            }
        }
    }
    printf("\n\n");
    solve(&sudoku, 0, 0);
}

int** read_sudoku(){
    int s[9][9];
    printf("0 for the empty spaces: \n");
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            scanf("%d", &s[i][j]);
        }
    }

    int **r = (int**)malloc(sizeof(int*)*9);
    for(int i = 0; i < 9; ++i){
        r[i] = (int*)malloc(sizeof(int)*9);

        for(int j = 0; j < 9; ++j){
            r[i][j] = s[i][j];
        }
    }

    return r;
}

bool solve(int ***sudoku, int lin, int col){
    if(col == 9){
        print_sudoku(*sudoku);
        return true;
    }

    if((*sudoku)[lin][col] != 0){
        if(lin < 8){
            if(solve(sudoku, lin+1, col)){
                return true;
            }
        }
        else {
            if(solve(sudoku, 0, col+1)){
                return true;
            }
        }
    }else{
        for(int i=1; i<=9; ++i){
            if(!lines[lin][i] && !columns[col][i] && !squares[calculate_square(lin, col)][i]){
                lines[lin][i] = true;
                columns[col][i] = true;
                squares[calculate_square(lin, col)][i] = true;
                (*sudoku)[lin][col] = i;
                
                if(lin < 8){
                    if(solve(sudoku, lin+1, col)){
                        return true;
                    }
                }
                else{
                    if(solve(sudoku, 0, col+1)){
                        return true;
                    }
                }
            
                lines[lin][i] = false;
                columns[col][i] = false;
                squares[calculate_square(lin, col)][i] = false;
                (*sudoku)[lin][col] = 0;
            }
        }
    }
    return false;
}

int calculate_square(int lin, int col){
    return (lin/3)*3 + col/3;
}

void print_sudoku(int** sudoku){
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            printf("%d ", sudoku[i][j]);
        }
        printf("\n");
    }
}

int** create_sudoku(){
    int s[9][9] = {
        2,0,0,   0,0,3,  7,9,4,
        4,0,0,   6,0,5,  0,8,0,
        0,0,1,   0,0,7,  0,0,0,

        0,3,2,   0,0,0,  0,0,8,
        0,0,4,   0,0,0,  9,0,0,
        9,0,0,   0,0,0,  5,4,0,

        0,0,0,   9,0,0,  1,0,0,
        0,4,0,   5,0,6,  0,0,7,
        3,8,5,   1,0,0,  0,0,9,
    };

    int **r = (int**)malloc(sizeof(int*)*9);
    for(int i = 0; i < 9; ++i){
        r[i] = (int*)malloc(sizeof(int)*9);

        for(int j = 0; j < 9; ++j){
            r[i][j] = s[i][j];
        }
    }

    return r;
}