验证数独是否有效

验证数独是否有效

题目说明

判断一个9x9的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。

  2. 数字 1-9 在每一列只能出现一次。

  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

sample

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

解决方案

本题主要是思想就是满足每行、每列和每个单元中不存在重复的数就可以,具体实现方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
if board is None:
return False

# 初始化rows、colunms和cells
rows = [{},{},{},{},{},{},{},{},{}]
columns = [{},{},{},{},{},{},{},{},{}]
cells = [{},{},{},{},{},{},{},{},{}]

for i in range(len(board)):
for j in range(len(board[i])):
# 计算cell的位置
cell = 3 * (i // 3) + j // 3
val = board[i][j]
if val == '.':
continue

if val not in rows[i] and val not in columns[j] and val not in cells[cell]:
rows[i][val] = 1
columns[j][val] = 1
cells[cell][val] = 1
else:
return False

return True

说明: 如果您有更好的解决方案或者本人写的有什么问题,请多多指教!