diff options
| -rw-r--r-- | solve.c | 82 |
1 files changed, 74 insertions, 8 deletions
@@ -4,14 +4,17 @@ #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(); - print_sudoku(sudoku); + //int** sudoku = create_sudoku(); + int** sudoku = read_sudoku(); + //print_sudoku(sudoku); memset(lines, 0, sizeof(lines)); memset(columns, 0, sizeof(columns)); @@ -27,15 +30,78 @@ int main(){ } } } - + 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){ - /* - 0 1 2 - 3 4 5 - 6 7 8 - */ return (lin/3)*3 + col/3; } |