sudoku ms interview

sudoku.java

import java.util.ArrayList;

public class sudoku {
    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 len = empty.size();
        dfs(board, 0, len, empty);
    }
    public boolean dfs(char[][] board, int cur, int len,  ArrayList<Integer> empty) {
        if(cur == len)
            return true;
        int index = empty.get(cur);
        int row = index / 9;
        int col = index % 9;
        for(int v = 1; v <= 9; v++) {
            if(isValid(board, v, row, col)){
                board[row][col] = (char)(v+'0');
                if(dfs(board, cur+1, len, empty))
                    return true;
                board[row][col] = '.';
            }
        }
        return false;
    }
    public boolean isValid(char[][]board, int v, int row, int col) {
        for(int i = 0 ; i < 9 ; i++) {
            if(board[row][i] == v+'0')
                return false;
            if(board[i][col] == v+'0')
                return false;
            int rows = 3*(row/3) + (i/3);
            int cols = 3*(col/3) + (i%3);
            if(board[rows][cols] == v+'0')
                return false;
        }
        return true;
    }
}