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 FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优