专栏首页小数志递归+回溯求解数独问题

递归+回溯求解数独问题

导读:回溯是常用的算法理论之一,很多规模较大、直接分析较为复杂的问题都可以考虑用回溯求解,例如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']]
  • 执行效率

本文分享自微信公众号 - 小数志(Datazhi),作者:luanhz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

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

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

    luanhz
  • 解数独

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

    你的益达
  • 用回溯算法求解数独问题

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

    疯狂的技术宅
  • 第7期 | cmd-parser,一个基于哈希匹配的超快命令解析器

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

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

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

    AI那点小事
  • 《剑指offer》二维数组中的查找——巧妙解法

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

    AI算法与图像处理
  • python数据科学-多变量数据分析

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

    张俊红
  • 几类关系型数据库的数据解决方案

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

    jeanron100

扫码关注云+社区

领取腾讯云代金券