class Solution {

    public void solveSudoku(char[][] board) {

        helper(board,0,0);

    }

    //判断row,col位置是否为'.'，是的话就设置值。

    //因为要判断是否正确，所以需要返回值

    public boolean helper(char[][] board,int row,int col){

        if(col>=9){  //下一个位置超出列，就是进行下一行

           return helper(board,row+1,0);

        }

        if(row==9){

            return true;

        }

        //如果该位置是'.'，则要添加数字

        if(board[row][col]=='.'){

            //依次给该位置添加1-9

            for(int k=1;k<=9;k++){

                board[row][col]=(char)(k+'0');

                if(isValid(board,row,col)){//如果有效，就进行下一个位置添加

                    if(helper(board,row,col+1))//如果后面的添加返回true,表明添加成功，返回true，否则就尝试下一个k

                        return true;

                }

                board[row][col]='.';

            }

        }else{

           return helper(board,row,col+1);

        }

        return false;

    }

    /*

    前面都已经判断了，只要判断该位置添加数字后是否符合要求，也就是看该行、列有没有和该元素相同的，而且该位置所在的九宫格中也不能有和它相同的

    */

    public boolean isValid(char[][] board,int row,int col){

        //判断列是否有相同的，再同列不同行，元素却相同

        for(int i=0;i<9;i++){

            if(i!=row&&board[i][col]==board[row][col])

                return false;

        }

        //判断行是否有相同的，同行不同列

        for(int j=0;j<9;j++){

            if(j!=col&&board[row][col]==board[row][j])

                return false;

        }

        //判断该位置所在九宫格是否有相同的

        /*要根据该位置找到所在九宫格的行和列的范围

        每个九宫格的行的范围是0-2,3-5,6-8,

        */

        for(int i=row/3*3;i<row/3*3+3;i++)

        {

            for(int j=col/3*3;j<col/3*3+3;j++){

                if((i!=row||j!=col)&&board[i][j]==board[row][col])

                    return false;

            }

        }

        return true;

    }

}