Advertisement
Guest User

Squirrel to the top !

a guest
Oct 24th, 2016
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.32 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define N 9
  5. #define TRUE 1
  6. #define FALSE 0
  7.  
  8.  
  9. void display_grid(int **grid);
  10. int test_numt(int **grid, int num, int row, int col);
  11. void solve(int **grid, int row, int col);
  12.  
  13. int main(int argc, char *argv[]){
  14.  
  15.   int i, j;
  16.   int **grid;
  17.  
  18.   // alloc-ons
  19.   grid = (int**) malloc(sizeof(int *) * N);
  20.   for(i=0; i<N; i++){
  21.     grid[i] = malloc(sizeof(int)*N);
  22.   }
  23.  
  24.   // initilize-ons
  25.   for(i=0; i<N; i++){
  26.     for(j=0; j<N; j++){
  27.       grid[i][j] = 0;
  28.     }
  29.   }
  30.  
  31.   solve(grid, 0, 0);
  32.  
  33.   // free-ons
  34.   for(i=0; i<N; i++){
  35.     free(grid[i]);
  36.   }
  37.   free(grid);
  38.  
  39.   return EXIT_SUCCESS;
  40. }
  41.  
  42. /*
  43.  * Display grid
  44.  */
  45. void display_grid(int **grid){
  46.   int i, j;
  47.  
  48.   printf("\n. - - - . - - - . - - - .\n");
  49.   for(i=0; i<N; i++){
  50.     for(j=0; j<N; j++){
  51.       if( j%3 == 0 )
  52.         printf("| ");
  53.       printf("\e[1m\x1B[31m%d \x1B[0m\e[0m", grid[i][j]);
  54.     }
  55.     if( (i+1)%3 == 0 )
  56.       printf("|\n. - - - . - - - . - - - .\n");
  57.     else
  58.       printf("|\n");
  59.   }
  60.  
  61. }
  62.  
  63. /*
  64.  * Test a number in a specific cell
  65.  */
  66. int test_num(int **grid, int num, int row, int col){
  67.  
  68.   int i, j, idi, idj;
  69.  
  70.   if( grid[row][col] != 0 ){
  71.     return FALSE;
  72.   }else{
  73.    
  74.     for(i=0; i<N; i++){
  75.       if( grid[row][i] == num || grid[i][col] == num ){
  76.         return FALSE;
  77.       }
  78.     }
  79.  
  80.     idi = (row/3) * 3;
  81.     idj = (col/3) * 3;
  82.     for(i=idi; i<idi+3; i++){
  83.       for(j=idj; j<idj+3; j++){
  84.         if( grid[i][j] == num ){
  85.           return FALSE;
  86.         }
  87.       }
  88.     }
  89.   }
  90.  
  91.   return TRUE;
  92. }
  93.  
  94. /*
  95.  * Solving sudoku using backtracking
  96.  *
  97.  */
  98. void solve(int **grid, int row, int col){
  99.  
  100.   int i;
  101.  
  102.   if( row >= N && col >= N ){
  103.     printf("\n I think I found a solution ! \n");
  104.     display_grid(grid);
  105.     return;
  106.   }else{
  107.  
  108.     if( grid[row][col] == 0 ){
  109.       for(i=1; i<=N; i++){
  110.         if( test_num(grid, i, row, col) ){
  111.           grid[row][col] = i;
  112.           //system("clear");
  113.           display_grid(grid);
  114.           if( col == N-1 ){
  115.             solve(grid, row+1, 0);
  116.           }else{
  117.             solve(grid, row, col+1);
  118.           }
  119.         }
  120.         grid[row][col] = 0;
  121.       }
  122.       //grid[row][col] = 0;
  123.     }else{
  124.       if( col == N-1 )
  125.         solve(grid, row+1, 0);
  126.       else
  127.         solve(grid, row, col+1);
  128.     }
  129.  
  130.   }
  131.  
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement