37. 解数独

╰半夏微凉° 2022-09-10 11:28 194阅读 0赞

[https://leetcode-cn.com/problems/sudoku-solver/][https_leetcode-cn.com_problems_sudoku-solver]

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

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

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

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

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

**示例：**

![1377561680611c155bece0f170ae6b30.png][]

输入：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"]]
    解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

![c5f4f3622a0a6ba18860f5a4964ed286.png][]

**提示：**

*  `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;
                }
            }
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_sudoku-solver]: https://leetcode-cn.com/problems/sudoku-solver/
[1377561680611c155bece0f170ae6b30.png]: /images/20220829/7b096b23aece4081bdc7391d734ab21b.png
[c5f4f3622a0a6ba18860f5a4964ed286.png]: /images/20220829/74bb6d0961ae4b1183a1d25dda75ab29.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/106736d59c0e47faa3b07b1460cab8e8.png