117. Sudoku Solver

public class Solution {
    public void solveSudoku(char[][] board) {
        ArrayList<Integer> empty = new ArrayList<Integer> ();

for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
if (board[i][j]=='.') empty.add(i*9+j);
}
}

int length = empty.size();

dfs(empty, board, 0, length);
}

public boolean dfs(ArrayList<Integer> empty, char[][] board, int cur, int length) {
if (cur==length) return true;

int index = empty.get(cur);
int row = index/9;
int col = index%9;

for (int v=1; v<=9; v++) {
if (isvalid(v, row, col, board)) {
board[row][col] = (char) (v+'0');
if (dfs(empty, board, cur+1, length)) return true;
board[row][col] = '.';
}
}
return false;
}

public boolean isvalid(int v, int row, int col, char[][] board) {
for (int i=0; i<9; i++) {
if (board[row][i]-'0'==v) return false;
if (board[i][col]-'0'==v) return false;
int row_s = 3*(row/3)+i/3;
int col_s = 3*(col/3)+i%3;
if (board[row_s][col_s]-'0'==v) return false;
}
return true;
}
}