【Python】判断数独是否合法

tracy 发布于2019-07-25 10:49 / 2656人阅读

摘要：题目描述请判定一个数独是否有效。解体思路将数独按照行列和块进行预处理，然后分别判断是否合法。代码利用一些技巧直接按块储存数据判断一条记录按某种方式排列的九个数字是否合法一步搞定感想能不用循环体尽量不用循环体，她好，我也好。

背景

在LintCode刷题的时候碰到一个很水的题目，不过要注意很多细节，不然调试的时候非常麻烦，利用Python的一些小技巧写了一个很简短的解决方案。

题目描述

请判定一个数独是否有效。

该数独可能只填充了部分数字，其中缺少的数字用 . 表示。

注意事项

一个合法的数独（仅部分填充）并不一定是可解的。我们仅需使填充的空格有效即可。

解体思路

将数独按照行、列和块进行预处理，然后分别判断是否合法。

利用Python的表达式推导，匿名函数和all函数可以很方便的进行处理。

代码

class Solution:

# @param board, a 9x9 2D array
# @return a boolean
def isValidSudoku(self, board):
    rows = [list(lst[::]) for lst in board]
    columns = [[lst[idx] for lst in board] for idx in range(9)]
    blocks_origin = [board[row][column] for x in [[0, 1, 2], [3, 4, 5], [6, 7, 8]] for y in [[0, 1, 2], [3, 4, 5], [6, 7, 8]] for row in x for column in y] # 利用一些技巧直接按块储存数据
    blocks = [[blocks_origin[row * 9 + column] for column in range(9)] for row in range(9)]
    check = lambda lst: all([lst.count(x) == 1 for x in lst if x != "."]) # 判断一条记录（按某种方式排列的九个数字）是否合法
    return all([check(x) for style in (rows, columns, blocks) for x in style]) # 一步搞定

# 感想
能不用循环体尽量不用循环体，她好，我也好。

GPU云服务器云服务器 python判断文件是否存在是否合法 js合法性判断 IP地址合法性判断

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38181.html

leetcode36 Valid Sudoku 查看数独是否合法

摘要：如果重复则不合法，否则极为合法。在这里我们使用数组代替作为存储行列和小正方形的值得数据结构。我存储这所有的行列小正方形的情况，并判断当前值是否重复。外循环则代表对下一行，下一列和下一个小正方形的遍历。题目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...

wing324 2019-08-16 10:32 评论0 收藏0
【LeetCode】数组初级算法-有效的数独

摘要：题目描述有效的数独判断一个的数独是否有效。上图是一个部分填充的有效的数独。数独部分空格内已填入了数字，空白格用表示。说明一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。题目描述有效的数独判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出...

wyk1184 2019-08-23 11:44 评论0 收藏0
记数独X--Android openCV识别数独并自动求解填充APP开发过程

摘要：可以针对笔者常用的数独本文的实现都基于该，实现数独的识别求解并把答案自动填入。专家级别的平均秒完成求解包括图像数字提取，识别过程，完成全部操作。步骤四数独求解，生成答案，并生成需要填充的数字序列。 1 序数独是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3...

yvonne 2019-08-16 15:18 评论0 收藏0
LeetCode36.有效的数独 JavaScript

摘要：上图是一个部分填充的有效的数独。数独部分空格内已填入了数字，空白格用表示。但由于位于左上角的宫内有两个存在因此这个数独是无效的。说明一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。判断一个 9x9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次...

elva 2019-08-23 15:16 评论0 收藏0