Sudoko Solver Problem Solution

Sudoko Solver Problem: Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Sudoko Solver Problem Solution

Problem Solution In Python

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        for i in range(9):
            for j in range(9):
                if(board[i][j] == "."):
                    board[i][j] = 0
        self.solve(board,0,0)
        
    def validation(self,board,row,col,number):
        for i in range(9):
            if(int(board[row][i]) == number):
                return False
        for j in range(9):
            if(int(board[j][col]) == number):
                return False
        grid_row = row - row % 3
        grid_col = col - col % 3
        for i in range(3):
            for j in range(3):
                if(int(board[grid_row + i][grid_col + j]) == number):
                    return False
        return True
        
    def solve(self,board,row,col):
        if(col == 9):
            if(row == 8):
                return True
            row += 1
            col = 0

        if(int(board[row][col]) > 0):
            return self.solve(board,row,col+1)

        for num in range(1,10):
            if(self.validation(board,row,col,num)):
                board[row][col] = str(num)
                if(self.solve(board,row,col+1)):
                    return True
            board[row][col] = 0  
        return False

Problem Solution In Java

class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][][] square = new boolean[3][3][10];
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                if(board[i][j] == '.') continue;
                int v = board[i][j] - '0';
                row[i][v] = true;
                col[j][v] = true;
                square[i/3][j/3][v] = true;
            }
        }
        solve(board,0,row,col,square);
    }
    public boolean solve(char[][] board,int index,boolean[][] row,boolean[][] col,boolean[][][] square) {
        if(index > 80) return true;
        int i = index/9, j = index%9;
        if(board[i][j] != '.') {
            return solve(board,index+1,row,col,square);
        }
        for(int v=1;v<=9;v++) {
            if(row[i][v] || col[j][v] || square[i/3][j/3][v]) continue;
            row[i][v] = true;
            col[j][v] = true;
            square[i/3][j/3][v] = true;
            board[i][j] = (char) (v + '0');
            if(solve(board,index+1,row,col,square)) return true;
            row[i][v] = false;
            col[j][v] = false;
            square[i/3][j/3][v] = false;
            board[i][j] = '.';
        }
        return false;
    }
}

Problem Solution In C++

class Solution {
    inline int getBox(int i, int j) {
        return i / 3 * 3 + j / 3;
    }
    inline bool contains(int bitset, int bit) {
        return bitset & (1 << bit);
    }
    inline void setBit(int& bitset, int bit) {
        bitset |= (1 << bit); 
    }
    inline void removeBit(int& bitset, int bit) {
        bitset &= ~(1 << bit);
    }
    bool backtrack(vector<vector<char>>& board, int v, vector<int>& row, vector<int>& col, vector<int>& box) {
        if (v > 80) return true;
        
        int i = v / 9, j = v % 9;
        if (board[i][j] != '.') return backtrack(board, v + 1, row, col, box);
        
        for (int num = 1; num <= 9; ++num) {
            if (!contains(row[i], num) && !contains(col[j], num) && !contains(box[getBox(i, j)], num)) {
                setBit(row[i], num);
                setBit(col[j], num);
                setBit(box[getBox(i, j)], num);
                board[i][j] = num + '0';
                
                if (backtrack(board, v + 1, row, col, box)) return true;
                
                removeBit(row[i], num);
                removeBit(col[j], num);
                removeBit(box[getBox(i, j)], num);
                board[i][j] = '.';
            }
        }
        
        return false;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<int> row(9, 0), col(9, 0), box(9, 0);
        
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    setBit(row[i], board[i][j] - '0');
                    setBit(col[j], board[i][j] - '0');
                    setBit(box[getBox(i, j)], board[i][j] - '0');
                }
            }
        }
        
        backtrack(board, 0, row, col, box);
    }
};

Problem Solution In C

