shudu.cpp

求解数独问题, 能精确快速求解数独, 是用回溯法求的.

/*回溯法求解数独问题*/
# include<stdio.h>
int a[10][10]={{0,0,0,0,0,0,0,0,0,0},
               {0,0,0,3,8,1,0,0,0,9},
               {0,5,0,0,4,0,0,0,8,0},
               {0,0,6,0,9,0,0,1,0,0},
               {0,0,0,8,0,3,0,0,0,6},
               {0,0,0,0,0,0,0,0,0,0},
               {0,9,0,0,6,0,0,5,0,0},
               {0,0,0,6,0,0,9,0,1,0},
               {0,0,1,0,0,0,5,0,0,4},
               {0,2,0,0,0,4,8,7,0,0},};     /*数组a用来存放原始数据*/


int flag[10][10]={0};                      /*数组flag用来存放标志变量*/



int check(int i,int j,int k)             /*用来检验当前位置是否合适*/
    {
     int i1,j1,k1,i2,j2;
     for(j1=1;j1<=9;j1++)              /*检查行*/
       if(a[i][j1]==k&&j1!=j)
        break;
      if(j1<=9)  return 0;

     for(i1=1;i1<=9;i1++)           /*检查列*/
        if(a[i1][j]==k&&i1!=i)
         break;
       if(i1<=9) return 0;


     if(i%3!=0) i1=(i/3)*3+1;  else  i1=i-2;  /*求小方格的行初始下标*/
     if(j%3!=0) j1=(j/3)*3+1;  else  j1=j-2;  /*求小方格的列初始下标*/

     for(i2=i1;i2<=i1+2;i2++)       /*检查每个小方格*/
       {
       for(j2=j1;j2<=j1+2;j2++)
          {
          if(a[i2][j2]==k&&i2!=i&&j2!=j)
            {
             return 0;}
           }
        }
      if(k!=0)       return 1;
      else           return 0;
      }






void main()           /*数独问题的主函数*/
{

 int i,j,k;
 for(i=1;i<=9;i++)  /*初始化标志数组*/
  for(j=1;j<=9;j++)
     flag[i][j]=a[i][j];

 i=1;j=1; a[i][j]=1;
 do                                            /*用回溯法求解数独问题*/
  {

     for(k=a[i][j];k<=9;k++)               /*为下标为i,j的元素找适合的数据*/
     {
       if(check(i,j,k)==1)
         break;
     }

   if(k<=9)                             /*若该数位能找到数,则填入*/
     {
           a[i][j]=k;
           if(i==9&&j==9)            /*检查数独是否已填满,若满则输出之,并结束程序*/
         {
           for(i=1;i<=9;i++)
             { printf("\n");
               for(j=1;j<=9;j++)
                 printf("%d  ",a[i][j]);
              }
             break;
         }

           else                  /*若数得还未满则找下一个需要填数的位置*/
          {
             do
              {
               if(j==9&&i<9) {i++;j=1;}
               else
                j++;
                  }while(flag[i][j]!=0);

          }
      }


   else                    /*若该数位未找到适的数,则回溯到上一个被填的数*/
     {

         do
        { if(flag[i][j]==0) a[i][j]=0;
          if(j==1&&i>1)  {i--;j=9;}
          else            j--;
         }while(flag[i][j]!=0);

        a[i][j]++;

        if(i==1&&j==1&&a[1][1]>9)  break;
      }

}while(1);
 //getch();
}