歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C語言遞歸解決數獨

運行程序,依次輸入數獨中的81個數,數獨中沒有數字的地方輸入0,感覺需要輸入那麼多數太麻煩了,請大家指導如何改的簡單一點。

  1. #include<stdio.h>   
  2. #include<stdlib.h>   
  3. #define DEBUG   
  4. int shukudo[9][9];  
  5. typedef struct shudo{  
  6.     int x;  
  7.     int y;  
  8.     struct shudo * next;  
  9. }shukudo_ptr;  
  10.   
  11. int count = 0;  
  12. void display_shukudo();  
  13. int check_right(shukudo_ptr*,int);  
  14.   
  15. void solution(shukudo_ptr *empty_ptr)  
  16. {  
  17.     if(!empty_ptr)  
  18.     {  
  19.         display_shukudo();  
  20.         return;  
  21.     }  
  22.   
  23.     for(int i = 1; i < 10; ++i)  
  24.     {  
  25.         if(check_right(empty_ptr,i))  
  26.         {  
  27.             shukudo[empty_ptr->x][empty_ptr->y] = i;  
  28.             solution(empty_ptr->next);  
  29.         }  
  30.         shukudo[empty_ptr->x][empty_ptr->y] = 0;  
  31.     }  
  32. }  
  33.   
  34. int check_right(shukudo_ptr *empty_ptr,int n)  
  35. {  
  36.     for(int i = 0; i < 9; ++i)  
  37.     {  
  38.         if(shukudo[empty_ptr->x][i] == n)  
  39.         {  
  40.             return 0;  
  41.         }  
  42.     }  
  43.   
  44.     for(int i = 0; i < 9; ++i)  
  45.     {  
  46.         if(shukudo[i][empty_ptr->y] == n)  
  47.         {  
  48.             return 0;  
  49.         }  
  50.     }  
  51.   
  52.     int start_x = empty_ptr->x / 3 * 3;  
  53.     int start_y = empty_ptr->y / 3 * 3;  
  54.       
  55.     for(int i = start_x; i < start_x + 3; ++i)  
  56.     {  
  57.         for(int j = start_y; j < start_y + 3; ++j)  
  58.         {  
  59.             if(shukudo[i][j] == n)  
  60.             {  
  61.                 return 0;  
  62.             }  
  63.         }  
  64.     }  
  65.   
  66.     return 1;  
  67. }  
  68.   
  69.   
  70. void display_shukudo()  
  71. {  
  72.     ++count;  
  73.     printf("solution %d\n",count);  
  74.     for(int i = 0; i < 9; ++i)  
  75.     {  
  76.         for(int j = 0; j < 9; ++j)  
  77.         {  
  78.             printf("%d ",shukudo[i][j]);  
  79.         }  
  80.         printf("\n");  
  81.     }  
  82.   
  83.     printf("\n\n");  
  84. }  
  85.   
  86. int main(void)  
  87. {  
  88.     shukudo_ptr *empty_ptr = NULL;  
  89.     shukudo_ptr *operate = NULL;  
  90.     shukudo_ptr *last = NULL;  
  91.       
  92.     for(int i = 0; i < 9; ++i)  
  93.     {  
  94.         for(int j = 0; j < 9; ++j)  
  95.         {  
  96.             printf("(%d,%d): ",i,j);  
  97.             scanf("%d",&shukudo[i][j]);  
  98.               
  99.             if(shukudo[i][j] == 0)  
  100.             {  
  101.                 operate = (shukudo_ptr*)malloc(sizeof(shukudo_ptr));  
  102.                 operate->x = i;  
  103.                 operate->y = j;  
  104.                 operate->next = NULL;  
  105.                 if(!empty_ptr)  
  106.                 {  
  107.                     empty_ptr = operate;  
  108.                     last = empty_ptr;  
  109.                 }  
  110.                 else  
  111.                 {  
  112.                     last->next = operate;  
  113.                     last = operate;  
  114.                 }  
  115.             }  
  116.         
  117.         }  
  118.     }  
  119.       
  120.   
  121.   
  122.     solution(empty_ptr);  
  123.       
  124.     while(empty_ptr)  
  125.     {  
  126.         operate = empty_ptr;  
  127.         empty_ptr = empty_ptr -> next;  
  128.         free(operate);  
  129.     }  
  130.     return 0;  
  131. }  
Copyright © Linux教程網 All Rights Reserved