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

typedef char Sudoku[81];
typedef enum { true, false } bool;

bool* get_possible_solutions(Sudoku s, int row, int col) {
    bool* solutions = malloc(sizeof(bool)*10);

    for(int i = 0; i < 10; i++) solutions[i] = true;

    for(int ccol = 0; ccol < 9; ccol++)
        solutions[ s[row*9+ccol] ] = false;

    for(int crow = 0; crow < 9; crow++)
        solutions[ s[crow*9+col] ] = false;

    for(int crow = row - row%3, rsteps = 0; rsteps < 3; crow++, rsteps++) {
        for(int ccol = col - col%3, csteps = 0; csteps < 3; ccol++, csteps++) {
            solutions[ s[crow*9 + ccol] ] = false;

        }
    }

    return solutions;
}

int sudoku_solve_rec(Sudoku s, int row, int col) {
    if(row >= 9)
        return 1;
    if(col >= 9)
        return sudoku_solve_rec(s, row + 1, 0);

    if(s[row*9+col] != 0)
        return sudoku_solve_rec(s, row, col + 1);

    bool* solutions = get_possible_solutions(s, row, col);

    for(int solution = 1; solution <= 9; solution++) {
        if(solutions[solution] == false) continue;
        s[row*9+col] = solution;
        if(sudoku_solve_rec(s, row, col + 1)) {
            free(solutions);
            return 1;
        }
    }

    s[row*9+col] = 0;

    free(solutions);

    return 0;
}

int sudoku_solve(Sudoku s) {
    return sudoku_solve_rec(s, 0,0);
}

int main( int argc, char *argv[] ) {

    Sudoku s = {
        0,3,0,0,0,0,0,0,0,
        0,0,0,1,9,5,0,0,0,
        0,0,8,0,0,0,0,6,0,
        8,0,0,0,6,0,0,0,0,
        4,0,0,8,0,0,0,0,1,
        0,0,0,0,2,0,0,0,0,
        0,6,0,0,0,0,2,8,0,
        0,0,0,4,1,9,0,0,5,
        0,0,0,0,0,0,0,7,0
    };

    if(sudoku_solve(s)) {
        printf("Solved\n");
    } else {
        printf("Not solved\n");
    }

    for(int row = 0; row < 9; row++) {
        for(int col = 0; col < 9; col++) {
            printf("%d ",s[row*9+col]);
        }
        printf("\n");
    }

	return 0;
}