Leetcode算法Java全解答--37. 解数独

亦凉 2022-04-13 10:05 189阅读 0赞

# Leetcode算法Java全解答–37. 解数独 #

### 文章目录 ###

*  Leetcode算法Java全解答--37. 解数独
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

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

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

数字 1-9 在每一行只能出现一次。  
数字 1-9 在每一列只能出现一次。  
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。  
空白格用 ‘.’ 表示。

一个数独。

答案被标成红色  
。Note:

给定的数独序列只包含数字 1-9 和字符 ‘.’ 。  
你可以假设给定的数独只有唯一解。  
给定数独永远是 9x9 形式的。

## 想法 ##

// TODO

## 结果 ##

// TODO

## 总结 ##

// TODO

## 代码 ##

### 我的答案 ###

### 大佬们的答案 ###

private int which(int i, int j) {
            if (i <= 2) {
                if (j <= 2)
                    return 1;
                if (j <= 5)
                    return 2;
                return 3;
            }
            if (i <= 5) {
                if (j <= 2)
                    return 4;
                if (j <= 5)
                    return 5;
                return 6;
            }
            if (j <= 2)
                return 7;
            if (j <= 5)
                return 8;
            return 9;
        }
    
        public void solveSudoku(char[][] board) {
            int[][] k = new int[10][10];
            // heng
            int[][] p = new int[10][10];
            // shu
            int[][] q = new int[10][10];
    
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.') {
                        p[i][board[i][j] - '0'] = 1;
                        q[j][board[i][j] - '0'] = 1;
                        k[which(i, j)][board[i][j] - '0'] = 1;
                    }
                }
            }
    
            dfs(k, p, q, board, 0, 0);
        }
    
        private boolean dfs(int[][] k, int[][] p, int[][] q, char[][] board, int i, int j) {
            if (j == 9) return true;
            if (board[i][j] != '.') {
                if (i + 1 < 9) {
                    boolean rst = dfs(k, p, q, board, i + 1, j);
                    if (rst) {
                        return true;
                    }
                } else {
                    boolean rst = dfs(k, p, q, board, 0, j + 1);
                    if (rst) {
                        return true;
                    }
                }
            } else {
                for (int x = 1; x <= 9; x++) {
                    if (p[i][x] != 1 && q[j][x] != 1 && k[which(i, j)][x] != 1) {
                        p[i][x] = 1;
                        q[j][x] = 1;
                        k[which(i, j)][x] = 1;
                        board[i][j] = (char) (x + '0');
                        if (i + 1 < 9) {
                            boolean rst = dfs(k, p, q, board, i + 1, j);
                            if (rst) {
                                return true;
                            }
                        } else {
                            boolean rst = dfs(k, p, q, board, 0, j + 1);
                            if (rst) {
                                return true;
                            }
                        }
                        p[i][x] = 0;
                        q[j][x] = 0;
                        k[which(i, j)][x] = 0;
                        board[i][j] = '.';
                    }
                }
            }
            return false;
        }

### 测试用例 ###

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan