[数据结构与算法]LeetCode-【回溯】解数独

这是一道非常经典的回溯（暴力搜索）

题目描述

题目分析

参考题解1
参考题解2

基本思想就是设立三个约束（行、列、九宫格），然后对于每一个空格进行1~9的试下棋，满足约束着可以继续递归，
若搜索不到解，则回溯；搜索到了则进入快速通道（添加变量 valid 用作判断）

优化一：使用set去重。去重是回溯问题经常结合的，难度也会上升，该方法其实形象的理解就是
当我面对空格时，找出这个空格的备选项，知道可以填哪些数字，然后一一递归回溯，而基本思想是1~9都试一遍

优化二：位运算。也很好理解，之前使用一个bool类型变量用来判断空格即将填入的数字是否满足约束，这样未免太浪费内存了，
于是乎，使用一个位 0/1 来代替bool变量，但这带来的困难是怎样去用位运算表示空格还能填入的数字集合、以及这些数字怎么去迭代等

python实现

以下展示了三种方法：

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        '''
        # 方法一：回溯dfs
        def dfs(pos:int):
            # nonlocal变量 防止与全局变量valid（solveSudoku函数以外）冲突
            nonlocal valid
            if pos == len(spaces):
                # 填写完所有空白位置，进入快速返回通道
                valid = True
                return 
            # 找到一个空白位置
            i,j = spaces[pos]
            for digit in range(9):
                # 找到一个可行数字
                if line[i][digit] == column[j][digit] == block[i//3][j//3][digit] == False:
                    # 假设先下这一步
                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = True
                    board[i][j] = str(digit+1)	#一定会修改成最终结果
                    # 继续下剩下空白位置
                    dfs(pos+1)
                    # 没找到快速通道，则假设的这步不成功
                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = False
                if valid:
                    # 找到一个可行解则走该快速通道返回
                    return 


        # 行、列、九宫格内标记digit是否使用过
        line = [[False]*9 for _ in range(9)]
        column = [[False]*9 for _ in range(9)]
        block = [[[False]*9 for _a in range(3)] for _b in range(3)]
        spaces = []
        valid = False

        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i,j))
                else:
                    digit = int(board[i][j])-1
                    line[i][digit] = column[j][digit] = block[i//3][j//3][digit] = True

    	# 从第一个开始深度遍历
        dfs(0)

        '''
		
        '''
        # 方法二：使用set优化
        line = [set(range(1,10)) for _ in range(9)]
        column = [set(range(1,10)) for _ in range(9)]
        block  = [set(range(1,10)) for _ in range(9)]
        spaces = []
        valid = False

        for i in range(9):
            for j in range(9):
                if board[i][j] != ".":
                    val = int(board[i][j])
                    line[i].remove(val)
                    column[j].remove(val)
                    block[(i//3)*3+j//3].remove(val)
                else:
                    spaces.append((i,j))


        def dfs(pos:int):
            nonlocal valid
            if len(spaces)==pos:
                valid = True
                return 
            
            i,j = spaces[pos]
            for digit in line[i]&column[j]&block[(i//3)*3+j//3]:
                line[i].remove(digit)
                column[j].remove(digit)
                block[(i//3)*3+j//3].remove(digit)
                board[i][j] = str(digit)
                dfs(pos+1)
                # 回溯
                line[i].add(digit)
                column[j].add(digit)
                block[(i//3)*3+j//3].add(digit)
                if valid:return 
        dfs(0)
        '''

        # 方法三：位操作优化
        def flip(i,j,digit):
            # 翻转第digit位电平
            line[i] ^= (1<<digit)
            column[j] ^= (1<<digit)
            block[i//3][j//3] ^= (1<<digit)

        def dfs(pos:int):
            nonlocal valid
            if pos == len(spaces):
                valid = True
                return
            
            i,j = spaces[pos]
            # bin(mask): (0000 0000 0000 0011)表示前9位中，数字1、2仍未使用
            mask = ~(line[i]|column[j]|block[i//3][j//3]) & 0x1ff
            while mask:
                # 找到第一个 1 
                digitmask = mask & (-mask)
                digit = bin(digitmask).count('0')-1
                flip(i,j,digit)
                board[i][j] = str(digit+1)
                dfs(pos+1)
                flip(i,j,digit)
                # 迭代下一位digit
                mask &= (mask-1)
                if valid:
                    return

        line = [0]*9
        column = [0]*9
        block = [[0]*3 for _ in range(3)]
        spaces = []
        valid = False
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i,j))
                else:
                    digit = int(board[i][j])-1
                    flip(i,j,digit)
        dfs(0)
        

代码性能