题目: 编写一个程序，通过已填充的空格来解决数独问题。
来源: https://leetcode-cn.com/problems/sudoku-solver/
法一: 自己的代码 注意board全局变量的用法
思路: 利用回溯法典型的模板,对没有填空的逐个遍历,测试用例的时候一定要注意边界条件,这个题的边界条件是九宫格的最后一个空,要分空和非空进行测试.回溯的时候有两种情况需要返回,一是全部填完了需要返回结果,二是某个格子没有可以填的数字,这时需要结束本次回溯,当用回溯法只返回一种情况的时候(如60题第K个排列),这时要把回溯函数写在return后面,当有两种及以上情况时,可以返回不同的值,用if语句进行判断,分别处理.
# 执行用时 :260 ms, 在所有 python3 提交中击败了34.63% 的用户 # 内存消耗 :12.8 MB, 在所有 python3 提交中击败了97.83%的用户 import typing as List class Solution: def solveSudoku(self, board): def cannot_place(row,col): # 如果为'.',说明可以放置数字,返回False,如果到最后一个或超出边界了,说明所有的都填满了 if (board[row][col] == '.') or ([row,col] in [[8,8],[9,0]]): return False else: return True def move_to_next_number(row,col): # 注意这里边界条件的设定,非常重要,很容易错 if col<8: return row,col+1 # 只有到了每行的最后一列,才会执行这个判断, elif row<8: col = 0 return row+1,col else: return 8,8 # 求(row,col)处可以填的数字 def diff_set(row,col): # a记录位置(row,col)所在行和列的数字 a = board[row] + [board[i][col] for i in range(9)] # k记录位置(row,col)所在九宫格的数字 p = int(row / 3) q = int(col / 3) dict = {0: (0, 3), 1: (3, 6), 2: (6, 9)} m, n = dict[p] u, v = dict[q] a = sum([i[u:v] for i in board[m:n]], []) + a a = set(a) if '.' in a: set(a).remove('.') b = [str(i+1) for i in range(9)] return list(set(b) - set(a)) def backtrack(row,col): # 如果当前位置有数字,则移到下一个 while cannot_place(row,col): row,col = move_to_next_number(row,col) # 如果到最后一个格子了,且该格不为空,则结束 if (row==8) & (col==8) & (board[8][8] != '.'): return True # 利用三个限定条件,减少数字的遍历数目 nums = diff_set(row,col) # 如果这个格子没有数字可以填了,则返回False回溯 if len(nums) == 0: return False for i in nums: board[row][col] = i # 这里为了避免重复判断,提前将空格移动到下一个,当前空格已经有数字了, # 无需在下一次的回溯中用while判断了,由于这里没有用while,要放止越界 p,q = move_to_next_number(row,col) # 这里的写法非常巧妙,因为回溯函数有两种情况需要中断,所以用一个if条件来判断 # 如果遇到nums为0,无法继续回溯,则返回False进行下一个, # 如果是找到合适的了,则返回True,结束程序 if backtrack(p,q): return True board[row][col] = '.' backtrack(row=0,col=0) if __name__ == '__main__': # data=[["5","3",".",".","7",".",".",".","."], # ["6",".",".","1","9","5",".",".","."], # [".","9","8",".",".",".",".","6","."], # ["8",".",".",".","6",".",".",".","3"], # ["4",".",".","8",".","3",".",".","1"], # ["7",".",".",".","2",".",".",".","6"], # [".","6",".",".",".",".","2","8","."], # [".",".",".","4","1","9",".",".","5"], # [".",".",".",".","8",".",".","7","9"]] data = [[".",".","9","7","4","8",".",".","."], ["7",".",".",".",".",".",".",".","."], [".","2",".","1",".","9",".",".","."], [".",".","7",".",".",".","2","4","."], [".","6","4",".","1",".","5","9","."], [".","9","8",".",".",".","3",".","."], [".",".",".","8",".","3",".","2","."], [".",".",".",".",".",".",".",".","6"], [".",".",".","2","7","5","9",".","."]] duixiang = Solution() duixiang.solveSudoku(data) print(data)
结合官方的字典方法修改后的,注意Do not return anything, modify board in-place instead.意思是直接修改board的值,不需要返回值,运行程序后,官方会根据传入board时的地址直接检查board地址的内容.即使把board的值赋值给另一个变量返回,再把board的值修改,结果也不会正确.
# 自己的代码 结合官网代码修改后的 # 执行用时 :272 ms, 在所有 python3 提交中击败了33.21% 的用户 # 内存消耗 :12.8 MB, 在所有 python3 提交中击败了97.83%的用户 import typing as List from collections import defaultdict class Solution: def solveSudoku(self, board): def cannot_place(row,col): # 如果为'.',说明可以放置数字,返回False,如果到最后一个或超出边界了,说明所有的都填满了 if (board[row][col] == '.') or ([row,col] in [[8,8],[9,0]]): return False else: return True def move_to_next_number(row,col): # 注意这里边界条件的设定,非常重要,很容易错 if col<8: return row,col+1 # 只有到了每行的最后一列,才会执行这个判断, elif row<8: col = 0 return row+1,col else: return 8,8 # 求(row,col)处可以填的数字 def diff_set(row,col): a = list(set(range(1,10)) - (set(rows[row].keys()) | set(columns[col].keys()) | set(boxes[box_index(row, col)].keys()))) return a # 给三个字典中添加值,并把字符添加到board中 def place_number(d, row, col): rows[row][d] += 1 columns[col][d] += 1 boxes[box_index(row, col)][d] += 1 board[row][col] = str(d) # 删除三个字典中的值,并删除board中的字符 def remove_numver(d, row, col): del rows[row][d] del columns[col][d] del boxes[box_index(row, col)][d] board[row][col] = '.' def backtrack(row,col): # 如果当前位置有数字,则移到下一个 while cannot_place(row,col): row,col = move_to_next_number(row,col) # 如果到最后一个格子了,且该格不为空,则结束 if (row==8) & (col==8) & (board[8][8] != '.'): return True # 利用三个限定条件,减少数字的遍历数目 nums = diff_set(row,col) # 如果这个格子没有数字可以填了,则返回False回溯 if len(nums) == 0: return False for i in nums: place_number(d=i, row=row, col=col) # 这里为了避免重复判断,提前将空格移动到下一个,当前空格已经有数字了, # 无需在下一次的回溯中用while判断了,由于这里没有用while,要放止越界 p,q = move_to_next_number(row,col) # 这里的写法非常巧妙,因为回溯函数有两种情况需要中断,所以用一个if条件来判断 # 如果遇到nums为0,无法继续回溯,则返回False进行下一个, # 如果是找到合适的了,则返回True,结束程序 if backtrack(p,q): return True remove_numver(d=i, row=row, col=col) n = 3 N = 9 box_index = lambda row, col: (row // n) * n + col // n rows = [defaultdict(int) for i in range(N)] columns = [defaultdict(int) for i in range(N)] boxes = [defaultdict(int) for i in range(N)] for i in range(N): for j in range(N): if board[i][j] != '.': d = int(board[i][j]) place_number(d, i, j) backtrack(row=0,col=0) if __name__ == '__main__': # data=[["5","3",".",".","7",".",".",".","."], # ["6",".",".","1","9","5",".",".","."], # [".","9","8",".",".",".",".","6","."], # ["8",".",".",".","6",".",".",".","3"], # ["4",".",".","8",".","3",".",".","1"], # ["7",".",".",".","2",".",".",".","6"], # [".","6",".",".",".",".","2","8","."], # [".",".",".","4","1","9",".",".","5"], # [".",".",".",".","8",".",".","7","9"]] data = [[".",".","9","7","4","8",".",".","."], ["7",".",".",".",".",".",".",".","."], [".","2",".","1",".","9",".",".","."], [".",".","7",".",".",".","2","4","."], [".","6","4",".","1",".","5","9","."], [".","9","8",".",".",".","3",".","."], [".",".",".","8",".","3",".","2","."], [".",".",".",".",".",".",".",".","6"], [".",".",".","2","7","5","9",".","."]] duixiang = Solution() duixiang.solveSudoku(data) print(data)
法二: 官方代码
思路: 建三个字典,每个字典分别存放行,列,九宫格的数字.要学会用字典存储数据的技巧.
from collections import defaultdict class Solution: def solveSudoku(self, board): def could_place(d, row, col): # 判断是否可以放置,这里用字典来实现 return not (d in rows[row] or d in columns[col] or d in boxes[box_index(row, col)]) # 对放置的数字做标记1 def place_number(d, row, col): rows[row][d] += 1 columns[col][d] += 1 boxes[box_index(row, col)][d] += 1 board[row][col] = str(d) # 不满足条件时,删除字典中的key def remove_number(d, row, col): del rows[row][d] del columns[col][d] del boxes[box_index(row, col)][d] board[row][col] = '.' def place_next_numbers(row, col): # 如果上一个放置的是最后一个格子,说明放满了,结束回溯 if col == N - 1 and row == N - 1: nonlocal sudoku_solved # global sudoku_solved 错误写法 sudoku_solved = True else: if col == N - 1: backtrack(row + 1, 0) else: backtrack(row, col + 1) def backtrack(row=0, col=0): # 如果为空开始遍历回溯 if board[row][col] == '.': # iterate over all numbers from 1 to 9 for d in range(1, 10): if could_place(d, row, col): place_number(d, row, col) place_next_numbers(row, col) # sudoku_solved为全局变量,默认为False, # 如果not sudoku_solved为真,说明对row,col格子全部遍历后仍未找到满足条件的解,删除它回溯继续寻找 if not sudoku_solved: remove_number(d, row, col) else: place_next_numbers(row, col) # box size n = 3 # row size N = n * n # lambda function to compute box index box_index = lambda row, col: (row // n) * n + col // n # 建立三个字典 rows = [defaultdict(int) for i in range(N)] columns = [defaultdict(int) for i in range(N)] boxes = [defaultdict(int) for i in range(N)] # 将原有的数字记录进三个字典中 for i in range(N): for j in range(N): if board[i][j] != '.': d = int(board[i][j]) place_number(d, i, j) sudoku_solved = False backtrack() if __name__ == '__main__': # data=[["5","3",".",".","7",".",".",".","."], # ["6",".",".","1","9","5",".",".","."], # [".","9","8",".",".",".",".","6","."], # ["8",".",".",".","6",".",".",".","3"], # ["4",".",".","8",".","3",".",".","1"], # ["7",".",".",".","2",".",".",".","6"], # [".","6",".",".",".",".","2","8","."], # [".",".",".","4","1","9",".",".","5"], # [".",".",".",".","8",".",".","7","9"]] data = [[".",".","9","7","4","8",".",".","."], ["7",".",".",".",".",".",".",".","."], [".","2",".","1",".","9",".",".","."], [".",".","7",".",".",".","2","4","."], [".","6","4",".","1",".","5","9","."], [".","9","8",".",".",".","3",".","."], [".",".",".","8",".","3",".","2","."], [".",".",".",".",".",".",".",".","6"], [".",".",".","2","7","5","9",".","."]] duixiang = Solution() duixiang.solveSudoku(data) print(data)
法三: 别人的代码
思路: 先把没有填数的位置都找出来,然后逐个回溯遍历,利用字典和set()实现非常巧妙!回溯结束的条件是没有填数的位置都遍历完了!
def solveSudoku(self, board: List[List[str]]) -> None: row = [set(range(1, 10)) for _ in range(9)] # 行剩余可用数字 col = [set(range(1, 10)) for _ in range(9)] # 列剩余可用数字 block = [set(range(1, 10)) for _ in range(9)] # 块剩余可用数字 empty = [] # 收集需填数位置 for i in range(9): for j in range(9): if board[i][j] != '.': # 更新可用数字 val = int(board[i][j]) row[i].remove(val) col[j].remove(val) block[(i // 3)*3 + j // 3].remove(val) else: empty.append((i, j)) def backtrack(iter=0): if iter == len(empty): # 处理完empty代表找到了答案 return True i, j = empty[iter] b = (i // 3)*3 + j // 3 for val in row[i] & col[j] & block[b]: row[i].remove(val) col[j].remove(val) block[b].remove(val) board[i][j] = str(val) if backtrack(iter+1): return True row[i].add(val) # 回溯 col[j].add(val) block[b].add(val) return False backtrack() 作者：yybeta 链接：https://leetcode-cn.com/problems/sudoku-solver/solution/pythonsethui-su-chao-guo-95-by-mai-mai-mai-mai-zi/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
ttt