# 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] == '.') {