Leetcode Sudoku Solver problem solution YASH PAL, 31 July 2024 In this Leetcode Sudoku Solver problem solution, we need to write a program to solve a Sudoku puzzle by filling the empty cells.A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each of the digits 1-9 must occur exactly once in each column.Each of the digits 1-9 must occur exactly once in each of the 9 3×3 sub-boxes of the grid.The ‘.’ character indicates empty cells. 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; } coding problems solutions