判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
<small style="box-sizing: border-box; font-size: 12px;">上图是一个部分填充的有效的数独。</small>
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 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
</pre>
示例 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 存在, 因此这个数独是无效的。</pre>
说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 给定数独序列只包含数字
1-9和字符'.'。 - 给定数独永远是
9x9形式的。
- 执行用时为 44 ms 的范例
class Solution:
# @param board, a 9x9 2D array
# @return a boolean
def isValidSudoku(self, board):
row = [set([]) for i in range(9)]
col = [set([]) for i in range(9)]
grid = [set([]) for i in range(9)]
for r in range(9):
for c in range(9):
if board[r][c] == '.':
continue
if board[r][c] in row[r]:
return False
if board[r][c] in col[c]:
return False
g = r / 3 * 3 + c / 3
if board[r][c] in grid[g]:
return False
grid[g].add(board[r][c])
row[r].add(board[r][c])
col[c].add(board[r][c])
return True
- 执行用时为 52 ms 的范例
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
s_row = [set() for i in range(9)]
s_col = [set() for i in range(9)]
s_box = [[set() for i in range(3)] for j in range(3)]
for i in range(9):
for j in range(9):
item = board[i][j]
if item != '.':
if item in s_row[i]:
return False
s_row[i].add(item)
if item in s_col[j]:
return False
s_col[j].add(item)
bi, bj = i/3, j/3
if item in s_box[bi][bj]:
return False
s_box[bi][bj].add(item)
return True
- 执行用时为 60 ms 的范例
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for row in board:
if not self.checkNums(row):
return False
for i in range(9):
col = [board[j][i] for j in range(9)]
if not self.checkNums(col):
return False
for i in range(0,9,3):
for j in range(0,9,3):
if not self.checkNode(row=i,col=j, board=board):
return False
return True
def checkNode(self, row=0, col=0, board=None):
lyst = []
for i in range(3):
for j in range(3):
lyst.append(board[row+i][col+j])
return self.checkNums(lyst)
def checkNums(self, lyst):
null_cnt = lyst.count('.')
m_set = set(lyst)
if '.' in lyst:
return len(m_set) - 1 + null_cnt == len(lyst)
else:
return len(m_set) == len(lyst)
