01
数独问题
我们考虑应用回溯求解经典数独问题，描述如下：
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
来源：力扣（LeetCode）37# 解数独
02
数独求解
数独是一个经典的可用回溯+递归求解的问题。在给定初始状态后，通过在空白区域不断尝试1-9中合理的数字，直至完成所有填充即可。
Talk is cheap, let's see the code!
- 明确初始状态：对于给定数独，查找待填充的空白方格，并用一个栈数据结构保存
def getLocs(board): locs = [] for row in range(9): for col in range(9): if board[row][col] == '.': locs.append((row, col)) return locs
标记出现数字：对数独的9行、9列和9个子块中已出现的数字记录，并保存在字典中
from collections import defaultdict as dd def getMaps(board): rowMap = [dd(int) for _ in range(9)] colMap = [dd(int) for _ in range(9)] blockMap = [dd(int) for _ in range(9)] for row in range(9): for col in range(9): if board[row][col] != '.': num = int(board[row][col]) rowMap[row][num] += 1 colMap[col][num] += 1 bolckIndex = int(row/3)*3+int(col/3) blockMap[bolckIndex][num] += 1 return rowMap, colMap, blockMa
- 递归求解：对于给定状态的数独和空白方格栈，依次尝试填充数字1-9：如果存在一个可行的数字，则在此基础上递归填充下一空白；否则，回溯上一状态，寻求其他解决方案
def fillBoard(board, locs): if not locs: return True row, col = locs.pop() bolckIndex， found = int(row/3)*3+int(col/3)， False for num in range(1, 10): if found: break if not rowMap[row][num] and not colMap[col][num] and not blockMap[bolckIndex][num]: rowMap[row][num] = colMap[col][num] = blockMap[bolckIndex][num] = 1 board[row][col] = str(num) found = fillBoard(board, locs) rowMap[row][num] = colMap[col][num] = blockMap[bolckIndex][num] = 0 if not found: locs.append((row, col)) return found
- 主调用程序：完成初始状态，递归求解。由于在递归求解中是直接更改的原数独数组，所以无返回值。
if __name__ == '__main__': rowMap, colMap, blockMap = getMaps(board) locs = getLocs(board) if fillBoard(board, locs): print(board)
03
执行结果
- 数独结果
[['5', '3', '4', '6', '7', '8', '9', '1', '2'], ['6', '7', '2', '1', '9', '5', '3', '4', '8'], ['1', '9', '8', '3', '4', '2', '5', '6', '7'], ['8', '5', '9', '7', '6', '1', '4', '2', '3'], ['4', '2', '6', '8', '5', '3', '7', '9', '1'], ['7', '1', '3', '9', '2', '4', '8', '5', '6'], ['9', '6', '1', '5', '3', '7', '2', '8', '4'], ['2', '8', '7', '4', '1', '9', '6', '3', '5'], ['3', '4', '5', '2', '8', '6', '1', '7', '9']]
- 执行效率
