[LeetCode] Sudoku Solver

Problem:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Solution: O(n^3)

public class Solution {
    public void solveSudoku(char[][] board) {
        ArrayList<Integer> arr= getEmptyList(board);
        DFS(board,arr,0);
    }

    public ArrayList<Integer> getEmptyList(char [][]board){
        ArrayList<Integer> arr= new ArrayList<Integer>();
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] == '.'){
                    arr.add(i*9+j);
                }
            }
        }
        return arr;
    }

    public boolean DFS(char[][]board,ArrayList<Integer> arr,int index){
        if(index == arr.size())
            return true;
        
        int data = arr.get(index);
        int row = data/9;
        int column = data%9;
        for(int i = 1;i <= 9;i++){
            if(isValid(board, row, column, i)){
                board[row][column]= (char)('0' + i);
            if(DFS(board, arr, index+1))
                return true;
            board[row][column]='.';
            }
        }
        return false;
    }

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

Key concept: Apply DFS to do all possible solution