37.解数独

做了两天晚上才做出来，主要是回溯忘得差不多了。 第一个问题是怎么终止回溯，用的是函数返回值，如果不为空就表示找到答案，不用继续向下了直接返回就行 第二个注意的思想是每一层函数只进行一个操作（试一个格子），操作完了就进下一层，不要for循环操作多个，就死循环了

class Solution:
    def get_candidates(self, board) -> List[Tuple[int, int, List[int]]]:
        """
        计算所有空白区域的候选数字
        :param board: List，每个元素是个Tuple，分别是row，col和候选数字
        如[(1,1,[1,2,3])]表示第一行第一列可以填入1、2、3
        :return:
        """
        candidates = []
        for row in range(9):
            for col in range(9):
                if board[row][col] != ".":
                    continue
                candidate = []
                r, c = row // 3 * 3, col // 3 * 3
                cell = [board[r][c], board[r][c + 1], board[r][c + 2],
                        board[r + 1][c], board[r + 1][c + 1], board[r + 1][c + 2],
                        board[r + 2][c], board[r + 2][c + 1], board[r + 2][c + 2]]
                for test_num in range(1, 10):
                    if str(test_num) in cell + board[row] + [line[col] for line in board]:
                        continue
                    candidate.append(str(test_num))
                if candidate:
                    candidates.append((row, col, candidate))
        return list(sorted(candidates, key=lambda candidate: len(candidate[2])))

    def solveSudoku(self, board: List[List[str]]) -> Optional[List]:
        """
        Do not return anything, modify board in-place instead.
        """
        candidates = self.get_candidates(board)
        if not candidates:   # 没有可以填的数字了，要么是填完了，要么是填错了
            for line in board:
                if "." in line: # 填错了
                    return
            else: # 填完了
                return board
        candidate = candidates[0]
        for test_num in candidate[2]:
            board[candidate[0]][candidate[1]] = test_num
            res = self.solveSudoku(board)
            if res:
                return res
        board[candidate[0]][candidate[1]] = "."

评论