37. 解数独

1. 步骤1 ：将所有的值保存到 列 行 3*3矩阵中
2. 步骤2 : 1~9 判断那个值可以选 可以选代入 然后回复现场

class Solution {
    boolean col[][];
    boolean row[][];
    boolean cell[][][];
    public void solveSudoku(char[][] board) {
        col = new boolean[9][9];
        row = new boolean[9][9];
        cell = new boolean[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j]!= '.') {
                    int t = board[i][j] - '0'-1;                            // 从 0开始数
                    col[j][t] = row[i][t] = cell[i / 3][j / 3][t] = true;
                }
            }
        }
        dfs(board , 0 ,0 );
    }
    private boolean dfs(char[][] board, int x, int y) {
        if(y == 9 ) {x++;  y = 0;}
        if(x == 9) return true;
        if(board[x][y] != '.') return dfs(board , x , y+1);
        for(int i = 0 ; i < 9 ;i++) {
            if(!col[y][i]&&!row[x][i]&&!cell[x/3][y/3][i]) {
                board[x][y] = (char) ('1'+ i);
                col[y][i] = row[x][i] = cell[x / 3][y / 3][i] = true;
                if(dfs(board, x , y+1)) return true;
                board[x][y] = '.';
                col[y][i] = row[x][i] = cell[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }   
}