数独1--暴力回溯法（时间超）

一、心得

可用暴力搜索法（找唯一数单元格）和算法求解

先回顾之前的三篇文章

“”，介绍求解数独的基本的暴力搜索法

“”，网友介绍的求解数独的舞蹈链（Dancing Links）算法，这篇文章是介绍舞蹈链（Dancing Links）算法的。

“”，该文介绍了用舞蹈链（Dancing Links）算法求解数独，并给出了暴力破解法和舞蹈链（Dancing Links）算法之间的时间和空间占用效率的对比。

二、题目及分析

 

三、代码

时间超，未解决

1 /*  2 0 0 0 5 0 0 0 0 7  3 4 8 0 0 0 6 3 2 0  4 0 0 9 4 0 0 0 0 8  5 5 0 0 3 0 7 0 0 0  6 8 0 7 0 9 4 1 5 2  7 2 9 6 8 1 0 0 0 4  8 3 5 2 7 4 9 8 1 6  9 7 4 0 1 6 3 2 9 0 10 0 6 1 0 5 0 0 0 3 11 算法： 12 有点像八皇后问题  13 每一列至少都有一个 14 每一行至少有一个 15 每一个3*3小方框里面至少有一个 16  17 总过有9列，c[i][j]==1表示第i列的数字j已经有了 18 总过有9行，r[i][j]==1表示第i行的数字j已经有了 19 总过有9行，q[i][j]==1表示第k(从上到小，从左到右)个3*3的框数字j已经有了  20  21 只能摆那些没有被数字占了的位置 22  23 优化1:1-9每个数字只能出现9次 24 numTimes[i]表示数字i出现的次数  25   26   27 */  28  29 #include 
     
       30 #include 
      
        31 using namespace std; 32 int c[10][10],r[10][10],q[10][10]; 33 int num[10][10]; 34 int numTimes[10];  35 int step=0; 36  37 void readDate(){ 38     for(int i=1;i<=9;i++){ 39         for(int j=1;j<=9;j++){ 40             int x; 41             cin>>x; 42             if(x){ 43                 step++; 44                 numTimes[x]++; 45                 num[i][j]=x; 46                 r[i][x]=1; 47                 c[j][x]=1; 48                 //找到行列对应的小方框  49                 int m=(i-1)/3*3; 50                 int n=(j-1)/3; 51                 int t=m+n+1; 52                 q[t][x]=1;  53             } 54              55         } 56     } 57 } 58  59 void printData(int a[10][10]){ 60     for(int i=1;i<=9;i++){ 61         for(int j=1;j<=9;j++){ 62             printf("%3d",a[i][j]); 63         } 64         cout<