37. Sudoku Solver 求解数独

[GH1995]

37. Sudoku Solver

Difficulty: Hard

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

Solution

Language: C++

class Solution {
 public:
  void solveSudoku(vector<vector<char>>& board) {
    if (board.empty() || board.size() != 9 || board.front().size() != 9) return;
    dfs(board, 0, 0);
  }

  bool dfs(vector<vector<char>>& board, int i, int j) {
    if (i == 9) return true;                  // 临界条件
    if (j >= 9) return dfs(board, i + 1, 0);  // 状态转换

    // 两种扩展
    if (board[i][j] == '.') {
      for (int k = 1; k <= 9; ++k) {
        board[i][j] = k + '0';

        if (isValid(board, i, j))
          if (dfs(board, i, j + 1))  // 相信 i,j+1也合法，信任链
            return true;

        board[i][j] = '.'; // 恢复原状
      }
    } else {
      return dfs(board, i, j + 1);
    }
    return false;
  }

  bool isValid(vector<vector<char>>& board, int i, int j) { // 这里检查的是 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;
  }
};

[GH1995]

return的是信任链

对于每个需要填数字的格子带入1到9，每代入一个数字都判定其是否合法，如果合法就继续下一次递归，结束时把数字设回'.'，判断新加入的数字是否合法时，只需要判定当前数字是否合法，不需要判定这个数组是否为数独数组，因为之前加进的数字都是合法的，这样可以使程序更加高效一些

• 决定谁来消耗，这里没有人来消耗，一种新的模式

• 决定谁来拓展

  • j作快拓展
  • i作慢拓展

• 临界条件转换j >= 9怎么办 (i, j + 1) - > (i, 9)-> (i + 1, 0)

• 判断当前字符

  • 如果当前是.，说明可以拓展，用1~9进行拓展 (i, j + 1)
  • 如果当前是数字，直接相信合法，拓展 (i, j + 1)

• 检查函数，主要检查的是传入的j，检查board[i][j] 合法性