C语言数独解题程序代码

周一四月 03, 2017 2:27 pm

程序代码由尤怪老师和谢道台老师提供。
显示效果不佳请您使用DejaVu Sans Mono或Courier New等等宽字体。
此程序并不是为了帮助作弊，而是用来进行数独的相关研究。
本程序不需要任何的逻辑技巧，而是暴力猜数的形式。
此例能够解答非无解题目，并给出第一个解；如果只有一个解则直接给出其解。

例： sudoku 802609051000800600000000049050200008008563900900007030530000000001008000480705203

#include
#include

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]) ;
}

周一四月 03, 2017 2:30 pm

在上一版的程式中，尤怪仅提供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

#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]) ;
}

C语言数独解题程序代码

C语言数独解题程序代码

回复： C语言数独解题程序代码