python解数独谜题思路和代码分享

2023-10-16 22:50

本文主要是介绍python解数独谜题思路和代码分享,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数独简介

         数独(shù dú)是源自18世纪瑞士的一种数学游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。

数独基础规则1

        数独的每个单元格内容要满足每一行、每一列、每一个粗线宫(3*3)内的数字均含1-9,不重复。根据这条规则,我们能很容易得出以下判断方法:

 # 基础校验规则,检验num是否符合行列九宫格三项def base_rule(row, col, num):# 检查行for i in range(n):if board[row][i] == num:return False# 检查列for i in range(n):if board[i][col] == num:return False# 检查 3x3 方格内是否存在相同数字start_row = 3 * (row // 3)start_col = 3 * (col // 3)for i in range(3):for j in range(3):if board[start_row + i][start_col + j] == num:return Falsereturn True

 如果我们填入了一个值,他满足行,列,九宫格都未出现过,那么他便是这个单元格中的一个“可能值“

 可能值规则

        什么是可能值?对于一个数独的空位置来说,没有到达一定的深度之前,我们这个空位使用规则一能满足的值便是可能值,一个空位置里,有一个或多个可能值的存在

[[5], [3], [1, 2, 4], [2, 4], [7], [4, 8], [1, 4, 9], [2, 8], [1, 2, 4]]
[[6], [2, 4, 7], [2, 4, 7], [1], [9], [5], [3, 4, 7], [2, 3, 7, 8], [2, 3, 4]]
[[1, 2, 4], [9], [8], [2, 4], [2], [3, 4], [1, 3, 4, 5, 7], [6], [1, 2, 3, 4, 5]]
[[8], [2], [1, 2, 5], [1, 4, 5, 7, 9], [6], [1, 4, 5, 9], [4, 5, 7, 9], [2, 7], [3]]
[[4], [2], [2, 5], [8], [5, 7, 9], [3], [5, 7, 9], [2, 7], [1]]
[[7], [3], [1, 3, 5], [1, 4, 5, 9], [2], [1, 4, 5, 9], [4, 5, 9], [8], [6]]
[[1, 4, 9], [6], [1, 3, 4, 5, 7], [5, 7], [5, 7], [3, 5], [2], [8], [1, 3, 4]]
[[2, 8], [2, 3, 7, 8], [2, 3, 7], [4], [1], [9], [3], [3, 6], [5]]
[[1, 2, 4], [2, 3, 4], [1, 2, 3, 4, 5], [2, 5], [8], [3, 5], [1, 3, 4], [7], [9]]

图1、一个数独内可能值举例

这样看可能会比较抽象,但是我们结合原始数独来分析:

5 3 0 | 0 7 0 | 0 0 0   

6 0 0 | 1 9 5 | 0 0 0

0 9 8 | 0 0 0 | 0 6 0

---------------------

8 0 0 | 0 6 0 | 0 0 3

4 0 0 | 8 0 3 | 0 0 1

7 0 0 | 0 2 0 | 0 0 6

---------------------

0 6 0 | 0 0 0 | 2 8 0

0 0 0 | 4 1 9 | 0 0 5

0 0 0 | 0 8 0 | 0 7 9

比如我们看第一行的第三个,[1,2,4]是该空位的三个可能值,因为其他数字在行列九宫格出现过,所以这一空我们只能在这三个中选择其中之一,那么该如何得出可能值呢?

 # 消除规则一,经过base_rule筛选后的可能值def rule_1():list_3d = [[[] for _ in range(9)] for _ in range(9)]for row in range(9):for col in range(9):if board[row][col] != 0:list_3d[row][col].append(board[row][col])else:for i in range(1, 10):if base_rule(row, col, i):list_3d[row][col].append(i)# print("规则一之后")# for row in range(9):#     print(list_3d[row])#     print()return list_3d

board是我们的原始数组,我创建的list_3d类是一个二维列表,这个二维列表的每个元素又是一个列表,从图1我们便可以看出。使用if判断不为零的直接放入,而为0的(空位置)则需要用base_rule循环判断,打印列表,你也能得到类似图一的效果。

消除规则二

        原理:如果可能某个值在行、列、九宫格里只出现过一次,那么我们便可以判定这个空位置的值就是这个只出现过一次的值。

这个原理也可以反向理解,如果一个可能值只在这个位置出现了,而行列九宫格中的其他地方没有,是不是表示这个值就只能待在这个空,否则他无处可去了呢?

