C语言求解数独

作者: 泡泡腾
发布时间:2015-07-07 16:46:03

平时喜欢玩数独游戏,昨日突发想用程序自动求解。思路是回溯法,不断试探。

程序代码如下:

  1 #include<stdio.h>    2     3 /*    4 {0,0,4,6,0,2,0,9,1},    5 {2,1,0,9,8,4,0,5,6},    6 {9,0,0,0,7,1,4,2,0},    7 {1,2,5,0,6,0,3,4,7},    8 {4,7,6,0,0,0,9,8,5},    9 {8,3,9,0,4,0,1,6,2},   10 {0,9,1,2,5,0,0,0,4},   11 {5,8,0,4,1,6,0,3,9},   12 {6,4,0,3,0,7,5,0,0}};   13 */   14    15 int data[9][9] = {   16 {0,7,0,2,6,0,9,0,0},   17 {3,0,0,0,0,8,0,0,7},    18 {0,9,0,0,5,7,0,0,0},    19 {5,0,0,0,0,0,0,7,0},    20 {0,4,7,3,1,2,8,5,0},    21 {0,8,0,0,0,0,0,0,1},    22 {0,0,0,8,2,0,0,4,0},    23 {7,0,0,6,0,0,0,0,2},    24 {0,0,4,0,3,9,0,8,0}};   25    26 void input()   27 {   28     int i,j;   29     for(i = 0;i < 9;i++)   30         for(j = 0;j < 9;j++)   31             scanf("%d",&data[i][j]);   32 }   33    34 void output()   35 {   36     int i,j;   37     for(i = 0;i < 9;i++)   38     {   39         for(j = 0;j < 9;j++)   40             printf("%d ",data[i][j]);   41         printf("\n");   42     }   43     printf("\n");   44 }   45    46 /*检查num是否可放置在3*3区域是否有冲突*/   47 int CheckSquare(int line,int col,int num)   48 {   49     int i = (line / 3) * 3;   50     int j = (col / 3) * 3;   51     int m,n;   52     for(m = i;m < i + 3;m++)   53         for(n = j;n < j + 3;n++)   54             if((data[m][n] == num) && !(m == line && n == col))   55                 return 0;   56     return 1;   57 }   58    59 /*检查行冲突*/   60 int CheckLine(int line,int col,int num)   61 {   62     int i = 9;   63     while(i--)   64         if((data[line][i] == num) && (i != col))   65             return 0;   66     return 1;   67 }   68    69 /*检查列冲突*/   70 int CheckColumn(int line,int col,int num)   71 {   72     int i = 9;   73     while(i--)   74         if((data[i][col] == num) && (i != line))   75             return 0;   76     return 1;   77 }   78    79 /*检查i行j列是否可放置num*/   80 int Check(int i,int j,int num)   81 {   82     return CheckSquare(i,j,num) && CheckLine(i,j,num) && CheckColumn(i,j,num);   83 }   84    85 /*检查是否完成*/   86 int IsDone()   87 {   88     int i,j;   89     for(i = 0;i < 9;i++)   90         for(j = 0;j < 9;j++)   91             if(!Check(i,j,data[i][j]) || (data[i][j] == 0))   92                 return 0;   93     return 1;   94 }   95    96 void Calc()   97 {   98     int i,j,x;   99     if(IsDone())  100     {  101         output();  102         return;  103     }  104     for(i = 0;i < 9;i++)  105     {  106         for(j = 0;j < 9;j++)  107         {  108             if(data[i][j] == 0)  109             {  110                 for(x = 1; x <= 9;x++)  111                 {  112                     if(Check(i,j,x))  113                     {  114                         data[i][j] = x;  115                         Calc();  116                     }  117                 }  118                 if(x == 10)  119                 {  120                     data[i][j] = 0;  121                     return ;  122                 }  123             }  124         }  125     }  126 }  127   128 int main()  129 {  130 //    input();  131     Calc();  132     output();  133   134     return 0;  135 }

上述程序中,数字0表示该位置为空,待填入数字。

标签: C语言
来源:http://www.cnblogs.com/renteng/archive/2012/05/26/2519308.ht

推荐: