Sudoku solver with two scans


  • 0
    R

    class Solution {
    public:
    void solveSudoku(vector<vector<char>>& board) {

        vector<pair<int,int>> positions;
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j]=='.')
                {
                    positions.push_back(make_pair(i, j));
                }
            }
        }
        int num = positions.size();
        vector<bool>visited(num, false);
        
        bool flag = recursive(board, positions, visited, 0);
    }
    
    bool recursive(vector<vector<char> > &board, vector<pair<int, int> > &positions, vector<bool> &visited, int idx)
    {
        
        int num = positions.size();
        if(idx==num) return true; //exceed the number
        
        int i = positions[idx].first;
        int j = positions[idx].second;
       
        for(int k=1; k<=9; k++)
        {
            
            board[i][j] = k+'0';
            if(valid(board, i, j) && recursive(board, positions, visited, idx+1))
                return true;
            board[i][j] = '.';   //backtrack
        }
        return false;
    }
    
    bool valid(vector<vector<char> > &board, int irow, int icol)
    {
        int val = board[irow][icol];
        for(int i=0; i<9; i++)
        {
            if(board[i][icol]==val&& i!=irow) return false;
        }
        for(int j=0; j<9; j++)
        {
            if(board[irow][j]==val&& j!=icol) return false;
        }
        
        int rs = (irow/3)*3;
        int cs = (icol/3)*3;
        for(int i=rs; i<rs+3; i++)
        {
            for(int j=cs; j<cs+3; j++)
            {
                if(board[i][j]==val&&i!=irow&&j!=icol)
                    return false;
            }
        }
        return true;
    }
    

    };


Log in to reply
 

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