当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > LeetCode Sudoku Solver

LeetCode Sudoku Solver

文章作者:新注册送38元体验金编程 上传时间:2019-08-29

LeetCode Sudoku Solver

原题

通过程序来解决数独问题。

注意点:

有且只有唯一解

例子:

输入:

新注册送38元体验金 1

输出:

新注册送38元体验金 2

解题思路

这次不是像 Valid Sudoku 一样只需要判断数独是否合法,而是要给出确切的解,但还是可以复用一下判断是否符合数独规则的方法。采用递归来解决,递归的终止条件有:

遍历完所有的格子违反数独的规则

新注册送38元体验金,遍历每个格子,如果已经有数字,则继续递归下一个位置;如果没有,就放入一个数字并检查是否符合规则,如果符合则继续递归,如果递归失败,则要进行回溯,将数字改为空格,继续尝试别的数字。直到放入一个合适的值后再去填下一个位置。

AC源码

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        for row in range(9):
            board[row] = list(board[row])
        self.recursive(0, 0, board)
        for row in range(9):
            board[row] = "".join(board[row])

    def recursive(self, i, j, board):
        if j >= 9:
            return self.recursive(i   1, 0, board)
        if i == 9:
            return True

        if board[i][j] == ".":
            for num in range(1, 10):
                num_str = str(num)
                if all([board[i][col] != num_str for col in
                        range(9)]) and all([board[row][j] != num_str for row in range(9)]) and all(
                    [board[i // 3 * 3   count // 3][j // 3 * 3   count % 3] != num_str for count in
                     range(9)]):
                    board[i][j] = num_str
                    if not self.recursive(i, j   1, board):
                        board[i][j] = "."
                    else:
                        return True
        else:
            return self.recursive(i, j   1, board)
        return False


if __name__ == "__main__":
    sudoku = ["..9748...", "7........", ".2.1.9...", "..7...24.", ".64.1.59.", ".98...3..", "...8.3.2.", "........6",
              "...2759.."]
    Solution().solveSudoku(sudoku)
    assert sudoku == ['519748632', '783652419', '426139875', '357986241', '264317598', '198524367', '975863124',
                      '832491756', '641275983']

 

Sudoku Solver 原题 通过程序来解决数独问题。 注意点: 有且只有唯一解 例子: 输入: 输出: 解题思路 这次不是像 Valid Sudoku 一样只需...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:LeetCode Sudoku Solver

关键词: