# 递归+回溯求解数独问题

01

02

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
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']]
```
• 执行效率

0 条评论

• ### 链家网杭州房产销售分析

杭州，一个集历史厚重积淀与现代发展潜质于一身的城市：回望历史，是当年越王勾践屯兵抗吴的重要军事城堡，也是隋炀帝杨广兴修京杭大运河的目的地，更是宋高宗赵构在靖康之...

• ### 如何变得更加pythonic？——一份关于PEP的入门指南

导读：如果你是一个python初学者，那么可能听过编码规范这一说；如果你是一个python老鸟，那么可能知道有很多PEP文档，但可能也缺乏系统了解；如果你是一个...

• ### pandas时间序列常用方法简介

pandas是Python数据分析最好用的第三方库，没有之一。——笛卡儿没说过这句话！

• ### 解数独

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只...

• ### 用回溯算法求解数独问题

回溯是通过逐步构建解决方案来解决递归问题的算法。通常回溯从可能的解决方案开始，如果它不起作用，则需要回溯并尝试另一种解决方案，直到找到可行的解决方案为止。回溯在...

• ### 第7期 | cmd-parser，一个基于哈希匹配的超快命令解析器

本专栏由Mculover666创建，主要内容为寻找嵌入式领域内的优质开源项目，一是帮助开发者使用开源项目实现更多的功能，二是通过这些开源项目，学习大佬的代码及背...

• ### CCF考试——201409-4最优配餐

栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。 　　栋栋的连锁店所在的区域可以看成是一个...

• ### 《剑指offer》二维数组中的查找——巧妙解法

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个...

• ### python数据科学-多变量数据分析

总第87篇 01|写在前面： 在前面我们研究了单列(变量)数据情况，现实中的案例大多都是多列(变量)的，即影响一件事情的因素有多个，我们除了要看单列数据以外还需...

• ### 几类关系型数据库的数据解决方案

今天聊下几类关系型数据库的数据解决方案,算是抛砖引玉，近期也要对技术方向上做一些扩展，也算是前期的小结吧。 Oracle 目前市面上的主流版本应该还是11g...