int brutal_solve(char** board, int pos){
    int i, j, ris = 0, k, flag = 1;
    while(pos <81 && board[pos/9][pos%9]!='.')  pos++;
    if(pos>=81){
        ris = 1;
        return ris;
    }

    for(k=1; k<=9; k++){
        flag = 1;
        for(i=0; i<9;i++){
            if(board[pos/9][i]==(k+'0')) flag = 0;
            if(board[i][pos%9]==(k+'0')) flag = 0;
        }
        for(i=(pos/9)-((pos/9)%3); i<(pos/9)-((pos/9)%3)+3; i++)
            for(j=(pos%9)-((pos%9)%3); j<(pos%9)-((pos%9)%3)+3; j++)
                if(board[i][j]==k +'0') flag = 0;
        if(flag){
            board[pos/9][pos%9] = k+'0';
            ris = brutal_solve(board, pos +1);
            if(ris==0)
                board[pos/9][pos%9] = '.';
            else
                return ris;

        }
    }
    return ris;
}


void updateExclusion(int exclusion[9][9][9], int i, int j, int value){
    int r, c, k, m, n;
    for(k=0;k<9;k++){
        exclusion[i][j][k]=0;
        exclusion[k][j][value]=0;
        exclusion[i][k][value]=0;
    }
    r = (i/3)*3;
    c = (j/3)*3;
    for(m=0; m<3; m++, r++)
        for(n=0; n<3; n++)
            exclusion[r][c+n][value]=0;
    return;
}

void solveSudoku(char** board, int boardSize, int* boardColSize){

    int exclusion[9][9][9], flag=1;
    int i, j, k, r, c, value, iter1, iter2, squareR, squareC, squareRlim, squareClim;
    int rToAdd, cToAdd;
    for(i=0;i<9;i++)
        for(j=0;j<9;j++)
            for(k=0;k<9;k++)
                exclusion[i][j][k]=1;
   
        for(i=0;i<9;i++)
            for(j=0;j<9;j++)
                if(board[i][j]!='.'){
                    value = board[i][j] - 1 - '0';
                    updateExclusion(exclusion, i, j, value);
                }
      /*this flag will be used for checking if a new value has been inserted in the Sudoku scheme*/
    while(flag){
        flag = 0;
        for(iter1=0;iter1<9;iter1++){
            for(squareR=0;squareR<3;squareR++){
                for(squareC=0;squareC<3;squareC++){
                    value =0;
                    squareRlim = squareR*3;
                    squareClim = squareC*3;
                    for(r=squareRlim;r<squareRlim+3&&flag==0;r++){
                        for(c=squareClim;c<squareClim+3&&flag==0;c++){
                            if(exclusion[r][c][iter1]!=0){
                                rToAdd=r;
                                cToAdd=c;
                                
                            }
                            value += exclusion[r][c][iter1];
                        }
                    }
                    if(value == 1){
                        board[rToAdd][cToAdd] = iter1+1+'0';
                        flag++;
                        updateExclusion(exclusion, rToAdd, cToAdd, iter1);
                    }
                }
            }
            for(r=0;r<9;r++){
                value = 0;
                for(c=0;c<9;c++){
                    if(exclusion[r][c][iter1]!=0)
                        cToAdd=c;
                    value += exclusion[r][c][iter1];
                }
                if(value == 1){
                    board[r][cToAdd] = iter1+1 +'0';
                    flag++;
                    updateExclusion(exclusion, r, cToAdd, iter1);
                }
            }

            for(c=0;c<9;c++){
                value = 0;
                for(r=0;r<9;r++){
                    if(exclusion[r][c][iter1]!=0)
                        rToAdd=r;
                    value += exclusion[r][c][iter1];
                }
                if(value == 1){
                    board[rToAdd][c] = iter1+1 + '0';
                    flag++;
                    updateExclusion(exclusion, rToAdd, c, iter1);
                }
            }
        }
    }
    brutal_solve(board, 0);
    return;
    
    
}