37. Sudoku Solver

一、题目

　　1、审题

　　 2、分析

　　　　将所给的数独棋盘补充完整。

二、解答

　　1、思路：

　　　　利用上一题的判断数独是否正确。依次在数独棋盘中的空位补充‘1’ -‘9’，递归判断是否符合，若符合则继续下一个空位；若不符合，则空位还原。

　　

public class Solution {
    public void solveSudoku(char[][] board) {
        helper(board);
    }
    
    private boolean helper(char[][] board) {

        for(int row = 0; row < 9; row++) {
            for(int col = 0; col < 9; col++) {
                if(board[row][col] == '.') {
                    for(char i = '1'; i <= '9'; i++) {
                        board[row][col] = i;
                        if(isValidSudoku(board) && helper(board))
                            return true;
                        // 还原
                        board[row][col] = '.';
                    }
                    return false;
                }
            }
        }
        return true;
    }

    public boolean isValidSudoku(char[][] board) {
        
        for(int i = 0; i < 9; i++) {
            HashSet<Character> row = new HashSet<Character>();
            HashSet<Character> column = new HashSet<Character>();
            HashSet<Character> cube = new HashSet<Character>();
            
            for(int j = 0; j < 9; j++) {
                
                if(board[i][j] != '.' && !row.add(board[i][j])) 
                    return false;
                
                if(board[j][i] != '.' && !column.add(board[j][i]))
                    return false;
                
                int rowNum = i / 3 * 3 + j / 3;
                int columnNum = i % 3 * 3 + j % 3;
                if(board[rowNum][columnNum] != '.' && !cube.add(board[rowNum][columnNum]))
                    return false;
            }
        }
        
        return true;
    }
}