C 語言數獨解題程式原始碼II

動機
  • 在上一版的程式中,尤怪僅提供 9*9 數獨的解題及唯一解的解答,如果是 4*4、6*6 數獨,或是多重解、無解題等,程式就沒有良好的回應了。
  • 本版可同時適用在 4*4、5*5、6*6、7*7、8*8、9*9、10*10的數獨,若是唯一解,可列出其解,若是多重解,在列出兩個解之後才停止, 若為無解題,也能分辨提示。
  • 請編輯後,在命令列中將單列格式數獨放在參數中即可。
    例:(4*4 數獨) sudoku 4030000000201000
    例:(5*5 數獨) sudoku 1300030405000004010200021
    例:(6*6 數獨) sudoku 053000200030006010030400010002000140
    例:(9*9 數獨) sudoku 802609051000800600000000049050200008008563900900007030530000000001008000480705203
C 語言原始碼
#include < stdio.h >
#include < stdlib.h >
	
int blockNumTbl[11]= {0, 1, 2, 3, 2, 5, 3, 7, 4, 3, 5} ;
int sudoku[100] ;                                // 數獨題目陣列
int tempNum[100] ;                               // 上一次填數位置
int tempSp= 0 ;                                  // 上一次填數位置指標
int startH[100] ;                                // 列位置的起點
int startV[100] ;                                // 行位置的起點
int startB[100] ;                                // 宮位置的起點
int addH[10] ;                                   // 列位置的加值
int addV[10] ;                                   // 行位置的加值
int addB[10] ;                                   // 宮位置的加值
int numRows= 3 ;                                 // 方陣大小
int numCells ;                                   // 格子總數
int blockNum ;                                   // 宮橫向大小
int blockNum2 ;                                  // 宮縱向大小

int main(int argc, char *argv[]) {
   int j ;
   if(argc>1) getVar(argv[1]) ; else exit(0) ;
   printf( "------------------\n");
   printSudoku(sudoku) ;
   init() ;                                     // 參數設定
   j= tryAns() ;                                // 測試求解
   printf( "------------------\n");
   if(j==1) {
      printf( "本題是唯一解數獨!\n");
   }else if(j>1) printf( "有多重解!\n");
   else printf( "本題無解!\n");
}

int getVar(char *testStr) {
   int j ; 
   numRows= 3 ;                                 // 方陣階數
   do {
      numRows++ ;                               // 方陣階數
      numCells= numRows* numRows ;              // 格子總數
   } while(numCells< strlen(testStr)) ;
   blockNum= blockNumTbl[numRows] ;
   blockNum2= numRows/ blockNum ;
   for(j=0; j< numCells; j++) sudoku[j]= testStr[j]-'0' ;
}

int init() {
   // 參數設定(設定這些參數之後,無論檢查行、列、宮都方便多了)
   int i ;
   for(i=0; i< numCells; i++) {
      startH[i]= i/numRows* numRows ;           // 列位置的起點
      startV[i]= i% numRows ;                               // 行位置的起點
      startB[i]= ((i/numRows)/blockNum2)*numRows*blockNum2+ ((i%numRows)/blockNum)*blockNum ;          // 宮位置的起點
   }
   for(i=0; i< numRows; i++) {
      addH[i]= i ;                              // 列位置的加值
      addV[i]= i*numRows ;                      // 行位置的加值
      addB[i]=(i/blockNum)*numRows+(i%blockNum);// 宮位置的加值
   }
}

int printSudoku(int *prn) {
   // 印出數獨題目(陣列內容)
   int i ;
   for(i=0; i< numCells; i++) {
      printf( "%2d", prn[i]);
      if(i%numRows==(numRows-1)) printf("\n");
   }
}

int tryAns() {
   // 測試求解
   int sum=0 ;
   int sp=getNextBlank(-1) ;                    // 取得第一個空白的位置開始填入數字
   do {
      sudoku[sp]++ ;                            // 將本位置數字加 1
      if(sudoku[sp] > numRows) {                  // 如果本位置的數字已大於 9 時則回到上一個位置繼續測試
         sudoku[sp]= 0 ;
         sp= pop() ;
      } else {
         if(check(sp)==0) {                     // 如果同行、列、宮都沒有相同的數字,則到下一個空白處繼續
            push(sp) ;                          // 當然,如果發現有相同的數字時,就需把原位置的數字加 1(所以本處什麼都不做)
            sp= getNextBlank(sp) ;
            if(sp==numCells) {
               printf( "------------------\n");
               printSudoku(sudoku) ;
               sum++ ;
               sp= pop() ;
            }           
         }
      }
   } while(sp>=0 && sp< numCells && sum<2) ;
   return(sum) ;
}

int getNextBlank(int sp) {
   // 取得下一個空白的位置
   do {
      sp++ ;
   } while(sp< numCells && sudoku[sp]>0) ;
   return(sp) ;
}

int check(int sp) {
   // 檢查同行、列、宮有沒有相同的數字,若有傳回 1
   int fg= 0 ;
   fg= check1(sp, startH[sp], addH) ;           // 檢查同宮有沒有相同的數字
   if(!fg) fg= check1(sp, startV[sp], addV) ;   // 檢查同宮有沒有相同的數字
   if(!fg) fg= check1(sp, startB[sp], addB) ;   // 檢查同宮有沒有相同的數字
   return(fg) ;
}   

int check1(int sp, int start, int *addnum) {
   // 檢查指定的行、列、宮有沒有相同的數字,若有傳回 1
   
   int fg= 0, i, sp1  ;
   for(i=0; i< numRows; i++) {
      sp1= start+ addnum[i] ;
      if(sp!=sp1 && sudoku[sp]==sudoku[sp1]) fg++ ;
   }
   return(fg) ;
}   

int push(int sp) {
   // 將指定的位置放入堆疊中
   tempNum[tempSp++]= sp ;
}

int pop() {
   // 取出堆疊中的上一個位置
   if(tempSp<=0) return(-1) ;
   else return(tempNum[--tempSp]) ;
}   

	
本網頁建置日期:95.10.22 | 最近更新日期:95.10.22  | 回上頁 | 回首頁 |