判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
- 數(shù)字
1-9在每一行只能出現(xiàn)一次主慰。 - 數(shù)字
1-9在每一列只能出現(xiàn)一次。 - 數(shù)字
1-9在每一個(gè)以粗實(shí)線分隔的3x3宮內(nèi)只能出現(xiàn)一次鲫售。
image
上圖是一個(gè)部分填充的有效的數(shù)獨(dú)共螺。
數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示情竹。
輸入:
[
["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
解答：
這道題相對(duì)來(lái)講稍微難一點(diǎn)藐不，需要考慮多種情況，判斷行秦效，判斷列雏蛮，判斷3x3的塊。
class Solution:
"""
:type board: List[List[str]]
:rtype: bool
"""
import collections
def isValidSudoku(self, board):
## check row
for i in range(9):
dic1 = collections.Counter(board[i])
for k,v in dic1.items():
if k!='.' and v>1:
return False
## check column
for j in range(9):
dic2 = collections.Counter([x[j] for x in board])
for k,v in dic2.items():
if k!='.' and v>1:
return False
## check block
for i in range(9):
for j in range(9):
## 關(guān)鍵在于這個(gè)部分阱州，當(dāng)i和j為0,3,6的時(shí)候挑秉，判斷block是否有效
if i%3==0 and j%3==0:
if not Solution.checkblock(board,i,j):
return False
return True
def checkblock(board,r,c):
dic = {}
for i in range(r,r+3):
for j in range(c,c+3):
if board[i][j]!='.':
if board[i][j] in dic:
return False
dic[board[i][j]]=1
return True
