Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #define N 9
- #define TRUE 1
- #define FALSE 0
- void display_grid(int **grid);
- int test_numt(int **grid, int num, int row, int col);
- void solve(int **grid, int row, int col);
- int main(int argc, char *argv[]){
- int i, j;
- int **grid;
- // alloc-ons
- grid = (int**) malloc(sizeof(int *) * N);
- for(i=0; i<N; i++){
- grid[i] = malloc(sizeof(int)*N);
- }
- // initilize-ons
- for(i=0; i<N; i++){
- for(j=0; j<N; j++){
- grid[i][j] = 0;
- }
- }
- solve(grid, 0, 0);
- // free-ons
- for(i=0; i<N; i++){
- free(grid[i]);
- }
- free(grid);
- return EXIT_SUCCESS;
- }
- /*
- * Display grid
- */
- void display_grid(int **grid){
- int i, j;
- printf("\n. - - - . - - - . - - - .\n");
- for(i=0; i<N; i++){
- for(j=0; j<N; j++){
- if( j%3 == 0 )
- printf("| ");
- printf("\e[1m\x1B[31m%d \x1B[0m\e[0m", grid[i][j]);
- }
- if( (i+1)%3 == 0 )
- printf("|\n. - - - . - - - . - - - .\n");
- else
- printf("|\n");
- }
- }
- /*
- * Test a number in a specific cell
- */
- int test_num(int **grid, int num, int row, int col){
- int i, j, idi, idj;
- if( grid[row][col] != 0 ){
- return FALSE;
- }else{
- for(i=0; i<N; i++){
- if( grid[row][i] == num || grid[i][col] == num ){
- return FALSE;
- }
- }
- idi = (row/3) * 3;
- idj = (col/3) * 3;
- for(i=idi; i<idi+3; i++){
- for(j=idj; j<idj+3; j++){
- if( grid[i][j] == num ){
- return FALSE;
- }
- }
- }
- }
- return TRUE;
- }
- /*
- * Solving sudoku using backtracking
- *
- */
- void solve(int **grid, int row, int col){
- int i;
- if( row >= N && col >= N ){
- printf("\n I think I found a solution ! \n");
- display_grid(grid);
- return;
- }else{
- if( grid[row][col] == 0 ){
- for(i=1; i<=N; i++){
- if( test_num(grid, i, row, col) ){
- grid[row][col] = i;
- //system("clear");
- display_grid(grid);
- if( col == N-1 ){
- solve(grid, row+1, 0);
- }else{
- solve(grid, row, col+1);
- }
- }
- grid[row][col] = 0;
- }
- //grid[row][col] = 0;
- }else{
- if( col == N-1 )
- solve(grid, row+1, 0);
- else
- solve(grid, row, col+1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement