# 13333 - Stewie vs Brian > author: daisyliu0225 ###### tags: recursion --- ## Thinking 我原先的想法是把所有的可能性全部列出來，但後來發現有一些格子可能會有兩個可能的數字，這樣又會回到遞迴的處理。不然還有另一個解法但助教說很複雜。所以之後乾脆用遞迴寫了。 ## Overall thought (Brute-Force) Step1：看到一個新的格子(以0為代表) --> 開始從1開始測試這一個為0的格子的橫排跟縱排 --> 如果可以，先將這一個格子填為1，如果不行，就加1(其他就依此類推) Step2：如果這一格格子掛掉了 --> 後退到剛剛那一格 --> 繼續尋找下一個可行的數字 Step3：一直到所有格子都有答案為止，就可以產生答案了！如果沒有答案，就產生no solution的答案 聽起來很簡單，但我錯了...寫的過程真的是一波三折QQ。 程式雛型大概長這樣 ```cpp= int main(){ scanf(sudoku); check sudoku space to space; if(sudoku(space)==0){ check from 1 to 9 which fits the space; if(number fits) sudoku(space)=number; else{ space-1; check again; } //number not fits } if(solved) printf(sudoku); else printf(no solution); return 0; } ``` ## Problems Occurred! Q1.測試總是不會第一次就成功，如何知道掛掉？ A1.如果從1~9都無法填入格子內，就可以知道這一個格子是掛掉的 --> 格子後退一格(最鄰近的0的位置) Q2.慘了，我不知道0在哪裡 A2.創建兩個數獨array，一個是改變前的array，一個是改變後的array，這樣在尋找哪一個數字沒有被填過，找改變前的array就好了 Q3.怎麼一直叭股拉(我搞了三天才想出原因) A3.沒有清除改變後array的資料當然一直叭股阿廢話！ :cry: Q4.一直跳出no solution，該如何處理？ A4.用exit(0)的指令 :::info :bulb: **The exit command** In computing, exit is a command used in many operating system command-line shells and scripting languages. -- from Wiki 簡單來說，使用了exit command就可以讓程式或是者是小函數們立刻停止。我在這邊是使用在no solution 指令上。 一般而言，如果要使用exit command，後面的小括號會打上0，代表正常的中止程序。 像這樣 ```cpp= exit(0); ``` ::: ## Code 我懶惰不想要打註解，相信大家一定都看得懂。而且(應該)也不會有人來看我的東西啦XD ```cpp= //note 1=die 0=live #include <stdio.h> #include <stdlib.h> int skudou[9][9]; int ch_skudou[9][9]; int print=0; int check_square(int i, int j, int k){ int ri,rj; ri=(i+1)%3; rj=(j+1)%3; if(ri==1){ if(rj==1){ if(ch_skudou[i+1][j+1]==k||ch_skudou[i+1][j+2]==k||ch_skudou[i+2][j+1]==k||ch_skudou[i+2][j+2]==k) return 0; else return 1; } else if(rj==2){ if(ch_skudou[i+1][j-1]==k||ch_skudou[i+1][j+1]==k||ch_skudou[i+2][j-1]==k||ch_skudou[i+2][j+1]==k) return 0; else return 1; } else if(rj==0){ if(ch_skudou[i+1][j-2]==k||ch_skudou[i+1][j-1]==k||ch_skudou[i+2][j-2]==k||ch_skudou[i+2][j-1]==k) return 0; else return 1; } }else if(ri==2){ if(rj==1){ if(ch_skudou[i-1][j]==k||ch_skudou[i-1][j+2]==k||ch_skudou[i+1][j+1]==k||ch_skudou[i+1][j+2]==k) return 0; else return 1; } else if(rj==2){ if(ch_skudou[i-1][j-1]==k||ch_skudou[i-1][j+1]==k||ch_skudou[i+1][j-1]==k||ch_skudou[i+1][j+1]==k) return 0; else return 1; } else if(rj==0){ if(ch_skudou[i-1][j-2]==k||ch_skudou[i-1][j-1]==k||ch_skudou[i+1][j-2]==k||ch_skudou[i+1][j-1]==k) return 0; else return 1; } }else if(ri==0){ if(rj==1){ if(ch_skudou[i-2][j+1]==k||ch_skudou[i-2][j+2]==k||ch_skudou[i-1][j+1]==k||ch_skudou[i-1][j+2]==k) return 0; else return 1; } else if(rj==2){ if(ch_skudou[i-2][j-1]==k||ch_skudou[i-2][j+1]==k||ch_skudou[i-1][j-1]==k||ch_skudou[i-1][j+1]==k) return 0; else return 1; } else if(rj==0){ if(ch_skudou[i-2][j-2]==k||ch_skudou[i-2][j-1]==k||ch_skudou[i-1][j-2]==k||ch_skudou[i-1][j-1]==k) return 0; else return 1; } } } //ok int check(int i,int j,int k){ int s=0; for(int f=0;f<9;f++){ if(ch_skudou[f][j]!=k&&ch_skudou[i][f]!=k){ continue; }else { s=1; return 0; } } if(s==0){ int checksqu; checksqu=check_square(i,j,k); if(checksqu==1){ return 1; } else { return 0; } } } //ok void solve(int i,int j,int x){ int counter=0; if((i>=0&&i<9)&&(j>=0&&j<9)){ if(skudou[i][j]!=0){ if(j==8){ solve(i+1,0,1); } else { solve(i,j+1,1); } }else{ if(x==0) counter=1; else counter=x; for(int k=x;k<10;k++){ int c = check(i,j,k); if(c==1) { ch_skudou[i][j]=k; if(j==8) { solve(i+1,0,1); }else { solve(i,j+1,1); } } else{ counter++; if(counter==10){ counter=0; ch_skudou[i][j]=0; if(j==0){ i=i-1; j=8; }else j--; while(skudou[i][j]!=0){ if(j==0){ i=i-1; j=8; }else j--; } solve(i,j,ch_skudou[i][j]); break; }else continue; } } } } else if(i==9&&j==0){ for(int k=0;k<9;k++){ for(int l=0;l<8;l++){ printf("%d ",ch_skudou[k][l]); } printf("%d\n",ch_skudou[k][8]); } } else{ if(print==0){ print=1; printf("no solution\n"); exit(0); } return 1; } } int main() { for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ scanf("%d",&skudou[i][j]); ch_skudou[i][j]=skudou[i][j]; } } int sw=0; solve(0,0,1); return 0; } //ok ``` ## Reference --數獨part-- [數獨sudoku解答計算器 by布丁布丁吃什麼？](https://blog.pulipuli.info/2006/05/sudoku.html?showComment=1546683280101) [iT邦幫忙[演算法][JavaScript]演算法挑戰系列(10)-Valid Sudoku by神Q超人](https://ithelp.ithome.com.tw/articles/10198639) [學會了回溯演算法，我終於會做數獨了 by@osc_sdc55qra](https://www.gushiciku.cn/pl/glKd/zh-tw) 資工系朋朋們、快被我煩死的室友、HuTAs --exit command-- [exit(command) from Wikipedia](https://en.wikipedia.org/wiki/Exit_(command)) [exit command from tutorialspoint](https://www.tutorialspoint.com/what-is-exit-function-in-c-language) --HackMD筆記程式碼-- [曾經使用過NTHU judge的某學長](https://hackmd.io/@Ice1187/nthuoj-solution) //學長辛苦了！