Sudoku Solver
Classic problem. At first we put all empty cells into a list, then we recursively test every possible
configuration of each empty cell to find a solution. The number of empty cells is at most 81. So there
won't be a StackOverflowError
.
public class SudokuSolver {
private boolean checkValid(char[][] board, int x, int y, int n) {
// check row
for (int i = 0; i < 9; i++) if ((board[x][i] - '0') == n) return false;
// check column
for (int i = 0; i < 9; i++) if ((board[i][y] - '0') == n) return false;
// check block
int l = (x / 3) * 3;
int t = (y / 3) * 3;
for (int i = l; i < l + 3; i++) {
for (int j = t; j < t + 3; j++) {
if ((board[i][j] - '0') == n) return false;
}
}
return true;
}
private boolean solveSudoku(char[][] board, List<Integer> xpos, List<Integer> ypos, int index) {
if (index >= xpos.size()) return true;
int x = xpos.get(index);
int y = ypos.get(index);
for (int i = 1; i <= 9; i++) {
if (checkValid(board, x, y, i)) {
board[x][y] = (char)('0' + i);
if (solveSudoku(board, xpos, ypos, index + 1)) return true;
board[x][y] = '.';
}
}
return false;
}
public void solveSudoku(char[][] board) {
ArrayList<Integer> xpos = new ArrayList<Integer>();
ArrayList<Integer> ypos = new ArrayList<Integer>();
for (int x = 0; x < 9; x++) {
for (int y = 0; y < 9; y++) {
if (board[x][y] == '.') {
xpos.add(x);
ypos.add(y);
}
}
}
solveSudoku(board, xpos, ypos, 0);
}
}