37 Sudoku Solver

class Solution {
public:
    unordered_set<char> findCandidates(vector<vector<char>>& board, int i) {
        unordered_set<char> res;
        string s = "123456789";
        int i0 = i/9, j0 = i%9;
        for ( int ii = 0; ii < 9; ii++ ) res.insert(s[ii]);
        for ( int ii = 0; ii < 9; ii++ ) {
            if ( res.find(board[i0][ii]) != res.end() ) res.erase(res.find(board[i0][ii]));
            if ( res.find(board[ii][j0]) != res.end() ) res.erase(res.find(board[ii][j0]));
        }
        for ( int ii = 3*(i0/3); ii < 3*(i0/3+1); ii++ ) {
            for ( int jj = 3*(j0/3); jj < 3*(j0/3+1); jj++ ) {
                if ( res.find(board[ii][jj]) != res.end() ) res.erase(res.find(board[ii][jj]));
            }
        }
        return res;
    }
    bool solveHelper(vector<vector<char>>& board, int i) {
        if ( i == 81 ) return true;
        int i0 = i/9, j0 = i%9;
        if ( board[i0][j0] != '.' ) return solveHelper(board, i+1);
        unordered_set<char> candidates = findCandidates(board, i);
        for ( auto next: candidates) {
            board[i0][j0] = next;
            if ( solveHelper(board, i+1) ) return true;
        }
        board[i0][j0] = '.';
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        solveHelper(board, 0);
        return;
    }
};

Notes
这类题想想很简单，但经常不能bug-free。注意总结backtracking类问题的套路！多练习！