追蹤
愛瑋斯坦の冒險日記にようこそ
關於部落格
「星屑のなかで出會えた奇跡が 」
  • 182111

    累積人氣

  • 7

    今日人氣

    23

    追蹤人氣

[遞迴應用] 數獨破解程式 (使用C) 附帶計概期末心得XDD

如果家裡有買過X由時報的應該都知道週末版的背面有附數獨的題目吧ˇˇ


其實我對數獨原本沒什麼興趣的XDDD 以前看到題目頂多無聊玩一下下就膩了,不過有一天突然發現可以利用「遞迴」來解,整個人於是燃了起來暴肝完成了程式,以下就是數獨簡介和思考過程。。。。


-----------------------------以下資料由維基大百科提供-------------------------

1.何謂數獨?
        數獨是一種源自18世紀末的瑞士數學家歐拉所創造的拉丁方塊游戲。


2.數獨玩法?
        在9格寬×9格高的大九宮格中有9個3格寬×3格高的小九宮格,並提供一定數量的數字。根據這些數字,利用邏輯和推理,在其他的空格上填入1到9的數字。每個數字在每個小九宮格內不能出現一樣的數字,每個數字在每行、每列也不能出現一樣的數字。 這種遊戲只需要邏輯思維能力,與數字運算無關。雖然玩法簡單,但數字排列方式卻千變萬化,所以不少教育者認為數獨是鍛鍊腦筋的好方法。


3.數獨組合?
        9! × 72 2 × 27 × 27,704,267,971=66,7090,3752,0210,7293,6960個組合,在2005年由Bertram Felgenhauer利用暴力法和邏輯計算出,如果將重複(如數字轉換,反射面等)不計算,那5,472,730,538個組合。

----------------------------------------------------------------------------

#思考過程

基本上中心思想很簡單,利用「遞迴」的觀念,把數獨的格子視為一個棋盤,每次填空格時從左邊填到右邊,再從上面填到下面,利用三個簡單的副程式判別是否能夠填進去空格


row()          <==檢查要填進去的數字是否在此"列"中已經被使用過了。
column()   <==檢查要填進去的數字是否在此"行"中已經被使用過了。
block()       <==檢查要填進去的數字是否在此"九宮格"已經被使用過了。



再利用遞迴與FOR迴圈產生數狀結構讓電腦去一個個Try & Error,簡單的說就是把每一格視為一個節點,由上面三個程式與迴圈產生「可能的候選元素」,然後產生支路(分歧),就這樣一直Run下去,只要發現無法再填進任何數字時,就把這個支路斷掉,直到達到「終止條件」(也就是成功填到最後一格)再把結果顯示在銀幕上。


不過中間也遇到了一些困難,因為再打的時候不小心忽略了一個判列條件,導致我程式跑了整整6個多小時才跑出來,結果還錯的XDDDD,完全找不出來錯在哪,還好後來終於DEBUG成功,花不到0.1秒的時間答案就出來了...C這種程序導向的語言果然差之毫里,失之千里阿。


下面就是完整版的程式...不過真的是又臭又長,因為原本的程式只有約4分之一,龜毛的我加了一些控制的功能-0- 如


1.利用system("cls")的功能產生簡潔並直覺的畫面(個人覺得啦XD)
2.可以在途中把之前的結果重新更改,不然打錯一個就要重頭輸入...
3.直接開始分析,因為有的題目後面幾乎都空格
4還有一個花了我最長的時間的功能,就是利用事前分析,把絕對不可能的元素剔除掉,並把一看就知道的答案直接補上,這個功能立意良好,因為正常人在解數獨題目的時後通常第一步都是先找出可直接看出來的空格,並一步步篩選要填的數字。


不過我忽略了一點,那就是電腦的計算速度太快了,解一題的時間根本不用0.1秒,就算有加速效果也顯著不到哪去-.-.....................不然就是答案無窮多組,有加速跟沒加速好像差不多.......


--------------------------------附上完整的程式碼-------------------------------

以下程式碼是利用DEV C++ 4.992版寫出來的,若要儲存檔名請打.c

