37. 解数独 (opens new window)

1.回溯

枚举每个空白位置可填写的数字，

• flag控制当前是否找到解：如果已经找到解，那么父节点不需要对原棋盘位置进行回溯复原。
• 保证每个dfs只对一个空格子位置进行枚举与回溯。因此空格子枚举完九个可能的数之后需要return返回。

class Solution {
    Set<Integer>[] rowSet=new Set[9];
    Set<Integer>[] lineSet=new Set[9];
    Set<Integer>[][] square=new Set[3][3];

    boolean flag=false;
    public void solveSudoku(char[][] board) {
        Arrays.setAll(rowSet,e->new HashSet<>());
        Arrays.setAll(lineSet,e->new HashSet<>());
        for(int i=0;i<3;i++) Arrays.setAll(square[i],e->new HashSet<>());
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]!='.'){
                    square[i / 3][j / 3].add(board[i][j] - '0');
                    rowSet[i].add(board[i][j]-'0');
                    lineSet[j].add(board[i][j]-'0');
                }
            }
        }
        dfs(board);
    }
    public void dfs(char[][] board){
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]=='.'){
                    for(int k=1;k<=9;k++){
                        if(!rowSet[i].contains(k)&&!lineSet[j].contains(k)&&!square[i / 3][j / 3].contains(k)&&!flag){
                            board[i][j]=String.valueOf(k).charAt(0);
                            square[i / 3][j / 3].add(board[i][j] - '0');
                            rowSet[i].add(board[i][j]-'0');
                            lineSet[j].add(board[i][j]-'0');
                            dfs(board);
                            //回溯
                            if(!flag){
                                rowSet[i].remove(board[i][j]-'0');
                                lineSet[j].remove(board[i][j]-'0');
                                square[i / 3][j / 3].remove(board[i][j] - '0');
                                board[i][j] = '.';
                            }
                            //子搜索树已经找到答案，无需再回溯与变更原数组
                            else return;
                        }
                    }
                    //控制每次dfs搜索只负责一个空白格位置的填写
                    return;
                }
            }
        }
        flag=true;
    }
}

2.位哈希

使用一个二进制比特串001100001记录每一行/列的出现情况。