千家信息网

怎么使用Python进行数独求解

发表于:2025-01-18 作者:千家信息网编辑
千家信息网最后更新 2025年01月18日,本篇内容主要讲解"怎么使用Python进行数独求解",感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习"怎么使用Python进行数独求解"吧!1. 引言数独这个名
千家信息网最后更新 2025年01月18日怎么使用Python进行数独求解

本篇内容主要讲解"怎么使用Python进行数独求解",感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习"怎么使用Python进行数独求解"吧!

1. 引言

数独这个名字的由来来自日语短语suuji wa dokushin ni kagiru,意思是"数字必须保持单一"。数独游戏的流行也源于其规则的简单性:数独游戏要求在 9 x 9 空间的网格上进行数字填写。在行和列中有 9 个"正方形"的格子block(由 3 x 3 个子单元格cell组成)。每一行、每一列、每一个block都需要填写数字 1-9,行、列、block内不得重复任何数字。

好的,知道了上述数独的规则,那么我们就来直接进入主体吧。 :)

2.描述数独九宫格

这一步主要为使用一组数字来初始化我们的九宫格。我们使用setBoard() 函数将输入转换为适合我们后续操作的数据类型。我们使用以下约定:

  • 空的单元格cell初始化为默认值0。

  • 维持数独谜题数字值的数据类型是一个 9x9 大小的二维列表。

这里我们的输入是一个多行字符串,我们将其处理成二维列表的形式。样例代码如下:

# Initialize a 2-D list with initial values described by the problem. # Returns boarddef setBoard():    board = list()    sudokuBoard = '''    200080300        060070084        030500209        000105408        000000000        402706000        301007040        720040060        004010003        '''    rows = sudokuBoard.split('\n')    for row in rows:        column = list()        for character in row:            digit = int(character)            column.append(digit)        board.append(column)    return board

上述代码运行后,如果展示在拼图游戏中,他的样子大概如下:

3.寻找下一个空子单元格

函数findEmpty() 函数的操作更加简单:对初始化后的九宫格作为参数传递,然后该遍历该九宫格中每一个子单元格cell,直到找到返回的第一个空的子单元格。如果没有找到空的子单元格,这表明我们的问题已解决,因此它返回None。

样例代码如下:

# Find next empty space in Sudoku board and return dimensionsdef findEmpty(board):    for row in range(9):        for col in range(9):            if board[row][col] == 0 :                return row,col    return None

4. 子单元格中设置值的合法性

函数isValid()的操作是确认设定的数字是否是九宫格子单元格的有效选项。为了使设置的值满足数独九宫格的要求,该值的设置需满足以下条件:

  • 同一行的任何子单元格cell都不应包含该数字

  • 同一列的任何子单元格cell都不应包含该数字

  • 该子单元格cell所在的block不应该包含该数字

如果我们设定的值满足以上所有条件,该函数返回True,否则返回False。代码如下:

# Check whether a specific number can be used for specific dimensionsdef isValid(board, num, pos):    row, col = pos    # Check if all row elements include this number    for j in range(9):        if board[row][j] == num:            return False    # Check if all column elements include this number    for i in range(9):        if board[i][col] == num:            return False    # Check if the number is already included in the block    rowBlockStart = 3* (row // 3)    colBlockStart = 3* (col // 3)    rowBlockEnd = rowBlockStart + 3    colBlockEnd = colBlockStart + 3    for i in range(rowBlockStart, rowBlockEnd):        for j in range(colBlockStart, colBlockEnd):            if board[i][j] == num:                return False    return True

以下是通过isValid() 函数中描述的条件后成功插入新值的动态示例:

同时,若我们引入一个与九宫格数独上已经存在的值冲突的数值,那么此时该值将不会被插入。图例如下:

5. 实现回溯算法

下一个函数是我们整个解决方案的核心思想,这里引入了回溯思想,该算法的实现步骤如下:

  • 搜索下一个空的子单元格cell。如果没有找到,那么我们已经解决了这个难题;如果没有,则转到第 2 步。

  • 通过迭代数字1-9 来猜测正确的数字,并参考已经确定的数字来检查它是否是一个合法的数字。

  • 如果找到一个有效的数字,此时递归调用solve() 函数并猜测下一个空的子单元格cell。

  • 如果数字1-9均无效,则将将子单元格cell的值重置为 0,并继续迭代以查找下一个有效数字。

# Solve Sudoku using backtrackingdef solve(board):    blank = findEmpty(board)    if not blank:        return True    else:        row, col = blank    for i in range(1,10):        if isValid(board, i, blank):            board[row][col] = i            if solve(board):                return True            board[row][col] = 0    return False

由于递归理解起来不是那么直观,不妨让我们尝试使用动态来将整个过程形象化:

正如我们在上面的示例中看到的那样,该算法用有效数字填充空子单元格cell,直到出现死胡同;然后它回溯,直到重新迭代该过程。

6. 性能表现

上述我们的程序需要使用回溯算法来遍历每个单元格的许多潜在值。这当然不是最优的解法,可以预想到我们的解决方法的性能会很慢。

我们使用上述代码,来解决欧拉计划的第96题中的50道数独题目,运行时间为:

The execution time of above program is : 23.56185507774353 s

到此,相信大家对"怎么使用Python进行数独求解"有了更深的了解,不妨来实际操作一番吧!这里是网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

数字 单元 函数 九宫 代码 有效 算法 条件 迭代 合法 一行 个子 内容 动态 思想 性能 数据 方法 格子 示例 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 佛山软件开发公司招聘 广东绿力网络技术有限公司官网 唐山软件开发销售电话 db2数据库文件格式 花季app链接服务器失败 方舟服务器管理员密码破解 软件开发合同培训条款 数据库 建库和表 软件开发和软件开发服务开票 辽宁网络技术分类服务标准 小程序 业务服务器 dell710服务器灯亮黄灯 计算三级计算机网络技术 惠州考试软件开发电话 金仓数据库设置自增 关于网络安全海报一等奖 济南领信软件开发公司吗 盈环网络技术有限公司电话 智阳网络技术上海有限公司 四川澜梦互联网科技有限公司 金山区网络技术开发报价表 数据库怎么处理并发 pubmed数据库是什么数据库 北京制造软件开发价位 做定位软件开发怎么弄 上海新能源网络技术零售价格 中科曙光软件开发工作怎样 湖南聚达网络技术 乡镇网络安全信息系统自查表 云服务器如何查看数据库
0