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;
    
    
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment