37. Sudoku Solver
class Solution {
public void solveSudoku(char[][] board) {
backTrack(board,0);
}
// return boolean to 1. reduce time complexity
// 2.to make backtrack not revert the value in board
private boolean backTrack(char[][] board, int i){
if(i==81) return true;
int row = i/9;
int col= i%9;
if(board[row][col]!='.') return backTrack(board, i+1);
for(char ch='1'; ch<='9'; ch++){
if(!isValid(row, col, ch, board)) continue;
board[row][col]=ch;
if(backTrack(board, i+1)){
return true;
}
board[row][col]='.';
}
return false;
}
private boolean isValid(int i, int j, char ch, char[][] board){
//check the 3*3 subbox
for(int row=i/3*3; row<(i/3+1)*3; row++){
for(int col=j/3*3; col<(j/3+1)*3; col++){
if(ch==board[row][col]){
return false;
}
}
}
//check the row
for(int col=0; col<board[0].length; col++){
if(ch==board[i][col]) return false;
}
//check the column
for(int row=0; row<board.length; row++){
if(ch==board[row][j]) return false;
}
return true;
}
}
Last updated
Was this helpful?