Python判断有效的数独算法示例
本文实例讲述了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语句来判断也行，那样比较好理解，但是不如这个式子简洁
- 类似于:ify<3:...elif3<=y<6:...elif6<=y:...,
代码如下：
#row，col，cell分别代表行，列，3x3单元格
row,col,cell=
[{},{},{},{},{},{},{},{},{}],
[{},{},{},{},{},{},{},{},{}],
[{},{},{},{},{},{},{},{},{}]
forxinrange(9):
foryinrange(9):
#取得单元格
num=3*(x//3)+y//3
temp=board[x][y]
#不需要存入'.'
iftemp!='.':
if(tempnotinrow[x]
andtempnotincol[y]
andtempnotincell[num]):
row[x][temp]='1'
col[y][temp]='1'
cell[num][temp]='1'
else:
returnFalse
returnTrue
时间64ms，击败了99.3%
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数组操作技巧总结》、《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。