37. Sudoku Solver **

你的名字 2021-11-01 04:46 265阅读 0赞

#### description: ####

数独

**Note:**

**Example:**

Example 1:
    
    Input:
    [
      ["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"]
    ]
    Output: true
    
    Example 2:
    
    Input:
    [
      ["8","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"]
    ]
    Output: false
    Explanation: Same as Example 1, except with the 5 in the top left corner being 
        modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

#### answer: ####

class Solution {
    public:
        void solveSudoku(vector<vector<char>>& board) {
            if (board.empty() || board.size() != 9 || board[0].size() != 9) return;
            solveDFS(board, 0, 0); //从阵列的左上角开始逐行逐列的递归填入检查
        }
        bool solveDFS(vector<vector<char>> &board, int i, int j) {
            if (i == 9) return true; // 如果行号到了9， 就证明已经全部遍历完毕
            if (j >= 9) return solveDFS(board, i + 1, 0); // 如果列号大于等于9了，就证明这一行已经ok了，可以进行下一行的递归了。
            if (board[i][j] == '.') { // 如果是需要填入的空，那就从1到9挨个试，看看哪个填入是合法的
                for (int k = 1; k <= 9; k++){
                    board[i][j] = (char)(k + '0');
                    if (isValid(board, i, j)) { // 如果是合法的，就继续递归，跳出递归之后就结束了也，这里必须要写return ，这样才能跳出循环，同时满足函数返回值类型
                        if (solveDFS(board, i, j + 1)) return true;
                    }
                    board[i][j] = '.'; // 这个是只有九个数都试过了但是都不行，就恢复原状，然后就跳到最后那个 return false 上去了，这样它前面一列那个数就相当于要换个k重新试试，这样不断往前改，总是能保证当前数之前填过的数都是正确的。
                }
            } else {
                return solveDFS(board, i, j + 1); // 如果不是需要去填的空，就跳过现在这个数继续递归，这里一定要写return
            }
            return false; 
        }
        bool isValid(vector<vector<char>> &board, int i, int j) {
            for (int col = 0; col < 9; ++col) {
                if (col != j && board[i][j] == board[i][col]) return false;
            }
            for (int row = 0; row < 9; ++row) {
                if (row != i && board[i][j] == board[row][j]) return false;
            }
            for (int row = i/3*3; row < i/3*3 + 3; ++row) {
                for (int col = j/3*3; col < j/3*3 + 3; ++col) {
                    if ((row != i || col != j) && board[i][j] == board[row][col]) return false; //这里是 || 只要行或者列任意一个数不一样就要比一下
                }
            }
            return true;
        }
    };

#### relative point get√： ####

#### hint : ####

转载于:https://www.cnblogs.com/forPrometheus-jun/p/11123306.html