#include <stdio.h>
#include <math.h> 
#define N 9
 
typedef struct{
               char c[9];
               int lenth;
                         }element;
int count=0;
int ans=0;
 
void printx(char a[N][N]);
void print(char a[N][N]);
int row(char a[N][N],char x,int i);
int column(char a[N][N],char x,int j);
int block(char a[N][N],char x,int i,int j);
void ele(char a[N][N],element b[N][N]);
void sudu(char a[N][N],element b[N][N],int i,int j);
 
int main()
{  
    int i,j,r,s;
    char check;
    char a[N][N]={'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n',
                  'n','n','n','n','n','n','n','n','n'};
    printf("*********歡迎使用數獨解答程式1.0版,作者Ewestein**********n");
    printf("*                                                        *n");          
    printf("*1.請開始輸入數字(1 ~ 9),由左而右,由上到下(Row Major)。*n");
    printf("*2.若為空白請鍵入'n'(null)。                             *n");  
    printf("*3.若要更改前次數值請鍵入'b'(back)。                     *n");  
    printf("*4.若要直接開始請鍵入's'(start)。                        *n");
    printf("*5.若要直接結束程式請鍵入'e'(exit)。                     *n");
    printf("*                                                        *n");
    printf("**********************************************************nnn");
    for(i=0;i<N;i++)
       for(j=0;j<N;)
       { a[i][j+1]='';           
         printf("請輸入第(%d,%d)格數字:",i+1,j+1);             
         scanf("%s",&check);
         if(check=='e')
            exit(0);
         if(check!='n' && check!='b' && check!='s')
           if(check>'9' || check<'1')
              {
                 system("cls"); 
                 printx(a);       
                 printf("請輸入1~9之數字!n");     
                 continue;
              }         
        
          if(row(a,check,i))
            if(column(a,check,j)) 
              if(block(a,check,i,j))  
                {   a[i][j]=check;
                    if(a[i][j]=='s')
                    { 
                       for(r=i+1;r<N;r++)
                           for(s=0;s<N;s++)
                             a[r][s]='n';
                       for(s=j;s<N;s++)
                             a[i][s]='n';     
                            
                       goto start;            
                    }
                    if(a[i][j]=='b')
                      {  
                       for(r=i+1;r<N;r++)
                         for(s=0;s<N;s++)
                           a[r][s]='n';
                       for(s=j;s<N;s++)
                         a[i][s]='n';  
                         if(j>0)
                           j=j-2;
                         else
                          {
                           i=i-1;
                           j=(N-2)   ;
                          }    
                          a[i][j+1]='';
                      }
                    system("cls"); 
                    printx(a);
                    j++;
                 }
            else { system("cls"); printx(a); printf("不好意思,此數值在同一個九宮格已經使用過n");}
           else { system("cls"); printx(a); printf("不好意思,此數值在同行已經使用過n");} 
         else  { system("cls"); printx(a); printf("不好意思,此數值在同列已經使用過n");}
      }
        
      
          
    start:         
    printf("nn這是你輸入的原始數據:n");           
    print(a);
    printf("若正確請按Enter開始分析:nn");
    system("pause");
 
    
    element b[N][N];
    ele(a,b);
 
    sudu(a,b,0,0);
   
    if(ans==0)
      printf("nn***非常抱歉,此題無解****nn");
   system("pause");
   return 0; 
}
 
