leetcode 36. Valid Sudoku | 37. Sudoku Solver（数独）

刺骨的言语ヽ痛彻心扉 2022-09-07 06:14 171阅读 0赞

## 36. Valid Sudoku ##

[https://leetcode.com/problems/valid-sudoku/][https_leetcode.com_problems_valid-sudoku]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

class Solution { 
        public boolean isValidSudoku(char[][] board) { 
            boolean[][] rows = new boolean[9][9];
            boolean[][] cols = new boolean[9][9];
            boolean[][] grids = new boolean[9][9];
            for (int i = 0; i < 9; i++) { 
                for (int j = 0; j < 9; j++) { 
                    if (board[i][j] == '.') continue;
                    int n = board[i][j] - '1';
                    int g = 3 * (i / 3) + (j / 3);
                    if (rows[i][n] || cols[j][n] || grids[g][n]) return false;
                    rows[i][n] = true;
                    cols[j][n] = true;
                    grids[g][n] = true;
                }
            }
            return true;
        }
    }

## 37. Sudoku Solver ##

[https://leetcode.com/problems/sudoku-solver/][https_leetcode.com_problems_sudoku-solver]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

## 题解 ##

思路是：暴力 DFS 无任何记忆，每走到下一个空闲格子，遍历放进 1 ~ 9 看是否可行。如果 1 ~ 9 都不行，回溯返回上一级。

class Solution { 
        public void solveSudoku(char[][] board) { 
            boolean[][] rows = new boolean[9][9];
            boolean[][] cols = new boolean[9][9];
            boolean[][] grids = new boolean[9][9];
            int filled = 0;
            for (int i = 0; i < 9; i++) { 
                for (int j = 0; j < 9; j++) { 
                    if (board[i][j] != '.') { 
                        int n = board[i][j] - '1';
                        int g = 3 * (i / 3) + (j / 3);
                        rows[i][n] = true;
                        cols[j][n] = true;
                        grids[g][n] = true;
                        filled++;
                    }
                }
            }
    
            for (int i = 0; i < 9; i++) { 
                for (int j = 0; j < 9; j++) { 
                    if (board[i][j] == '.') { 
                        for (int num = 1; num <= 9; num++) { 
                            if (tryFill(board, i, j, num, rows, cols, grids, filled)) return;
                        }
                    }
                }
            }
        }
    
        public boolean tryFill(char[][] board, int i, int j, int value, boolean[][] rows, boolean[][] cols, boolean[][] grids, int filled) { 
            int n = value - 1;
            int g = 3 * (i / 3) + (j / 3); // 九宫格的index
            if (rows[i][n] || cols[j][n] || grids[g][n]) {  // 当前数字冲突
                return false;
            } else {  // 当前数字有效
                board[i][j] = (char) ('0' + value);
                rows[i][n] = true;
                cols[j][n] = true;
                grids[g][n] = true;
                if (++filled == 9 * 9) return true;
                // 填充下一个位置
                for (int ii = 0; ii < 9; ii++) { 
                    for (int jj = 0; jj < 9; jj++) { 
                        if (board[ii][jj] == '.') {  // 首个下一个位置
                            for (int v = 1; v <= 9; v++) { 
                                if (tryFill(board, ii, jj, v, rows, cols, grids, filled)) return true;
                            }
                            // value=1~9都不能填充下一个位置，直接返回
                            board[i][j] = '.';
                            rows[i][n] = false;
                            cols[j][n] = false;
                            grids[g][n] = false;
                            return false;
                        }
                    }
                }
            }
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_valid-sudoku]: https://leetcode.com/problems/valid-sudoku/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/e9dcbf1a96664631a4de576e23d91273.png
[https_leetcode.com_problems_sudoku-solver]: https://leetcode.com/problems/sudoku-solver/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/a177c5ddfac740799ab3b5e47fcfbea1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/46b9cc3bf44c4126833440882119cc12.png