37. Sudoku Solver

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.

 完成数独游戏，目前空的小方格被标记为'.'。

数独游戏规则：规则以及区块的定义在上一个题目Valid Sudoku中介绍过（行、列、区块中每个数字只用一次，均不能重复）。

在LeetCode官网本道题的Dission区有很多好的巧妙的解决方达。我看了一下，懒一点就选了一个最好理解的.....

　　　　

JAVA解决方法：对每个要填的空从‘1’试到‘9’，时间复杂度是 9 ^ n（n是要填的空有几个）。

public class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0)
            return;
        solve(board);
    }
    
    public boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '.'){
                    for(char c = '1'; c <= '9'; c++){  //一个个尝试，从‘1’试到‘9’
                        if(isValid(board, i, j, c)){  //isValid函数先判断这个数字是否重复
                            board[i][j] = c;           //把数字填入
                            
                            if(solve(board))          //如果填的这个数以至于之后可以完成数独，等继续完成之后，就返回true
                                return true;          
                            else  //如果填的这个数字，导致之后无法完成整个数独，就把这个空重新置为空（说明填上c这个数字不合适），之后尝试其他数字
                                board[i][j] = '.';    
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char c){   //判断c是否在当前行、列、区块已经存在
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; //判断列
            if(board[row][i] != '.' && board[row][i] == c) return false; //判断行
            if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' && 
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //判断当前区块3*3的九个位置
        }
        return true;
    }
}

至于区块为什么这么来算？

board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' 

之后再更新。。。