void sudu(char a[N][N],element b[N][N],int i,int j)
{   
     count++;
     int next_i,next_j,v,q,flag=1,space=0;
     int p;
     char r;
     char c[N][N];
     int copy_i,copy_j;
     for(copy_i=0;copy_i<N;copy_i++)
        for(copy_j=0;copy_j<N;copy_j++)
          c[copy_i][copy_j]=a[copy_i][copy_j];   
    
     if(i==N)   
       {
          printf("nn電腦一共計算了%d種組合nn",count);
          for(v=0;v<N;v++)
             for(q=0;q<N;q++)
               if(c[v][q]=='n')
                {
                  flag=0;      
                  space++;
                }  
          if(flag==1)
          { 
             ans++;         
         
             printf("解答%d:n",ans);       
             print(c);
           } 
         
       }  
     else
     {
              if(j<(N-1))
                {
                  next_i=i;
                  next_j=j+1;
                }
               else
                {
                  next_i=i+1;
                  next_j=0;
                }   
    
         if(c[i][j]=='n')
         {
            for(p=0;p<b[i][j].lenth;p++)
            {
              r=b[i][j].c[p];                        
               if(row(c,r,i))
                 if(column(c,r,j))
                   if(block(c,r,i,j))
                   { 
                       c[i][j]=r;
                        sudu(c,b,next_i,next_j); 
                   }
                 
                  
            }
         }
        else
         sudu(c,b,next_i,next_j);
     }
                       
}
 
void ele(char a[N][N],element b[N][N])
{
 
    int i,j,k,r,s,t,u;            
    char l;
    int flag=1;
   
    while(flag==1)
    {
        flag=0;         
        for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
          {
             for(k=0,l='1';k<N;k++,l++)
                b[i][j].c[k]=l;
             b[i][j].lenth=0;    
          }          
        for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
            for(k=0;k<N;k++)
              if(a[i][k]!='n')
              b[i][j].c[a[i][k]-49]='0';
        for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
            for(k=0;k<N;k++)
              if(a[k][j]!='n')
              b[i][j].c[a[k][j]-49]='0';
         for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
          {
              if(i>2)
                if(i>5)
                   r=6;
                else r=3;
              else r=0;
   
              if(j>2)
                if(j>5)
                   s=6;
                else s=3;
              else s=0;  
         
             for(t=r;t<r+3;t++)
               for(u=s;u<s+3;u++)
                if(a[t][u]!='n')
                 b[i][j].c[a[t][u]-49]='0';                 
          }              
     
     
         for(i=0;i<N;i++) 
           for(j=0;j<N;j++)
           {
              for(k=0;k<N-1;k++)
              {int p=1;
                while(b[i][j].c[k]=='0')
                 {                                      
                  b[i][j].c[k]= b[i][j].c[k+p];
                  b[i][j].c[k+p]='0';
                  p++;
                  if((k+p)>8)
                   break;
                 }
              }
           }               
   
        for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
             for(k=0;k<N;k++)
                if(b[i][j].c[k]!='0')
                 b[i][j].lenth++;
      
        for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
             for(k=0;k<N;k++)
                  if(b[i][j].lenth==1)   
                     if(a[i][j]=='n')
                     {
                        a[i][j]=b[i][j].c[0];
                        flag=1;
                     }
    }              
      
 
      printf("nnn各位置的可能元素有:n")    ;
       for(i=0;i<N;i++) 
          for(j=0;j<N;j++)
             {
             printf("(%d,%d)={",i+1,j+1);            
             for(k=0;k<N;k++)
                 printf("%c",b[i][j].c[k]) ;
             printf("}  可能元素有=%d種",b[i][j].lenth); 
            printf("n");
             } 
        
}    
 
int row(char a[N][N],char x,int i)
{
    int j,flag=1;
    if(x=='n')
     return flag;
    for(j=0;j<N;j++)
     if(x==a[i][j])
       flag=0;
    return flag;  
}
 
int column(char a[N][N],char x,int j)
{
    int i,flag=1;
    if(x=='n')
     return flag;
    for(i=0;i<N;i++)
     if(x==a[i][j])
       flag=0;
    return flag;  
}
 
int block(char a[N][N],char x,int i,int j)
{
    int r,s,flag=1;
    if(x=='n')
     return flag;
    if(i>2)
      if(i>5)
        i=6;
      else i=3;
    else i=0;
   
    if(j>2)
      if(j>5)
        j=6;
      else j=3;
    else j=0;  
         
 
   
    for(r=i;r<(i+3);r++)
      for(s=j;s<(j+3);s++)
       if(x==a[r][s])
        flag=0;
    return  flag; 
}   
 
