Sudoku Solver 37 (LeetCode)

Question

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.

Solution

看到这道题应该就能想到是尝试在一个格子填可能的数，检查是否valid再递归填剩下的格子。因此自然想到用backtrack，其中check valid步骤和Valid Sudoku一样，这里不再赘述。

遍历Sudoku中的每一个格子，如果已经有数字就继续下一个，如果没有就在里面填数字i（1～9），检查填了之后是否valid并且递归寻找新board中（即填了i之后的board）剩余格子能否有可行解，如果两个条件都满足，则直接返回true表示这个格子填数字i有可行解，否则将该格子重置为'.'，并继续尝试下一个数字。

代码如下：

public class Solution {
    public void solveSudoku(char[][] board) {
        solve(board, 0, 0);
    }

    private boolean solve(char[][] board, int row, int col){
        if(col == board[0].length){
            row += 1;
            col = 0;
        }

        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] != '.'){
                    continue;
                }

                for(int k = 1; k <= 9; k++){
                    board[i][j] = (char) ('0' + k);
                    if(isValid(board, i, j) && solve(board, i, j + 1)){
                        return true;
                    }
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col){
        HashSet<Character> set = new HashSet<Character>();
        for(int i = 0; i < board.length; i++){
            if(set.contains(board[i][col])){
                return false;
            }
            if(board[i][col] != '.'){
                set.add(board[i][col]);
            }
        }

        set = new HashSet<Character>();
        for(int i = 0; i < board[0].length; i++){
            if(set.contains(board[row][i])){
                return false;
            }
            if(board[row][i] != '.'){
                set.add(board[row][i]);
            }
        }

        set = new HashSet<Character>();
        int r = (row / 3) * 3;
        int c = (col / 3) * 3;
        for(int i = r; i < r + 3; i++){
            for(int j = c; j < c + 3; j++){
                if(set.contains(board[i][j])){
                    return false;
                }
                if(board[i][j] != '.'){
                    set.add(board[i][j]);
                }
            }
        }

        return true;
    }
}