通过这项规则,我们似乎又可以确定一些空位置该填什么了:

 # 基础消除规则2,如果可能值满足在行列九宫只出现1次,则可以确定为该值def base_rule2(row, col, num, current_board):flag1 = Trueflag2 = Trueflag3 = Truefor i in range(n):if i != col and num in current_board[row][i]:flag1 = Falsebreak# 检查列for i in range(n):if i != row and num in current_board[i][col]:flag2 = Falsebreak# 检查 3x3 方格内是否存在相同数字start_row = 3 * (row // 3)start_col = 3 * (col // 3)for i in range(start_row, start_row + 3):if not flag3:breakfor j in range(start_col, start_col + 3):if num in current_board[i][j] and (i != row or j != col):flag3 = Falsebreak# if flag1 or flag2 or flag3:# print("检查到唯一值" + str(row) + "," + str(col) + "," + str(num) + str(flag1) + ",# " + str(flag2) + "," + str(flag3))return flag1 or flag2 or flag3

并且,我们还能通过确认这个值,再次消除一些可能值,假如[1,2,4]这三个里,我确认了1是唯一的,那么除了他所在的那个单元格,与他同行,同列,同九宫格的所有的1都可以被消除:

 # 通过规则二检测到可能值后,清除行,列,九宫格内所有可能值,被间接消除的只剩一个是会继续调用def clear_row(row, col, num, current_board):for i in range(9):if i != col and num in current_board[row][i]:current_board[row][i].remove(num)if len(current_board[row][i]) == 1:clear_col(row, i, current_board[row][i][0], current_board)clear_cell(row, i, current_board[row][i][0], current_board)# print("得到值,继续消除列和九宫" + str(current_board[row][i][0]))def clear_col(row, col, num, current_board):for i in range(9):if i != row and num in current_board[i][col]:current_board[i][col].remove(num)if len(current_board[i][col]) == 1:clear_row(i, col, current_board[i][col][0], current_board)clear_cell(i, col, current_board[i][col][0], current_board)# print("得到值,继续消除行和九宫" + str(current_board[i][col][0]))def clear_cell(row, col, num, current_board):start_row = 3 * (row // 3)start_col = 3 * (col // 3)for i in range(start_row, start_row + 3):for j in range(start_col, start_col + 3):if num in current_board[i][j] and (i != row or j != col):current_board[i][j].remove(num)if len(current_board[i][j]) == 1:clear_row(i, j, current_board[i][j][0], current_board)clear_col(i, j, current_board[i][j][0], current_board)# print("得到值,继续消除行和列" + str(current_board[i][j][0]))

注意,我为什么说间接消除的要多执行一次消除?比如 [1,5]......[2,5]在同一行,当遍历到[2,5]时,确认可能值只有5,那么[1,5]中会被消除的只剩[1],相当于又确认了一个值,所以我们要移到[1,5]所在的行列继续进行消除

搜索+回溯

        经过一次消除规则1和消除规则2的处理,我们数独空位里的可能值也少了很多,这个时候我们可以选择直接遍历+回溯带入可能值来进行最终的解数独,也可以使用搜索+回溯来解,这里我选择的是搜索+回溯,每次搜索可能值最少的那个位置开始试

  def search(result):current_len = 9999current_row = 9999current_col = 9999for row in range(9):for col in range(9):if current_len >= len(result[row][col]) > 1:current_len = len(result[row][col])current_row = rowcurrent_col = colreturn current_row, current_col# 经过一二消除后,开始递归可能值解数独def recursion(result):if isOver(result):return Truerow, col = search(result)for i in result[row][col]:if board[row][col] == 0 and base_rule(row, col, i):temp = copy.deepcopy(result[row][col])result[row][col] = [i]board[row][col] = iif recursion(result):return True# 撤销选择,将之前移除的候选数字添加回去并重置为0result[row][col] = tempboard[row][col] = 0return False

到这里解数独大部分程序都完成了,最后根据自己需要,选择输入值,判断数独结束方法等

最终执行效果:

 解50个大约14s,简单数独平均0.01s一个,但是这50个里有两个解的很慢,一个2s,一个8s,这点笔者也还没研究出是为什么

 

经过分析后发现是搜索方法的问题,注释掉搜索方法,重新编写回溯执行,只需要2s

这篇关于python解数独谜题思路和代码分享的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/221293

相关文章

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模