[LeetCode] Sudoku Solver

這題大概半年前有看過

前女友家教學生的題目，她是一個蠻聰明的人，印象那時候她好像不久就看出解法惹，我卻還沒甚麼想法。

阿不過這是題外話了，這題是個DFS跟我們寫數獨時的行為蠻相似的，我們會一直在往下寫，一旦發現寫錯就會回到上一格、上上格、甚至整張重寫XD。

這個行為跟DFS蠻像的，一直往下走、發現走到leaf發現不合法就回頭找其他路、直到找到正確的path。

(只是電腦比較笨，不會觀察格子之間的關係，只能簡單判斷數字田在這個格字是不是合法的)

所以一樣，就用這個概念 從(0,0)的位置從1開始猜，然後去猜(0,1)，如果發現(0,1) 1~9都不能填，那就是上一格填錯了，那就回到(0,0)然後猜2、以此類推，直到猜完(8,8)

bool DFS(vector<vector<char>>& board, int i, int j)
    {
        if(i == 9) //done
            return true;            
        if(j == 9) 
            return DFS(board, i+1, 0);
        if(board[i][j] != '.') 
            return DFS(board, i, j+1);
        
        //guess
        for(char c = '1' ; c <= '9' ; c++)
        {
            
            //check the value is legal?
            int ro = i/3 , col = j/3;
            bool flag = false;

            for(int k = 0 ; k < 9 ; k++)
            {
                if(c == board[i][k] || c == board[k][j] || c == board[ro*3+k/3][col*3+k%3])
                {
                    flag = true;
                    break;
                }
            }
            
            if(flag == true)
                continue;
            else
            {
                board[i][j] = c;
                    
                if(DFS(board,i,j+1))
                    return true;
                
                board[i][j] = '.';
            }            
        }
        
        //all numbers are illegal, so go back last point 
        return false;
    }

這個syntax highlight theme好像好一點，但是還是找不到VSCode的theme QQ