导读：回溯是常用的算法理论之一，很多规模较大、直接分析较为复杂的问题都可以考虑用回溯求解，例如N皇后问题、骑士周游和走迷宫问题等。本质上，回溯问题是一种优化后的暴力求解，通过及时的剪枝和启发式的寻找最优路径，可以有效加速求解过程。回溯还常常与递归搭配使用。
我们考虑应用回溯求解经典数独问题，描述如下：
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
来源：力扣（LeetCode）37# 解数独
一个有效的数独方案
数独是一个经典的可用回溯+递归求解的问题。在给定初始状态后，通过在空白区域不断尝试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
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
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)
[['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']]
数独是一款填充数字类的游戏，一个数独必须满足如下游戏规则：常见的数独是一个由9个3x3的九宫格组成的，总共有81个小单元格，每个单元格里面通过填充数字1到9，使得整个数独满足其规则，那么这个数独就是一个有效的数独的解。上面就是一个待完成的数独，一个数独可能没有解，也可能具有多个解，例如上面的数独其中一个解就可以如下所示： 下面介绍一下求解数独需要使用到的算法思想，即：递归和回溯算法。在解数独的过程里面，我们需要向每一个没有填充数字的单元格中，依次填充数字1到9，判断是否能够使得当前单元格所在行、列、3x..
那么接数独的思路是这样的，在一个空格子中，先从同一列，同一行，小矩阵中排除已有的数字，然后在剩下的数字中先填一个，再到下一个空格子中重复此步骤，如果下一个格子中找不出解，那么说明在之前的步骤中填的数字是不对的，那就回退到之前的格子，换一个数字继续下一
数独可以使用递归回溯算法解决。
什么是回溯算法？
在回溯算法中，您尝试一次构建一个解决方案。如果在某些步骤上可以清楚地知道当前的路径无法导致解决方案，则请返回上一步（回溯）并选.
我们可以考虑按照「行优先」的顺序依次枚举每一个空白格中填的数字，通过递归 + 回溯的方法枚举所有可能的填法。当递归到最后一个空白格后，如果仍然没有冲突，说明我们找到了答案；在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。
由于每个数字在同一行、同一列、同一个九宫格中只会出现一次，因此我们可以使用 \textit{line}[i]line[i]，\textit{column}[j]column[j]，\textit{block}[x][y]block[x][y] 分别表示第 ii 行，
数独，是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。
数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以
递归求解数独(C语言)本程序采用c语言编写，作用是获得一个数独的解。经测试，计算普通数独时间花费不大于0.02秒。
计算“世界最难数独”时间花费约为0.05秒。
计算效率中等，有待提高。
输入会自动忽略所有的空格和回车等非数字。输入方便，可以多行分开输入也可以在一行输入。
#includeusing namespace std;void init();void function(int m);int canplace(int row,int col,int c);void outputresult();int a[9][9], maxm = 0;int main(){init();function(0);return 0;}void init(){int i, j;...
编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则数字1-9在每一行只能出现一次。数字1-9在每一列只能出现一次。数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）数独部分空格内已填入了数字，空白格用‘.’表示。...
