Sudoku Solver

/*
这道题的方法就是用在N-Queens中介绍的常见套路。简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，然后判合法，如果成立就递归继续，结束后把数字设回空。大家可以看出代码结构和N-Queens是完全一样的。判合法可以用Valid Sudoku做为subroutine，但是其实在这里因为每次进入时已经保证之前的board不会冲突，所以不需要判断整个盘，只需要看当前加入的数字和之前是否冲突就可以，这样可以大大提高运行效率，毕竟判合法在程序中被多次调用。
*/
public class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length != 9 || board[0].length != 9)
        return;
        helper(board, 0, 0);
    }
    public boolean helper(char[][] board, int i, int j){
        if(j >= 9){//一行已经遍历完了,换一下行
            return helper(board, i + 1, 0);
        }
        if(i == 9)//last row
        return true;
        if(board[i][j] == '.'){
            for(int k = 1; k <= 9; k++){//从1-9挨个试
                board[i][j] = (char)(k + '0');
                if(isValid(board, i , j)){
                    if(helper(board, i, j + 1)){//递归到下一格,下一个再递归到下一格直到最后都成立
                        return true;
                    }
                }
                board[i][j] = '.';//归位
            }
        }
        else{
            return helper(board, i, j + 1);
        }
        return false;
    }
    public boolean isValid(char[][] board, int i, int j){
        for(int row = 0; row < 9; row++){//check column
            if(row != i && board[row][j] == board[i][j])
            return false;
        }
        for(int col = 0; col < 9; col++){//check row
            if(col != j && board[i][col] == board[i][j])
            return false;
        }
        for(int row = i / 3 * 3; row < i / 3 * 3 + 3; row++){
            for(int col = j / 3 * 3; col < j / 3 * 3 + 3; col++){
                if((row != i && col != j) && (board[row][col] == board[i][j]))
                return false;
            }
        }
        return true;
    }
}