C++ solution using bit manipulation rather than hash tables. (92 percentile)


  • 0
    G
    class Solution {
    public:
    
        int Rows[9];
        int Cols[9];
        int Squares[9];
        
        bool Solve(vector<vector<char>> &b, int i, int j)
        {
            if(j == b[i].size())
            {
                i++;
                j = 0;
            }
            
            if(i == b.size())
            {
                return (true);
            }
            
            if(b[i][j] != '.')
            {
                return Solve(b,i,j + 1);
            }
            
            for(int n = 1; n <= 9; ++n)
            {
                if((Rows[i] & (1 << n)) != 0)
                {
                    continue;
                }
                
                if((Cols[j] & (1 << n)) != 0)
                {
                    continue;
                }
                
                if((Squares[(i/3)*3 + (j/3)] & (1 << n)) != 0)
                {
                    continue;
                }
                
                Rows[i] |= (1 << n);
                Cols[j] |= (1 << n);
                Squares[(i/3)*3 + (j/3)] |= (1 << n);
                b[i][j] = n + '0';
                
                if(Solve(b,i,j + 1))
                {
                    return (true);
                }
                
                b[i][j] = '.';
                Rows[i] &= ~(1 << n);
                Cols[j] &= ~(1 << n);
                Squares[(i/3)*3 + (j/3)] &= ~(1 << n);
            }
            
            return (false);
        }
    
        void solveSudoku(vector<vector<char>>& board) 
        {
            memset(Rows,0,sizeof(Rows));
            memset(Cols,0,sizeof(Cols));
            memset(Squares,0,sizeof(Squares));
            
            for(int i = 0; i < board.size(); ++i)
            {
                for(int j = 0;j < board[i].size(); ++j)
                {
                    if(board[i][j] != '.')
                    {
                        Rows[i] |= (1 << (board[i][j] - '0'));
                        Cols[j] |= (1 << (board[i][j] - '0'));
                        Squares[(i/3)*3 + (j/3)] |= (1 << (board[i][j] - '0'));
                    }
                }
            }
            
            Solve(board,0,0);
        }
    };

Log in to reply
 

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