递归+回溯求解数独问题
导读：回溯是常用的算法理论之一，很多规模较大、直接分析较为复杂的问题都可以考虑用回溯求解，例如N皇后问题、骑士周游和走迷宫问题等。本质上，回溯问题是一种优化后的暴力求解，通过及时的剪枝和启发式的寻找最优路径，可以有效加速求解过程。回溯还常常与递归搭配使用。
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, blockMap
- 递归求解：对于给定状态的数独和空白方格栈，依次尝试填充数字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']]
- 执行效率
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
云数据库 MySQL
腾讯云数据库 MySQL（TencentDB for MySQL）为用户提供安全可靠，性能卓越、易于维护的企业级云数据库服务。其具备6大企业级特性，包括企业级定制内核、企业级高可用、企业级高可靠、企业级安全、企业级扩展以及企业级智能运维。通过使用腾讯云数据库 MySQL，可实现分钟级别的数据库部署、弹性扩展以及全自动化的运维管理，不仅经济实惠，而且稳定可靠，易于运维。