Spread the love
Write a program to solve a Sudoku puzzle by filling the empty cells.
Java Solution
public void solveSudoku(char[][] board) {
helper(board);
}
private boolean helper(char[][] board){
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(board[i][j]!='.'){
continue;
}
for(char k='1'; k<='9'; k++){
board[i][j]=k;
if(isValid(board, i, j) && helper(board)){
return true;
}
board[i][j]='.';
}
return false;
}
}
return true; //return true if all cells are checked
}
private boolean isValid(char[][] board, int i, int j){
HashSet<Character> set = new HashSet<>();
for(int k=0; k<9; k++){
if(set.contains(board[i][k])){
return false;
}
if(board[i][k]!='.'){
set.add(board[i][k]);
}
}
set.clear();
for(int k=0; k<9; k++){
if(set.contains(board[k][j])){
return false;
}
if(board[k][j]!='.'){
set.add(board[k][j]);
}
}
set.clear();
int x=i/3 * 3;
int y=j/3 * 3;
for(int m=x; m<x+3; m++){
for(int n=y; n<y+3; n++){
if(set.contains(board[m][n])){
return false;
}
if(board[m][n]!='.'){
set.add(board[m][n]);
}
}
}
set.clear();
return true;
}
Improved Version
public void solveSudoku(char[][] board) {
helper(board);
}
private boolean helper(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
continue;
}
for (char k = '1'; k <= '9'; k++) {
if (isValid(board, i, j, k)) {
board[i][j] = k;
if (helper(board)) {
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true; //return true if all cells are checked
}
private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] != '.' && board[i][col] == c) {
return false;
}
if (board[row][i] != '.' && board[row][i] == c) {
return false;
}
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
&&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) {
return false;
}
}
return true;
}
The time complexity is O(9^m) where m represents the number of blanks to be filled. No extra space is needed.