C++ solution that beats 90.32% of the submission


  • 0
    D
    class Solution {
    public:
        bool go(vector<vector<char>>& board, vector<pair<int, int>>& q, int depth, bool row[][9], bool col[][9], bool sub[][9]) {
            if (q.size() == depth) return true;
            int i = q[depth].first, j = q[depth].second;
            int k = i/3*3+j/3;
            for (int v=0;v<9;v++) {
                if (row[i][v]||col[j][v]||sub[k][v]) continue;
                row[i][v]=col[j][v]=sub[k][v]=true;
                board[i][j] = '0'+v+1;
                if (go(board, q, depth+1, row, col, sub) ) {
                    return true;
                }    
                board[i][j] = '.';
                row[i][v]=col[j][v]=sub[k][v]=false;
            }
            return false;
        }
        void solveSudoku(vector<vector<char>>& board) {
            vector<pair<int, int>> q;
            bool row[9][9]={false}, col[9][9]={false}, sub[9][9]={false};
            for (int i=0;i<9;i++) {
                for (int j=0;j<9;j++) {
                    if (board[i][j] == '.') {
                        q.emplace_back(i, j);
                        continue;
                    }
                    int k = i/3*3+j/3;
                    int v = board[i][j] - '0' - 1;
                    row[i][v]=col[j][v]=sub[k][v]=true;
                }
            }
            go(board, q, 0, row, col, sub);
        }
    };
    

    Any comments are welcomed?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.