Straight forward, clean c++ solution using backtracking


  • 0
    O

    There are plenty of good solutions out there. Mine might not as fancy as others, but should be clean and straightforward

    void solveSudoku(vector<vector<char>>& board) 
    {
        if(board.empty() || board[0].empty()) 
            return;
        
        int rows = board.size();
        int cols = board[0].size();
        int boxSize = 3;
        solve(board, 0, 0, rows, cols, boxSize);
    }
    
    bool solve(vector<vector<char>>& board, int cy, int cx, int rows, int cols, int boxSize)
    {
        if(cy>=rows || cx>=cols)
            return true;
        
        // skipping the non empty cells
        if(board[cy][cx] != '.')
        {
            if(cx == cols-1)
                return solve(board, cy+1, 0, rows, cols, boxSize);
            else
                return solve(board, cy, cx+1, rows, cols, boxSize);
        }
        
        // trying different numbers
        for(int i='1'; i<='9'; i++)
        {
            bool b = false;
            char c = (char)i;
            if(placeAt(board, cy, cx, c, rows, cols, boxSize))
            {
                board[cy][cx] = c;
                if(cx == cols-1)
                    b = solve(board, cy+1, 0, rows, cols, boxSize);
                else
                    b = solve(board, cy, cx+1, rows, cols, boxSize);
                if(b)
                    return true;
                board[cy][cx] = '.';
            }
        }
        return false;
    }
    
    
    bool placeAt(vector<vector<char>>& board, int cy, int cx, char c, int rows, int cols, int boxSize)
    {
        // checking rows
        for(int x=0; x<cols; x++)
        {
            if(board[cy][x] == c)
                return false;
        }
        
        // checking columns
        for(int y=0; y<rows; y++)
        {
            if(board[y][cx] == c)
                return false;
        }
        
        // checking the box
        int startY = cy / boxSize;
        int startX = cx / boxSize;
        
        for(int y= startY*boxSize; y<(startY+1)*boxSize; y++)
        {
            for(int x= startX*boxSize; x<(startX+1)*boxSize; x++)
            {
                if(board[y][x] == c)
                    return false;
            }
        }
        return true;
    }

  • 0
    O

    Made some changes so that it uses bit masks

    vector<unsigned int> rMasks;    // for each col
    vector<unsigned int> cMasks;    // for each row
    vector<unsigned int> bMasks;    // for each boxes
    
    
    void solveSudoku(vector<vector<char>>& board) 
    {
        if(board.empty() || board[0].empty()) 
            return;
        
        rMasks.resize(9, 0);
        cMasks.resize(9, 0);
        bMasks.resize(9, 0);
        
        int rows = board.size();
        int cols = board[0].size();
        int boxSize = 3;
        
        for(int y=0; y<rows; y++)
        {
            for(int x=0; x<cols; x++)
            {
                char c = board[y][x];
                if(c != '.')
                {
                    int cnum = c-'0';
                    setMaskBit(rMasks, y, cnum);
                    setMaskBit(cMasks, x, cnum);
                    setMaskBit(bMasks, y, x, boxSize, cnum);
                }
            }
        }
        
        solve(board, 0, 0, rows, cols, boxSize);
    }
    
    
    bool solve(vector<vector<char>>& board, int cy, int cx, int rows, int cols, int boxSize)
    {
        if(cy>=rows || cx>=cols)
            return true;
        
        // skipping the non empty cells
        if(board[cy][cx] != '.')
        {
            if(cx == cols-1)
                return solve(board, cy+1, 0, rows, cols, boxSize);
            else
                return solve(board, cy, cx+1, rows, cols, boxSize);
        }
        
        // trying different numbers
        for(int i='1'; i<='9'; i++)
        {
            bool b = false;
            char c = (char)i;
            int cnum = c-'0';
            if(placeAt(board, cy, cx, c, rows, cols, boxSize))
            {
                board[cy][cx] = c;
                setMaskBit(rMasks, cy, cnum);
                setMaskBit(cMasks, cx, cnum);
                setMaskBit(bMasks, cy, cx, boxSize, cnum);
                
                if(cx == cols-1)
                    b = solve(board, cy+1, 0, rows, cols, boxSize);
                else
                    b = solve(board, cy, cx+1, rows, cols, boxSize);
                if(b)
                    return true;
                    
                board[cy][cx] = '.';
                clearMaskBit(rMasks, cy, cnum);
                clearMaskBit(cMasks, cx, cnum);
                clearMaskBit(bMasks, cy, cx, boxSize, cnum);
            }
        }
        return false;
    }
    
    
    bool placeAt(vector<vector<char>>& board, int cy, int cx, char c, int rows, int cols, int boxSize)
    {
        int cnum = c-'0';
        
        // checking rows
        if((rMasks[cy] >> cnum) & 1)
            return false;
        
        // checking cols
        if((cMasks[cx] >> cnum) & 1)
            return false;
    
        // checking the box
        int idx = computeBMaskIndex(cy, cx, boxSize);
        if((bMasks[idx] >> cnum) & 1)
            return false;
    
        return true;
    }
    
    
    void setMaskBit(vector<unsigned int> & mask, int index, int bit)
    {
        mask[index] |= (1<<bit);
    }
    
    void setMaskBit(vector<unsigned int> & mask, int y, int x, int bs, int bit)
    {
        setMaskBit(mask, computeBMaskIndex(y, x, bs), bit);
    }
    
    void clearMaskBit(vector<unsigned int> & mask, int index, int bit)
    {
        mask[index] &= ~(1<<bit);   
    }
    
    void clearMaskBit(vector<unsigned int> & mask, int y, int x, int bs, int bit)
    {
        clearMaskBit(mask, computeBMaskIndex(y,x,bs), bit);
    }
    
    int computeBMaskIndex(int cy, int cx, int boxSize)
    {
        int by = cy/boxSize;
        int bx = cx/boxSize;
        return by + bx * boxSize;
    }

Log in to reply
 

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