一、题目
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1-9 without repetition.1-9 without repetition.3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.‘.
Example 1:
Input: [ ["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"] ] Output: true
Example 2:
Input:
[
["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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8‘s in the top left 3x3 sub-box, it is invalid.
Note:
1-9 and the character ‘.‘.9x9.题目大致意思就是，数独的规则，每行1~9不重复，每列1~9不能重复，3x3小方格1~9不重复。
二、思路
此题使用可以分别判断行列和小方格内的数字是否重复，可以利用哈希思想，其实就是python中的字典也是一样的，逐一遍历行列和小方格，遇到不同的值就存进去，若是存储的过程中遇到相同的就返回False。
行号规律
观察行号规律：
第0个九宫格：000111222; 第1个九宫格：000111222; 第2个九宫格：000111222;
第3个九宫格：333444555; 第4个九宫格：333444555; 第5个九宫格：333444555;
第6个九宫格：666777888; 第7个九宫格：666777888; 第8个九宫格：666777888;
可见对于每三个九宫格行号增3；对于单个九宫格，每三个格点行号增1。
因此第i个九宫格的第j个格点的行号可表示为i/3*3+j/3
三、代码
#coding:utf-8
‘‘‘
Solution0最原始暴力求解，但代码冗余
‘‘‘
class Solution0:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for row in range(9):
if not self.isValidNine(board[row]):
return False
column = [c[row] for c in board]
if not self.isValidNine(column):
print(‘False‘)
return False
for i in [0,3,6]:
for j in [0,3,6]:
block = [board[s][t] for s in [i,i+1,i+2] for t in [j,j+1,j+2]]
if not self.isValidNine(block):
print(False)
return False
print(‘True‘)
return True
def isValidNine(self,row):
"""
当前九个数字是否有效
:param row:int
:return:bool
"""
map = {}
for c in row:
if c != ‘.‘:
if c in map:
return False
else:
map[c] = True #若字典map中没有c，则将c存至该map字典中，key为c，value为True
return True
‘‘‘
Solution1精简代码，分别用三个矩阵来检查三个规则是否有重复数字
‘‘‘
class Solution1:
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
row = [[False for i in range(9)] for j in range(9)]
col = [[False for i in range(9)] for j in range(9)]
block = [[False for i in range(9)] for j in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] != ‘.‘:
num = int(board[i][j])-1 #这里其实使用了哈希思想，因为数字都是在0~9之间，所以索引减1，试想如果某个位置上的数字和其他位置的数字相同的话，其num值也是一样的，所以通过True或者False就可以辨别是否有重复
k = i//3*3 + j//3 #K表示第i个九宫格的第j个格点的行号
if row[i][num] or col[j][num] or block[k][num]:
print(‘False‘)
return False
row[i][num] = col[j][num] = block[k][num] = True
print(‘True‘)
return True
if __name__ == ‘__main__‘:
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"]
]
#ss =Solution0()
ss = Solution1()
ss.isValidSudoku(board)
参考博客：https://www.cnblogs.com/ganganloveu/p/4170632.html https://blog.csdn.net/coder_orz/article/details/51596499
LeetCode Medium: 36. Valid Sudoku
原文：https://www.cnblogs.com/xiaodongsuibi/p/8982486.html