37. Sudoku Solver

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool isValid(vector<vector<char>>& board, int r, int c, char ch ){
        
        for(int i=0;i<9;++i){
            if(board[r][i] == ch) return false;
            if(board[i][c] == ch) return false;
            if(board[(r/3)*3+i/3][(c/3)*3 +i%3] == ch ) return false;
        }
        return true;
    }
    bool traverse(vector<vector<char>> & board, int r, int c){
        
        if(c==9) return traverse(board, r+1,0);
        if(r==9) return true;
        
        
        
        if(board[r][c]!='.') return traverse(board, r, c+1);
        
        for(char ch='1'; ch<='9' ;++ch){
            if(!isValid(board, r, c, ch)) continue;
            board[r][c] = ch;
            if(traverse(board, r, c+1)) return true;
            board[r][c] ='.';
        }
        return false;
        
    }
    void solveSudoku(vector<vector<char>>& board) {
        if (traverse(board, 0, 0))
            return;
    }
};

analysis

  • time complexity O(9^nm)
  • sparse complexity O(nm)