This shows you the differences between two versions of the page.
cs:c_language:sudoku [2019/02/26 14:35] |
cs:c_language:sudoku [2020/11/26 23:18] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Sudoku ====== | ||
+ | **Concepts: | ||
+ | Matrices, function, algorithms of medium complexity | ||
+ | |||
+ | **Text:**\\ | ||
+ | Solve the sudoku game, given a '' | ||
+ | |||
+ | For instance, given the following matrix, with '' | ||
+ | |2|3|5|6|**0**|9|4|7|1| | ||
+ | |4|**0**|1|5|7|2|8|6|3| | ||
+ | |7|6|8|1|3|4|5|2|9| | ||
+ | |1|5|9|7|2|**0**|6|4|8| | ||
+ | |3|2|6|8|4|1|7|9|5| | ||
+ | |8|4|7|**0**|5|6|3|1|2| | ||
+ | |6|8|2|3|9|**0**|1|5|4| | ||
+ | |5|7|4|2|1|8|**0**|3|6| | ||
+ | |9|1|3|4|6|5|2|8|7| | ||
+ | |||
+ | the solution is: | ||
+ | |2|3|5|6|**8**|9|4|7|1| | ||
+ | |4|**9**|1|5|7|2|8|6|3| | ||
+ | |7|6|8|1|3|4|5|2|9| | ||
+ | |1|5|9|7|2|**3**|6|4|8| | ||
+ | |3|2|6|8|4|1|7|9|5| | ||
+ | |8|4|7|**9**|5|6|3|1|2| | ||
+ | |6|8|2|3|9|**7**|1|5|4| | ||
+ | |5|7|4|2|1|8|**9**|3|6| | ||
+ | |9|1|3|4|6|5|2|8|7| | ||
+ | |||
+ | Remember that the following three rules must be verified by a '' | ||
+ | * Each row (composed of '' | ||
+ | |||
+ | |9|1|3|4|6|5|2|8|7| | ||
+ | |||
+ | * Each column (composed of '' | ||
+ | |||
+ | |2| | ||
+ | |4| | ||
+ | |7| | ||
+ | |1| | ||
+ | |3| | ||
+ | |8| | ||
+ | |6| | ||
+ | |5| | ||
+ | |9| | ||
+ | |||
+ | * The '' | ||
+ | |||
+ | |7|2|3| | ||
+ | |8|4|1| | ||
+ | |9|5|6| | ||
+ | |||
+ | |||
+ | **Solution: | ||
+ | |||
+ | <file C sudoku.c> | ||
+ | /* Solve the sudoku game, given a '' | ||
+ | The numbers '' | ||
+ | */ | ||
+ | |||
+ | |||
+ | #include < | ||
+ | |||
+ | /* Dimension of a square sudoku matrix */ | ||
+ | #define D 9 | ||
+ | |||
+ | /* Print the sudoku matrix */ | ||
+ | void print_matr(int m[][D], int nr, int nc){ | ||
+ | int r, c; | ||
+ | | ||
+ | for (r=0; r<nr; r++) { | ||
+ | for (c=0; c<nc-1; c++) | ||
+ | printf(" | ||
+ | printf(" | ||
+ | } | ||
+ | } | ||
+ | |||
+ | |||
+ | /* Verify if the sudoku matrix m is a valid | ||
+ | | ||
+ | 1, otherwise the function returns 0 */ | ||
+ | int sudoku_matrix_verify(int m[][D], int dim) { | ||
+ | int r, c, n, found, r_sm, c_sm; | ||
+ | |||
+ | /* Analyze if all rows contains the numbers between 1 and 9 */ | ||
+ | for (r=0; r<dim; r++) { /* Fix the row */ | ||
+ | for (n=1; n<=9; n++) { /* Verify all the numbers from 1 to 9 */ | ||
+ | found = 0; | ||
+ | for (c=0; c<dim && !found; c++) { | ||
+ | if (m[r][c] == n) | ||
+ | found = 1; | ||
+ | } | ||
+ | if (found == 0) | ||
+ | return 0; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | /* Do the same for all the columns */ | ||
+ | for (c=0; c<dim; c++) { | ||
+ | for (n=1; n<=9; n++) { | ||
+ | found = 0; | ||
+ | for (r=0; r<dim && !found; r++) { | ||
+ | if (m[r][c] == n) | ||
+ | found = 1; | ||
+ | } | ||
+ | if (found == 0) | ||
+ | return 0; | ||
+ | } | ||
+ | } | ||
+ | | ||
+ | | ||
+ | /* Analyze all the 9 submatrices of dimension 3x3 */ | ||
+ | | ||
+ | /* Select a specific submatrix */ | ||
+ | for (r_sm=0; r_sm< | ||
+ | for (c_sm=0; c_sm< | ||
+ | for (n=1; n<=9; n++) { /* Verify all the numbers from 1 to 9 */ | ||
+ | /* ...checking if the number is contained in the submatrix */ | ||
+ | found = 0; | ||
+ | for (r=r_sm; r<r_sm+3 && !found; r++) { | ||
+ | for (c=c_sm; c<c_sm+3 && !found; c++) { | ||
+ | if (m[r][c] == n) | ||
+ | found = 1; | ||
+ | } | ||
+ | } | ||
+ | if (found == 0) | ||
+ | return 0; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return 1; | ||
+ | } | ||
+ | |||
+ | |||
+ | |||
+ | int main() { | ||
+ | |||
+ | /* The input matrix with unknown numbers */ | ||
+ | int m[D][D] = { | ||
+ | {2, | ||
+ | {4, | ||
+ | {7, | ||
+ | {1, | ||
+ | {3, | ||
+ | {8, | ||
+ | {6, | ||
+ | {5, | ||
+ | {9, | ||
+ | }; | ||
+ | |||
+ | /* The correct solution of the sudoku is... */ | ||
+ | /* int m[D][D] = { */ | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* | ||
+ | /* }; */ | ||
+ | |||
+ | int unknown_r[D*D], | ||
+ | int comb[D]; | ||
+ | int r, c, i; | ||
+ | int res; | ||
+ | |||
+ | print_matr(m, | ||
+ | |||
+ | /* Found the position of the 0s (i.e., unknown numbers) and | ||
+ | store their lines and columns */ | ||
+ | for (r=0; r<D; r++) { | ||
+ | for (c=0; c<D; c++) { | ||
+ | if (m[r][c] == 0) { | ||
+ | unknown_r[n_i] = r; | ||
+ | unknown_c[n_i] = c; | ||
+ | n_i++; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | printf(" | ||
+ | |||
+ | /* The algorithm tries all the possible combinations of numbers, | ||
+ | | ||
+ | | ||
+ | with all 1. The program then verify if a given combination | ||
+ | is a correct solution */ | ||
+ | for (i=0; i<n_i; i++) | ||
+ | comb[i] = 1; | ||
+ | | ||
+ | do { | ||
+ | /* Insert a specific combination into the sudoku matrix */ | ||
+ | for(i=0; i<n_i; i++) { | ||
+ | m[unknown_r[i]][unknown_c[i]] = comb[i]; | ||
+ | } | ||
+ | |||
+ | /* Verify if the solution is correct */ | ||
+ | res = sudoku_matrix_verify(m, | ||
+ | | ||
+ | /* Generate a new possible combination */ | ||
+ | comb[0]++; | ||
+ | for(i=0; i<n_i-1; i++) | ||
+ | if (comb[i]> | ||
+ | comb[i] = 1; | ||
+ | comb[i+1]++; | ||
+ | } | ||
+ | | ||
+ | if (res==1){ | ||
+ | printf(" | ||
+ | print_matr(m, | ||
+ | } | ||
+ | | ||
+ | /* }while(res==0 && comb[n_i-1]!=10); | ||
+ | }while(comb[n_i-1]!=10); | ||
+ | |||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | </ | ||