递归+回溯求解数独问题

导读：回溯是常用的算法理论之一，很多规模较大、直接分析较为复杂的问题都可以考虑用回溯求解，例如N皇后问题、骑士周游和走迷宫问题等。本质上，回溯问题是一种优化后的暴力求解，通过及时的剪枝和启发式的寻找最优路径，可以有效加速求解过程。回溯还常常与递归搭配使用。

数独问题

我们考虑应用回溯求解经典数独问题，描述如下：

编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。空白格用 '.' 表示。来源：力扣（LeetCode）37# 解数独

一个有效的数独方案

数独求解

数独是一个经典的可用回溯递归求解的问题。在给定初始状态后，通过在空白区域不断尝试1-9中合理的数字，直至完成所有填充即可。

Talk is cheap, let's see the code!

明确初始状态：对于给定数独，查找待填充的空白方格，并用一个栈数据结构保存

代码语言：javascript复制

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个子块中已出现的数字记录，并保存在字典中

代码语言：javascript复制

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：如果存在一个可行的数字，则在此基础上递归填充下一空白；否则，回溯上一状态，寻求其他解决方案

代码语言：javascript复制

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

主调用程序：完成初始状态，递归求解。由于在递归求解中是直接更改的原数独数组，所以无返回值。

代码语言：javascript复制

if __name__ == '__main__':
    rowMap, colMap, blockMap = getMaps(board)
    locs = getLocs(board)
    if fillBoard(board, locs):
        print(board)

执行结果

数独结果

代码语言：javascript复制

[['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']]

执行效率

云数据库MySQL

0 人点赞