void print(char a[N][N])
{
     int i,j;
    
      for(i=0;i<N;i++)
    {
     printf(" ");              
     for(j=0;j<N;j++)
     {         
       if(j==(N)/sqrt(N) || j==2*(N)/sqrt(N) )
       printf("  ");             
       printf("---");
       
     }
     if(i==(N)/sqrt(N) || i==2*(N)/sqrt(N) )
     {
      printf("n");
      printf(" ");          
      for(j=0;j<N;j++)
       {
        if(j==(N)/sqrt(N) || j==2*(N)/sqrt(N) )
       printf("  ");   
       printf("---");              
       }
     }  
     printf("n");
  
                    
     for(j=0;j<N;j++)
     {
        if(j==(N)/sqrt(N) || j==2*(N)/sqrt(N) )
       printf("|");         
       if(a[i][j]!='n')   
       printf("|%c",a[i][j]);
       else
       printf("| ");
     } 
     printf("|n");
    } 
       printf(" ");
      for(i=0;i<N;i++)
      {
        if(i==(N)/sqrt(N) || i==2*(N)/sqrt(N) )              
       printf("  ");
       printf("---");
      }
       printf("n");
}
 
void printx(char a[N][N])
{
     int i,j;
    
      for(i=0;i<N;i++)
    {
     printf(" ");              
     for(j=0;j<N;j++)
     {         
       if(j==(N)/sqrt(N) || j==2*(N)/sqrt(N) )
       printf("  ");             
       printf("---");
       
     }
     if(i==(N)/sqrt(N) || i==2*(N)/sqrt(N) )
     {
      printf("n");
      printf(" ");          
      for(j=0;j<N;j++)
       {
        if(j==(N)/sqrt(N) || j==2*(N)/sqrt(N) )
       printf("  ");   
       printf("---");              
       }
     }  
     printf("n");
  
                    
     for(j=0;j<N;j++)
     {
        if(j==(N)/sqrt(N) || j==2*(N)/sqrt(N) )
       printf("|");         
       if(a[i][j]!='n')   
       printf("|%c",a[i][j]);
       else
       printf("|x");
     } 
     printf("|n");
    } 
       printf(" ");
      for(i=0;i<N;i++)
      {
        if(i==(N)/sqrt(N) || i==2*(N)/sqrt(N) )              
       printf("  ");
       printf("---");
      }
       printf("n");
}

-----------------------------以下為計概期末心得-----------------------------

差點忘了貼初開版圖的正確解答XD


      大一的計算機概論終於結束了,王壘大大真的讓我學到很多有關計算機組織還有程式語言的知識ˋ▽ˊ


      程式語言是資工系的專長,但我相信能從王壘的大刀下PASS的絕對不會輸資工系太多,(不過二年級以後大概就輸了,畢竟程式是他們的吃飯傢伙阿=口=+)。他的教法是告訴你必備的材料,然後讓你自己去思考整個邏輯結構,而不是直接告訴你怎麼解,慢慢暗示引導你找出答案,有時候他問完問題的瞬間,我就大概知道他要問什麼了....這種心臟碰碰跳的感覺除了國中小的數理課和美術課發表作品以後再也沒有過,曾幾何時,已被填鴨式的教育給麻痺了對數理的興趣。要形容王大刀的話,引用冬瓜的名言:「雖然很臭屁,但是真的很強~~」如果遇到的是其他老師,我可能會覺得C 語言沒什麼有趣的吧@@。


  順便感謝一下助教冬瓜,我第一次遇到這麼(會講冷笑話)盡責的助教,不但上起課來不會死氣沉沉,而且還在課後幫我們開遊戲教學課程(雖然我只學到「終極密碼」,之後的沒時間參加><),最後還在我們參加計概實習比賽的時候幫我們做了整整10幾頁的power point,雖然身材很冬瓜不過很有領導魅力。



  不過電機系系上開的計算機組課程還真的有點少,只有一上選修的資料結構和二下的微處理機比較有關係而已,只能希望8月底的選課結果能夠選到資料結構摟~^^"



文章到此結束!

                                        以上.......
相簿設定
標籤設定
相簿狀態