Sharing my 56ms C++ solution


  • 0
    T
    class Solution {
    private:
        vector<vector<bool>> rows;
        vector<vector<bool>> cols;
        vector<vector<bool>> grid;
        
        bool isValidSudoku(vector<vector<char>>& board)
        {
            rows.resize(9);
            cols.resize(9);
            grid.resize(9);
            for(int k=0; k<9; k++)
            {
                rows[k].resize(9, false);
                cols[k].resize(9, false);
                grid[k].resize(9, false);
            }
            
            for(int i=0; i<9; i++)
                for(int j=0; j<9; j++)
                {
                    char c = board[i][j];
                    if(c != '.')
                    {
                        if(rows[i][c-'1']  || cols[j][c-'1'])
                            return false;
                        else
                        {
                            rows[i][c-'1'] = true;
                            cols[j][c-'1'] = true;
                        }
                        
                        int gridx = i/3;
                        int gridy = j/3;
                        int gridi = gridx*3+gridy;
                        if(grid[gridi][c-'1'])
                            return false;
                        else
                            grid[gridi][c-'1'] = true;;
                    }
                }
                
            return true;
        }
        
        void solveSudokuHelper(vector<vector<char>>& board, int pos, vector<vector<char>>& result)
        {
            int i, j;
            i = pos/9;
            j = pos%9;
            int gridx = i/3;
            int gridy = j/3;
            int gridi = gridx*3+gridy;
            
            if(pos == 81)
            {
                result = board;
                return;
            }
            
            char c = board[i][j];
            if(c == '.')
            {
                for(int k=0; k<9; k++)
                {
                    char temp = k+'1';
                    if(rows[i][k]==false && cols[j][k]==false && grid[gridi][k]==false)
                    {
                        rows[i][k] = true;
                        cols[j][k] = true;
                        grid[gridi][k] = true;
                        board[i][j] = temp;
                        solveSudokuHelper(board, pos+1, result);
                        rows[i][k] = false;
                        cols[j][k] = false;
                        grid[gridi][k] = false;
                        board[i][j] = c;
                    }
                }
            }
            else
                solveSudokuHelper(board, pos+1, result);
        }
    public:
        void solveSudoku(vector<vector<char>>& board) {
            if(!isValidSudoku(board))
                return;
            
            vector<vector<char>> result;
            solveSudokuHelper(board, 0, result);
            board = result;
        }
    };

  • 0
    P

    Great, If the vector is replaced with int[9][9], it will be faster. From my testing, it will be 4 ms.


  • 0
    T

    Yes, you are right. Now it's much faster. I appreciate your comments.


Log in to reply
 

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