C++ Backtracking Modular Solution: (Understand in 30seconds)


#1
bool isEmpty(vector<vector<char>>A, int& x, int& y){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            if(A[i][j]=='.'){
                x = i;
                y = j;
                return true;
            }
    return false;
}

bool isValidRow(vector<vector<char>>&A, int x, char num){
    for(int i=0;i<9;i++)
        if(A[x][i]==num)
            return false;
    return true;
}

bool isValidCol(vector<vector<char>>&A, int y, char num){
    for(int i=0;i<9;i++)
        if(A[i][y]==num)
            return false;
    return true;
}

bool isValidSquare(vector<vector<char>>&A, int x, int y, char num){
    int row = x/3;
    int col = y/3;
    
    for(int i=3*row;i<3*row+3;i++)
        for(int j=3*col;j<3*col+3;j++)
            if(A[i][j]==num)
                return false;
    return true;
}

bool isValid(vector<vector<char>>&A, int x, int y, char num){
    if(isValidRow(A, x, num) and isValidCol(A, y, num) and isValidSquare(A, x, y, num))
        return true;
    return false;
}

bool solve(vector<vector<char>>& A){
    int x,y;
    if(!isEmpty(A, x, y))
        return true;
    
    for(int i=1;i<=9;i++){
        char num = (i+'0');
        if(isValid(A, x, y, num)){
            A[x][y] = num;
            if(solve(A))
                return true;
            A[x][y] = '.';
        }
    }
    return false;
}

void Solution::solveSudoku(vector<vector<char> > &A) {
   solve(A);
}