python实现leetcode之37. 解数独（哈希+回溯）

解题思路

按行
按列
按九宫
建每一个集合
将出现的数字加入对应三个集合
然后计算出待填位置的候选项
对所有位置按照下标项xy排序后,在可选项上尝试直到找到有效方案
如果进入瓶颈，后退回溯解决
每次前进的时候记住位置，回溯时从那个位置继续，与N皇后问题解决方案一样

37. 解数独

代码

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        cells = [set() for _ in range(9)]
        empty_cells = {}  # (x, y): options
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty_cells[(i, j)] = set([x for x in range(1, 10)])
                else:
                    rows[i].add(int(board[i][j]))
                    cols[j].add(int(board[i][j]))
                    cell_idx = (i // 3) * 3 + (j//3)
                    cells[cell_idx].add(int(board[i][j]))
        for x, y in empty_cells:
            cell_idx = (x // 3) * 3 + (y//3)
            for n in rows[x] | cols[y] | cells[cell_idx]:
                empty_cells[(x, y)].discard(n)

        empty_cells = sorted([(x, y, list(options)) for (x, y), options in empty_cells.items()])
        trace = []
        i = j = 0
        while i < len(empty_cells):
            x, y, options = empty_cells[i]
            cell_idx = (x // 3) * 3 + (y//3)
            find = False
            for j in range(j, len(options)):
                v = options[j]
                if v in rows[x] or v in cols[y] or v in cells[cell_idx]:
                    continue
                else:
                    board[x][y] = str(v)
                    rows[x].add(v)
                    cols[y].add(v)
                    cells[cell_idx].add(v)
                    trace.append([i, j])
                    find = True
                    break
            if find:  # 处理完一个单元格，查看是不是有冲突
                i += 1
                j = 0
            else:
                i, j = trace.pop()
                x, y, options = empty_cells[i]
                cell_idx = (x // 3) * 3 + (y//3)
                v = int(board[x][y])
                board[x][y] = '.'
                rows[x].discard(v)
                cols[y].discard(v)
                cells[cell_idx].discard(v)
                j += 1

效果图