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

動機
  • 要如何寫個能解數獨的程式呢?
    隨著數獨的風行,程式設計的老師常常以此為題,要求學生寫個解題的程式。
    自數獨樂園開張以來,要求提供原始碼的要求就不曾斷過。
    幫還是不幫好呢?幫了,好像在作弊,不幫又好像敝帚自珍,所以乾脆公開算了!
  • 當然也有些人並不是為了寫作業,而是為了研究數獨,才提出此要求。這時如果能有個範例,提供一個初步的架構, 接下去的工作就簡單多了。
  • 程式不使用任何技巧,完全採試誤法,有人會說:這樣做需要很長時間的試誤吧!程式的執行可以給你解答。
  • 請編輯後,在命令列中將單列格式數獨放在參數中,只要有解,一定可獲得解答;如果是多重解,只解出一解就會停止。
    例: sudoku 802609051000800600000000049050200008008563900900007030530000000001008000480705203
C 語言原始碼
	#include < stdio.h >
	#include < stdlib.h >
	
	int sudoku[81] ;                                // 數獨題目陣列
	int tempNum[81] ;                               // 上一次填數位置
	int tempSp= 0 ;                                 // 上一次填數位置指標
	int startH[81] ;                                // 列位置的起點
	int startV[81] ;                                // 行位置的起點
	int startB[81] ;                                // 九宮格位置的起點
	int addH[9] ;                                   // 列位置的加值
	int addV[9] ;                                   // 行位置的加值
	int addB[9] ;                                   // 九宮格位置的加值
	
	int main(int argc, char *argv[]) {
	   int j ; 
	   if(argc>1) for(j=0; j<81; j++) sudoku[j]= argv[1][j]-'0' ;
	   else exit(0) ;
	   printf( "------------------\n");
	   printSudoku(sudoku) ;
	   init() ;                                     // 參數設定
	   tryAns() ;                                   // 測試求解
	   printf( "------------------\n");
	   printSudoku(sudoku) ;
	   printf( "------------------\n");
	}
	
	int init() {
	   // 參數設定(設定這些參數之後,無論檢查行、列、九宮格都方便多了)
	   int i ;
	   for(i=0; i<81; i++) {
	      startH[i]= i/9* 9 ;                       // 列位置的起點
	      startV[i]= i% 9 ;                         // 行位置的起點
	      startB[i]= ((i/9)/3)*27+ ((i%9)/3)*3 ;    // 九宮格位置的起點
	   }
	   for(i=0; i<9; i++) {
	      addH[i]= i ;                              // 列位置的加值
	      addV[i]= i*9 ;                            // 行位置的加值
	      addB[i]= (i/3)*9+ (i%3) ;                 // 九宮格位置的加值
	   }
	}
	
	int printSudoku(int *prn) {
	   // 印出數獨題目(陣列內容)
	   int i ;
	   for(i=0; i<81; i++) {
	      printf( "%2d", prn[i]);
	      if(i%9==8) printf("\n");
	   }
	}
	
	int tryAns() {
	   // 測試求解
	   int sp=getNextBlank(-1) ;                    // 取得第一個空白的位置開始填入數字
	   do {
	      sudoku[sp]++ ;                            // 將本位置數字加 1
	      if(sudoku[sp]>9) {                        // 如果本位置的數字已大於 9 時則回到上一個位置繼續測試
	         sudoku[sp]= 0 ;
	         sp= pop() ;
	      } else {
	         if(check(sp)==0) {                     // 如果同行、列、九宮格都沒有相同的數字,則到下一個空白處繼續
	            push(sp) ;                          // 當然,如果發現有相同的數字時,就需把原位置的數字加 1(所以本處什麼都不做)
	            sp= getNextBlank(sp) ;
	         }
	      }
	   } while(sp>=0 && sp<81) ;
	}
	
	int getNextBlank(int sp) {
	   // 取得下一個空白的位置
	   do {
	      sp++ ;
	   } while(sp<81 && sudoku[sp]>0) ;
	   return(sp) ;
	}
	
	int check(int sp) {
	   // 檢查同行、列、九宮格有沒有相同的數字,若有傳回 1
	   int fg= 0 ;
	   if(!fg) 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<9; 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  | 回上頁 | 回首頁 |