37.md

题目地址

https://leetcode-cn.com/problems/sudoku-solver/

解答

class Solution(object):
    def solveSudoku(self, board):
        """ 解决9*9数独 """
        pos, H, V, G = [], [0] * 9, [0] * 9, [0] * 9  # 分别是：单元格的位置、水平位置、垂直位置、网格位置
        ctoV = {str(i): 1 << (i - 1) for i in range(1, 10)}  # 转换成1后面加i-1个0的形式，如:'4'=>1000
        self.vtoC = {1 << (i - 1): str(i) for i in range(1, 10)}  # 1后面加i-1个0的形式转换成数字，如:100=>'3'
        for i, row in enumerate(board):
            for j, c in enumerate(row):
                if c != '.':  # 如果是数独中的数字
                    v = ctoV[c]  # 获取1000式的值
                    # 计算行列和网格中出现的1~9的数字的次数，如1 | 100 | 1000，即为出现4, 3, 1
                    H[i], V[j], G[i // 3 * 3 + j // 3] = H[i] | v, V[j] | v, G[i // 3 * 3 + j // 3] | v
                else:
                    pos += (i, j),
        # 0*7 + 111111111 & (0000000000001010按位取反为1*8 + 11110101) = 0000000111110101，此为补码，即501。负数的补码最后一个1不动，其他位取反)
        # 计算未出现的值，如[393, 4], print(bin(393))可知[0b110001001, 3]，即数独中可填数字为9, 8, 4, 1
        posDict = {(i, j): [x, self.countOnes(x)] for i, j in pos \
                   for x in [0x1ff & ~(H[i] | V[j] | G[i // 3 * 3 + j // 3])]}
        print(posDict)
        self.slove(board, posDict)

    def countOnes(self, n):
        """
            计算n中1的数量
        """
        count = 0
        while n:
            count, n = count + 1, n & (n - 1)
        return count

    def slove(self, board, posDict):
        if len(posDict) == 0:
            return True
        p = min(posDict.keys(), key=lambda x: posDict[x][1])  # "."的位置，如(0, 2)
        candidate = posDict[p][0]
        while candidate:  # 如果某一个位置没有可填数字，那么就是无效数独
            v = candidate & (~candidate + 1)  # 获取最后一个1, 如0*8 + 10000100, 最后一个1为100, 值为4
            candidate &= ~v  # 从candidate中去掉最后一个1
            tmp = self.updata(board, posDict, p, v)  # 修改board和posDict
            if self.slove(board, posDict):  # 为下一个填值, 如果posDict为空，则代表都填完了，此时的数独为一个有效数独，那么结束递归
                return True
            self.recovery(board, posDict, p, v, tmp)  # 用recovery函数回溯
        return False

    def updata(self, board, posDict, p, v):
        """
            把最后一个1更新到board
            posDict中删除key为p的键值对
            posDict中的相关点去掉最后一个1，计数减1
            返回[posDict[p], 相关点的key]
        """
        i, j = p[0], p[1]
        board[i][j] = self.vtoC[v]  # 把100转为1~9的数字
        tmp = [posDict[p]]  # 如[[393, 4]]
        del posDict[p]
        for key in posDict.keys():
            if i == key[0] or j == key[1] or (i // 3, j // 3) == (key[0] // 3, key[1] // 3):  # 相关的点
                if posDict[key][0] & v:  # 如果可以填入相同元素，则需要去掉这个元素
                    posDict[key][0] &= ~v  # 去掉这个元素
                    posDict[key][1] -= 1  # 可选填数字减一
                    tmp += key,  # 把这些点记录下来，形如[[393, 4], (0, 4), (5, 4)]
        return tmp

    def recovery(self, board, posDict, p, v, tmp):
        """ 回溯恢复 """
        board[p[0]][p[1]] = '.'
        posDict[p] = tmp[0]  # 把这个点的位置和值添加回posDict
        for key in tmp[1:]:
            posDict[key][0] |= v  # 把最后一个1添加回相关的点中
            posDict[key][1] += 1  # 把相关点的计数加1