LeetCode Sudoku Solver

原題

通過程序來解決數獨問題。

注意點：

例子：

輸入:

輸出:

解題思路

這次不是像 Valid Sudoku 一樣只需要判斷數獨是否合法，而是要給出確切的解，但還是可以復用一下判斷是否符合數獨規則的方法。采用遞歸來解決，遞歸的終止條件有：

遍歷每個格子，如果已經有數字，則繼續遞歸下一個位置；如果沒有，就放入一個數字並檢查是否符合規則，如果符合則繼續遞歸，如果遞歸失敗，則要進行回溯，將數字改為空格，繼續嘗試別的數字。直到放入一個合適的值後再去填下一個位置。

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']