This solution uses DFS (Depth First Search) Algorithm and looks for a unique solution to the given Sudoku Puzzle.
DFS Solution
class Solution {
public void solveSudoku(char[][] board) {
if (solve(board, 0, 0)) {
System.out.println("Solved");
}
}
public boolean solve(char[][] board, int row, int col) {
if (row > 8)
return true;
if (col > 8)
return solve(board, row + 1, 0);
if (board[row][col] != '.') {
return solve(board, row, col + 1);
} else {
for (int k = 1; k <= 9; k++) {
board[row][col] = (char)(k + '0');
if (isValid(board, row, col) && solve(board, row, col + 1)) {
return true;
} else
board[row][col] = '.';
}
}
return false;
}
public boolean isValid(char[][] board, int row, int col) {
for (int i = 0; i < 9; i++) {
if (i != col && board[row][i] == board[row][col])
return false;
}
for (int j = 0; j < 9; j++) {
if (j != row && board[j][col] == board[row][col])
return false;
}
int x = (row / 3) * 3;
int y = (col / 3) * 3;
for (int m = x; m < x + 3; m++) {
for (int n = y; n < y + 3; n++) {
if ((m != row || n != col) && board[m][n] == board[row][col])
return false;
}
}
return true;
}
}
Using HashSet
Instead of running valid() for all possible values, we can pre-compute and check if the current value is valid.
class Solution {
public void solveSudoku(char[][] board) {
if (solve(board, 0, 0)) {
System.out.println("Solved");
}
}
public boolean solve(char[][] board, int row, int col) {
if (row > 8)
return true;
if (col > 8)
return solve(board, row + 1, 0);
if (board[row][col] != '.') {
return solve(board, row, col + 1);
} else {
HashSet < Character > set = new HashSet < Character > ();
buildMaps(board, set, row, col);
for (int k = 1; k <= 9; k++) {
board[row][col] = (char)(k + '0');
if (!set.contains(board[row][col]) && solve(board, row, col + 1)) {
return true;
} else
board[row][col] = '.';
}
}
return false;
}
public void buildMaps(char[][] board, HashSet < Character > set, int row, int col) {
for (int i = 0; i < 9; i++) {
set.add(board[row][i]);
}
for (int j = 0; j < 9; j++) {
set.add(board[j][col]);
}
int x = (row / 3) * 3;
int y = (col / 3) * 3;
for (int m = x; m < x + 3; m++) {
for (int n = y; n < y + 3; n++) {
set.add(board[m][n]);
}
}
}
}
Another alternate solution would be to precompute these values into lists of Hashsets.