資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中的有效數獨
假設我們有一個 9x9 的數獨棋盤。我們必須檢查該棋盤是否有效。根據以下規則，只需驗證已填入的方格 −
- 每一行都必須包含 1-9 的數字，不可重複。
- 每一列都必須包含 1-9 的數字，不可重複。
- 網格的 9 個 (3x3) 子方格中的每一個都必須包含 1-9 的數字，不可重複。
假設數獨網格如下 −
| 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 |
這是有效的。
為了解決這個問題，我們將遵循以下步驟 −
- 從 0 到 8 的 i
- 建立名為 row、col 和 block 的空字典，row_cube := 3 * (i / 3)，col_cube := 3 * (i mod 3)
- 從 0 到 8 的 j
- 如果 board[i, j] 不為空且 board[i, j] 在 row 中，則返回 false
- row[board[i, j]] := 1
- 如果 board[j, i] 不為空且 board[j, i] 在 col 中，則返回 false
- col[board[j, i]] := 1
- rc := row_cube + j/3 和 cc := col_cube + j mod 3
- 如果 board[rc, cc] 在 block 中且 board[rc, cc] 不為空，則返回 false
- block[board[rc, cc]] := 1
- 返回 true
示例（Python）
下面讓我們看看以下實現以加深理解 −
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
for i in range(9):
row = {}
column = {}
block = {}
row_cube = 3 * (i//3)
column_cube = 3 * (i%3)
for j in range(9):
if board[i][j]!='.' and board[i][j] in row:
return False
row[board[i][j]] = 1
if board[j][i]!='.' and board[j][i] in column:
return False
column[board[j][i]] = 1
rc= row_cube+j//3
cc = column_cube + j%3
if board[rc][cc] in block and board[rc][cc]!='.':
return False
block[board[rc][cc]]=1
return True
ob1 = Solution()
print(ob1.isValidSudoku([
["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"]]))輸入
[["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
更新於：2020-04-27
5 千+ 瀏覽
廣告