https://leetcode-cn.com/problems/sudoku-solver/

难度困难936收藏分享切换为英文接收动态反馈

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字或者 '.'
• 题目数据 保证 输入数独仅有一个解

通过次数97,696提交次数145,663

class Solution {
    int [][] line = new int[9][9];
    int [][] column = new int[9][9];
    int [][][] block = new int[3][3][9];
    boolean valid = false;
    List<int[]> blank = new ArrayList<int[]>();
    public void solveSudoku(char[][] board) {

        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]=='.')
                {
                    blank.add(new int[]{i,j});
                }
                else
                {
                    int x = board[i][j]-'0'-1;
                    line[i][x] = column[j][x] = block[i/3][j/3][x]=1;
                }
            }
        }
        dfs(board, 0);
    }

    void dfs(char[][] board,int index)
    {
        if(index == blank.size())
        {
            valid = true;
            return; 
        }

        int[] blank_ = blank.get(index);
        int i = blank_[0];
        int j = blank_[1];
        for(int d =0 ;d < 9 && !valid;++d)
        {
            if(line[i][d]!=1 && column[j][d]!=1 && block[i/3][j/3][d]!=1)
            {
                line[i][d] = column[j][d] = block[i/3][j/3][d] = 1;
                board[i][j] = (char)(d+'0'+1);
                dfs(board,index+1);
                line[i][d] = column[j][d] = block[i/3][j/3][d] = 0;
            }
        }
    }
}