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 3x3 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;
}
0 Comments