ChoDocs

外观

LeetCode 37. 解数独 困难 ​

作者:Choi Yang
更新于:6 个月前
字数统计:1.1k 字
阅读时长:5 分钟
阅读量:

题目描述 ​

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

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

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

一个数独。

答案被标成红色。

提示：

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sudoku-solver 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

我们一行一行的放，如果能得到一个解，直接返回 true，然后剪枝条件如下述 check函数。

参考 xiao_ben_zhu 大佬图解
https://leetcode-cn.com/problems/sudoku-solver/solution/shou-hua-tu-jie-jie-shu-du-hui-su-suan-fa-sudoku-s/
javascript
var solveSudoku = function (board) {
  let check = (x, y, val) => {
    // 一行或者一列有重复元素，剪掉
    for (let i = 0; i < 9; i++) {
      if (board[x][i] == val || board[i][y] == val) return true;
    }
    let xx = Math.floor(x / 3) * 3;
    let yy = Math.floor(y / 3) * 3;
    // 3x3宫格内重复的情况，剪掉
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[xx + i][yy + j] == val) return true;
      }
    }
    return false; // 没有冲突情况
  };
  let dfs = (x, y) => {
    if (y == 9) {
      x++;
      y = 0;
      if (x == 9) return true; // 都填完了，直接返回 true
    }
    if (board[x][y] != ".") return dfs(x, y + 1);
    for (let i = 1; i < 10; i++) {
      if (check(x, y, String(i))) continue;
      board[x][y] = String(i);
      if (dfs(x, y + 1)) return true; // 如果往下走，能够解出数独，直接返回 true
      board[x][y] = "."; // 回溯，因为往下走得不到一个解
    }
    return false;
  };
  dfs(0, 0);
  return board;
};
cpp
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> row(9, vector<bool>(9, false));
        vector<vector<bool>> col(9, vector<bool>(9, false));
        vector<vector<bool>> block(9, vector<bool>(9, false));
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '1';
                    row[i][num] = true;
                    col[j][num] = true;
                    block[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs(board, row, col, block, 0, 0);
    }
    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& row, vector<vector<bool>>& col, vector<vector<bool>>& block, int i, int j){
        if(j == 9){
            i++;
            j = 0;
            if(i == 9) return true;
        }
        if(board[i][j] != '.') return dfs(board, row, col, block, i, j + 1);
        for(int k = 0; k < 9; k++){
            if(row[i][k] || col[j][k] || block[i / 3 * 3 + j / 3][k]) continue;
            board[i][j] = k + '1';
            row[i][k] = true;
            col[j][k] = true;
            block[i / 3 * 3 + j / 3][k] = true;
            if(dfs(board, row, col, block, i, j + 1)) return true;
            board[i][j] = '.';
            row[i][k] = false;
            col[j][k] = false;
            block[i / 3 * 3 + j / 3][k] = false;
        }
        return false;
    }
};
java
class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col = new boolean[9][9];
        boolean[][] block = new boolean[9][9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '1';
                    row[i][num] = true;
                    col[j][num] = true;
                    block[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs(board, row, col, block, 0, 0);
    }
    public boolean dfs(char[][] board, boolean[][] row, boolean[][] col, boolean[][] block, int i, int j){
        if(j == 9){
            i++;
            j = 0;
            if(i == 9) return true;
        }
        if(board[i][j] != '.') return dfs(board, row, col, block, i, j + 1);
        for(int k = 0; k < 9; k++){
            if(row[i][k] || col[j][k] || block[i / 3 * 3 + j / 3][k]) continue;
            board[i][j] = (char)(k + '1');
            row[i][k] = true;
            col[j][k] = true;
            block[i / 3 * 3 + j / 3][k] = true;
            if(dfs(board, row, col, block, i, j + 1)) return true;
            board[i][j] = '.';
            row[i][k] = false;
            col[j][k] = false;
            block[i / 3 * 3 + j / 3][k] = false;
        }
        return false;
    }
}
python
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row = [[False] * 9 for _ in range(9)]
        col = [[False] * 9 for _ in range(9)]
        block = [[False] * 9 for _ in range(9)]
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j]) - 1
                    row[i][num] = True
                    col[j][num] = True
                    block[i // 3 * 3 + j // 3][num] = True
        self.dfs(board, row, col, block, 0, 0)
    def dfs(self, board, row, col, block, i, j):
        if j == 9:
            i += 1
            j = 0
            if i == 9:
                return True
        if board[i][j] != '.':
            return self.dfs(board, row, col, block, i, j + 1)
        for k in range(9):
            if row[i][k] or col[j][k] or block[i // 3 * 3 + j // 3][k]:
                continue
            board[i][j] = str(k + 1)
            row[i][k] = True
            col[j][k] = True
            block[i // 3 * 3 + j // 3][k] = True
            if self.dfs(board, row, col, block, i, j + 1):
                return True
            board[i][j] = '.'
            row[i][k] = False
            col[j][k] = False
            block[i // 3 * 3 + j // 3][k] = False
        return False
javascript
学如逆水行舟，不进则退

Contributors ​

Choi Yang