用python查找有效的數獨:
每日一題:
判斷一個 9x9 的數獨是否有效。只需要根據以下規則,驗證已經填入的數字是否有效即可。
- 數字 1-9 在每一行只能出現一次。
- 數字 1-9 在每一列只能出現一次。
- 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。
![每日一題:用python查找有效的數獨](http://p2.ttnews.xyz/loading.gif)
上圖是一個部分填充的有效的數獨。
數獨部分空格內已填入了數字,空白格用 '.' 表示。
示例 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
示例 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 存在, 因此這個數獨是無效的。
說明:
- 一個有效的數獨(部分已被填充)不一定是可解的。
- 只需要根據以上規則,驗證已經填入的數字是否有效即可。
- 給定數獨序列只包含數字 1-9 和字符 '.' 。
- 給定數獨永遠是 9x9 形式的。
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
cacheCol = [[0] * 9 for _ in range(0, 10)]
cacheRow = [[0] * 9 for _ in range(0, 10)]
cacheBox = [[0] * 9 for _ in range(0, 10)]
for i in range(0, 9):
for j in range(0, 9):
ib = (i / 3) * 3 + j / 3
if board[i][j] == ".":
continue
num = int(board[i][j]) - 1
if cacheRow[i][num] != 0 or cacheCol[j][num] != 0 or cacheBox[ib][num] != 0:
return False
cacheRow[i][num] = 1
cacheCol[j][num] = 1
cacheBox[ib][num] = 1
return True