Python判断有效的数独算法示例
作者:linfeng886 发布时间:2021-10-09 06:37:37
本文实例讲述了Python判断有效的数独算法。分享给大家供大家参考,具体如下:
一、题目
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独部分空格内已填入了数字,空白格用 ‘.' 表示。
例1:
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
例2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
二、解法
先创建三个空数组 row、col、cell,以 cell 为例,里面的每个空字典都代表一个 3×3单元格,然后我们需要把数据一个个填进去
遍历整个二维数组,然后边遍历边把数组分别存入到 行 row , 列 col , 3×3单元格 cell 内的字典,存为key ,而不是 value 。
然后我们就可以判断,行、列、3×3单元格 对应的字典内是否已经存在board[x][y]这个键名,如果存在,那么说明重复了,返回 False
注意,字典中的值这里都为1,但是没有任何意义,你可以随意更改
把数组存入 3×3的单元格是一个难点,num = 3*(x//3)+y//3,这个式子是关键,可以找个数独,然后代入进去好好理解下
当然你也可以不用这个式子,用if/else语句来判断也行,那样比较好理解,但是不如这个式子简洁
类似于: if y<3 : ... elif 3<=y<6 : ... elif 6<=y : ...,
代码如下:
#row,col,cell分别代表行,列,3x3单元格
row, col, cell =
[{}, {}, {}, {}, {}, {}, {}, {}, {}],
[{}, {}, {}, {}, {}, {}, {}, {}, {}],
[{}, {}, {}, {}, {}, {}, {}, {}, {}]
for x in range(9):
for y in range(9):
#取得单元格
num = 3*(x//3)+y//3
temp = board[x][y]
#不需要存入 '.'
if temp != '.':
if (temp not in row[x]
and temp not in col[y]
and temp not in cell[num]):
row[x][temp] = '1'
col[y][temp] = '1'
cell[num][temp] = '1'
else:
return False
return True
时间 64ms,击败了 99.3%
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/linfeng886/article/details/82778890
猜你喜欢
- 大家好,学完面向对象与异常处理机制之后,接下里我们要学习 包与模块 。首先我们要了解什么是包?什么是模块?接下来我们还要学习 如何自定义创建
- 块级元素块级元素生成一个元素框,(默认地)它会填充其父级元素的内容,旁边不能有其他元素。换句话说,他在元素框之前和之后生成了“分隔”符。我们
- 构筑专业的网络站点和应用程序,先进的设计工具,功能强大,开放式集成系统;流畅的开发进程。Macromedia Dreamweaver MX
- 惊现!表面下的隐藏信息——浅谈信息可视化1910年,病卧床上的魏格那(德国气象学家,以“大陆漂移学说”闻名),无意地注视着墙上的世界地图……
- xml(可扩展标记语言)看起来可能像某种w3c标准——现在没有什么实际影响,即使以后能派上用场,也是很久以后的事。但实际上,它现在已经得到了
- 问题描述前端 vue 框架,后台 php,百度跨域问题后台加这段代码header("Access-Control-Allow-Or
- 本文实例讲述了Golang最大递减数算法问题。分享给大家供大家参考,具体如下:给出一个非负整数,找到这个非负整数中包含的最大递减数。一个数字
- 如下所示:arrs=[2,15,48,4,5,6,7,6,4,1,2,3,6,6,7,4,6,8]f=open('test.txt&
- 下拉框连动JavaScript代码,市区二级联动多级联动下拉选择框,动态获取下一级琥珀无限级联动菜单-JavaScript版 <htm
- 前几天帮人调试一个ASP+SQL2000+IIS5.1/6.0的网站程序,调试过程中遇到的问题如下:一、 SQLServer登录 原先存在备
- go-ini的分区go-ini的多个配置项通过分区(section)来划分。有默认(空)分区和命名的分区,没有给分区命名就是默认分区,默认分
- 从这节开始,将会给大家介绍几个ASP中的三大通用类,它贯穿于我所设计的三层架构中,是对ASP语法的扩展,可以提高很多细节处理上的效率,可以算
- 概述迭代器是访问集合元素的一种方式。迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。迭代器只能往前不会后退。延迟计算或惰性
- 质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两
- python这样注释,让你的代码看起来更加的优雅,是不是常常感觉自己的python代码写出来,看起来特别的乱,虽然可以正常运行,但是在优雅性
- Python项目文件中安装 setup.py安装 setup.py 的过程与安装其他的 Python 包的过程类似。首先,你需要下载或者使用
- 表单验证是WEB开发中经常遇到的问题,我们以前常见的做法是:在客户端对表单域进行内容的检查,看是否是满足一定的要求或满足一定的结构,比如:是
- 本文实例讲述了Python实现子类调用父类的方法。分享给大家供大家参考。具体实现方法如下:python和其他面向对象语言类似,每个类可以拥有
- 前言首先抛出几个问题:console.log(Boolean({}));console.log(Number([]));console.lo
- 本文实例讲述了Python实现的数据结构与算法之基本搜索。分享给大家供大家参考。具体分析如下:一、顺序搜索顺序搜索 是最简单直观的搜索方法: