Python每日一练-----那些年你曾经玩过的数独
✐拒绝平躺，每日一卷（第10天）
目录
题目分析：
暴力解法：
哈希解法：
题目：判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
1.数字 1-9 在每一行只能出现一次。
2.数字 1-9 在每一列只能出现一次。
3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。注意：
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用
'.'表示。
示例：
输入：board =
[["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
输入：board =
[["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 存在, 因此这个数独是无效的
题目分析：
玩过数独的应该知道，一个数独是否有效可以判断这个数独表的行和列是否出现相同的数字，再判断小九宫格是否出现相同的数字。若出现相同数字则该数独无效，反之则有效。
判断行和例是否相同
可以看出数独的行即为数组中的一个子列表，数独中的列由为9行子列表中第n个元素构成。
判断行列的数是否相同可以遍历每个子列和遍历子列表中的第n个数。
再遍历前可以将遍历时遇到的数字加入一个集合中，当遍历该行时遇到已添加的数则出现重复，数独无效。
# 判断行含有数字是否相同 for child_list in board: row = set() # 定义一个包含行数值的集合 for j in child_list: if j != ".": if j in row: # return False else: row.add(j)接下来是行，同样的方法
# 判断列含有数字是否相同 for i in range(9): column = set() # 定义一个包含例数值的集合 for j in range(9): if board[j][i] != ".": if board[j][i] in column: return False else: column.add(board[j][i])接下来判断小九宫格，如何选出小九宫格的数？我们已第一个小九宫格为例：
第一个小九宫格 = 第一个子列表的前三位数 + 第二个子列表的前三位数 + 第三个子列表的前三位数
=board[1][前三位] + board[2][前三位] + board[3][前三位]
以此类推
# 判断小九宫格 for i in range(3): for j in range(3): square = set() for m in range(3): for n in range(3): if board[m + 3 * i][n + 3 * j] != ".": # 实现提取小九宫格，遍历顺序n>m>j>iif board[m + 3 * i][n + 3 * j] in square: return Falseelse: square.add(board[m + 3 * i][n + 3 * j])暴力解法：
将上述分析结合
def isValidSudoku(board): # 判断行含有数字是否相同 for child_list in board: row = set() # 定义一个包含行数值的集合 for j in child_list: if j != ".": if j in row: # return False else: row.add(j) # 判断列含有数字是否相同 for i in range(9): column = set() # 定义一个包含例数值的集合 for j in range(9): if board[j][i] != ".": if board[j][i] in column: return False else: column.add(board[j][i]) # 判断小九宫格 for i in range(3): for j in range(3): square = set() for m in range(3): for n in range(3): if board[m + 3 * i][n + 3 * j] != ".": # 实现提取小九宫格，遍历顺序n>m>j>i if board[m + 3 * i][n + 3 * j] in square:return False else:square.add(board[m + 3 * i][n + 3 * j]) return True接下来再介绍哈希解法
哈希解法：
这里主要是运用哈希算法避免重复计算的思想来解题。在暴力解法中我们每次检验是否有效都遍历一次数组，这就出现了重复的计算。所以我们想要提高效率就需要减少重复计算，而哈希算法可以只用遍历一次就可以判断是否有效。如果你没有接触过哈希算法，你完全可以吧哈希当作列表来看。
创建哈希表（列表）
# 创建三个元素都为零的数组 rows = [[0] * 9 for i in range(9)] # columns = [[0] * 9 for i in range(9)] subboxes = [[[0] * 9 for i in range(3)] for i in range(3)]改变一些数值，减少列表长度后可以看到以下输出
接着我们只需遍历一次列表
因为有效的数独，行列，小九宫格出现的数唯一
所以可以将获取到的数值作为序数，将对应数组（rows，column，subboxes）对应的位置加1。
接着检测数组（rows，column，subboxes）中对应的位置是否为1
唯一的数只能用做一个序数----->对应的值也只能加1
如果超过1，说明对应的位置加了n次1------->该数不唯一
def isValidSudoku(board): # 创建三个元素都为零的数组 rows = [[0] * 9 for i in range(9)] columns = [[0] * 9 for i in range(9)] subboxes = [[[0] * 9 for i in range(3)] for i in range(3)] # 遍历行，列，小九宫格 for i in range(9): for j in range(9): c = board[i][j] # 遍历数组元素 if c != '.': c = int(c) - 1 # 数组元素为字符串需要使用int（）转化成数值，c可已取到9，但是row[i][9]已经超出列表长度，所以c需要-1 rows[i][c] += 1 # 将获取到的数c作为序数，然后将序数对应的位置+1，以便后续的判断 columns[j][c] += 1 subboxes[int(i / 3)][int(j / 3)][c] += 1 if rows[i][c] > 1 or columns[j][c] > 1 or subboxes[int(i / 3)][int(j / 3)][c] > 1: return False return True这样我们只需遍历一次数组就可以判断数独是否有效了。
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
