---
# System prepended metadata

title: 13333 - Stewie vs Brian

---

# 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)
//學長辛苦了！
