Sodoku Solver

Question

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.

Analysis

My approach is to do Set Union operation to find all the possible numbers that each empty cell in the soduku can be applied. Then backtracking all the cells to find the unique answer.

Solution

 public void solveSudoku(char[][] board) {
        if(board==null || !(board.length==9&&board[0].length==9)) return;
        boolean[][][] sub=new boolean[3][3][9];
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
            Arrays.fill(sub[i][j],true);
        boolean[][] row=new boolean[9][9];
        for(int i=0;i<9;i++) Arrays.fill(row[i],true);
        boolean[][] col=new boolean[9][9];
        for(int i=0;i<9;i++) Arrays.fill(col[i],true);

        List<int[]> list=new LinkedList<int[]>();
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j]!='.'){
                    sub[i/3][j/3][board[i][j]-'1']=false;
                    row[i][board[i][j]-'1']=false;
                    col[j][board[i][j]-'1']=false;
                }else{
                    list.add(new int[]{i,j});
                }
            }
        }
        List<Integer> answer=new ArrayList<>();
        solve(list,sub,row,col,0,answer);
        for(int i=0;i<list.size();i++){
            int[] tmp=list.get(i);
            board[tmp[0]][tmp[1]]=(char)(answer.get(i)+'1');
        }
        return;
    }

    public boolean solve(List<int[]> list, boolean[][][] sub, boolean[][] row, boolean[][] col, int index, List<Integer> answer){
        if(index==list.size()) return true;
        int i=list.get(index)[0], j=list.get(index)[1];
        List<Integer> pot=getPot(sub[i/3][j/3],row[i],col[j]);
        if(pot.size()==0) return false;
        boolean flag=false;
        for(int a : pot){
            sub[i/3][j/3][a]=false;
            row[i][a]=false;
            col[j][a]=false;
            if(solve(list,sub,row,col,index+1,answer)){
                answer.add(0,a);
                flag=true;
                break;
            }
            sub[i/3][j/3][a]=true;
            row[i][a]=true;
            col[j][a]=true;
        }
        return flag;
    }

    public List<Integer> getPot(boolean[] a, boolean[] b, boolean[] c){
        List<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<9;i++){
            if(a[i]&&b[i]&&c[i]) list.add(i);
        }
        return list;
    }